基于組合規(guī)則的作業(yè)車間AGV 聯(lián)合調(diào)度優(yōu)化＊

鐘宏揚(yáng) 彭乘風(fēng) 廖 勇 李 翔

（①?gòu)V東工業(yè)大學(xué)廣東省計(jì)算機(jī)集成制造重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006；②湘南學(xué)院物理與電子電氣工程學(xué)院，湖南 郴州 423000）

在新冠疫情肆虐，人力成本逐漸攀升的制造業(yè)大背景下，傳統(tǒng)車間的智能化改造需求日益迫切。傳統(tǒng)車間通常制定獨(dú)立的任務(wù)作業(yè)計(jì)劃與物料搬運(yùn)計(jì)劃，再由管理者經(jīng)驗(yàn)式協(xié)調(diào)，這種割裂式的生產(chǎn)計(jì)劃制定手段將難以適用智能車間[1]。物料儲(chǔ)運(yùn)系統(tǒng)是智能車間生產(chǎn)閉環(huán)的關(guān)鍵環(huán)節(jié)，自動(dòng)導(dǎo)航小車(automated guided vehicle,AGV)作為重要承運(yùn)設(shè)備已經(jīng)成為物料有序流轉(zhuǎn)的重要保障，作業(yè)車間符合定制化企業(yè)多品種小批量的生產(chǎn)特點(diǎn)，但相關(guān)調(diào)度研究卻鮮有將物料運(yùn)輸過(guò)程控制納入考量[2]，故如何制定AGV 搬運(yùn)計(jì)劃以快捷響應(yīng)作業(yè)車間機(jī)床生產(chǎn)需求的聯(lián)合調(diào)度優(yōu)化問(wèn)題應(yīng)運(yùn)而生。

作業(yè)車間AGV 聯(lián)合調(diào)度可以解耦成作業(yè)車間機(jī)器調(diào)度與AGV 調(diào)度兩個(gè)關(guān)聯(lián)耦合的子問(wèn)題，由于兩個(gè)子問(wèn)題均已被證實(shí)為NP-hard[3-4]，所以作業(yè)車間AGV 聯(lián)合調(diào)度也屬于NP-Hard 問(wèn)題。表1 為作業(yè)車間環(huán)境下AGV 聯(lián)合調(diào)度文獻(xiàn)分類匯總，早期研究通過(guò)構(gòu)建混合整數(shù)規(guī)劃模型以精確法求解，例如Sigrid Knust[5]等基于上/下界約束松弛的算法求解聯(lián)合調(diào)度問(wèn)題，盡管全局優(yōu)化算法可以獲取最優(yōu)解，但全局優(yōu)化局限于小規(guī)模場(chǎng)景問(wèn)題求解，在現(xiàn)實(shí)場(chǎng)景中難以推廣。在中等規(guī)模以上的問(wèn)題求解上，元啟發(fā)式算法提供了有效的途徑，如混合粒子群搜索算法[6]、遺傳算法[7]等，但隨著問(wèn)題規(guī)模逐漸變大，問(wèn)題求解空間也指數(shù)型劇增，算法陷入早熟與局部最優(yōu)的概率隨之增加，有效鄰域搜索產(chǎn)生的時(shí)間代價(jià)與解的優(yōu)度控制相互掣肘，故此類算法性能相對(duì)依賴參數(shù)設(shè)置。啟發(fā)式規(guī)則因其高效快速、符合經(jīng)驗(yàn)直覺(jué)的特點(diǎn)被廣泛應(yīng)用于在線調(diào)度領(lǐng)域[8-10]。陳敏[9]等以單環(huán)布局多AGV 調(diào)度問(wèn)題為背景，比較分析了7 種調(diào)度規(guī)則的性能差異；郭沛佩[10]等在離散事件系統(tǒng)建模仿真技術(shù)下，分析了不同任務(wù)到達(dá)模式下AGV 調(diào)度規(guī)則與工件路由規(guī)則的組合性能。作為在線調(diào)度的常用策略，啟發(fā)式規(guī)則被認(rèn)為存在工況適應(yīng)的局限性，根據(jù)No free lunch 定律[11]單個(gè)規(guī)則無(wú)法在所有指標(biāo)上都完全勝過(guò)其他規(guī)則。因此，亟待提出一套組合規(guī)則設(shè)計(jì)框架，通過(guò)融合差異化規(guī)則的特征以期增強(qiáng)啟發(fā)式規(guī)則的場(chǎng)景適應(yīng)性。

表1 作業(yè)車間環(huán)境下AGV 聯(lián)合調(diào)度文獻(xiàn)

本文對(duì)研究問(wèn)題進(jìn)行結(jié)構(gòu)化分析后，構(gòu)建數(shù)學(xué)模型并設(shè)計(jì)一套組合規(guī)則算法框架，通過(guò)導(dǎo)入分屬不同子決策的規(guī)則以生成大量組合規(guī)則算法。鑒于組合規(guī)則的耦合性能受到任務(wù)和資源等多方面因素的影響，設(shè)計(jì)差異化的算例實(shí)驗(yàn)，以評(píng)估不同組合規(guī)則受實(shí)驗(yàn)參量敏感程度，進(jìn)而驗(yàn)證算法的有效性與穩(wěn)定性。

1 研究問(wèn)題及數(shù)學(xué)模型

如圖1 所示，作業(yè)車間AGV 聯(lián)合調(diào)度問(wèn)題可以描述為：已知待加工工件集合J={J1,J2,···,Jn}，任意工件的工藝路徑已知且唯一，工藝路徑有nj道工序，每道工序有且僅有一臺(tái)設(shè)備可以加工，作業(yè)車間中的加工設(shè)備資源集記為M={M1,M2,···,Mm}。物料儲(chǔ)運(yùn)系統(tǒng)由車間鋪設(shè)的軌道與r臺(tái)AGV 組成，AGV 往返于原料池、車間、成品倉(cāng)之間執(zhí)行物料轉(zhuǎn)運(yùn)操作，搬運(yùn)集合記為R={R1,R2,···,Rr}。為使研究更為聚焦，現(xiàn)對(duì)問(wèn)題所涉及的其他因素做抽象化假設(shè)：

圖1 運(yùn)輸能力有限的作業(yè)車間運(yùn)行示意圖

（1）所有待加工工件在零時(shí)刻都可加工，且工藝路徑、加工工時(shí)等信息已知。

（2）所有加工/搬運(yùn)設(shè)備在零時(shí)刻都處在空閑狀態(tài)，且設(shè)備在生產(chǎn)過(guò)程中一直可用，不考慮各類機(jī)器故障。

（3）加工工件的工藝路徑信息固定，同一個(gè)工件工序間的緊前緊后關(guān)系不得違背。

（4）同一臺(tái)加工設(shè)備在同一時(shí)刻只可以加工一個(gè)工件，且工序一旦開(kāi)始加工就不可中斷。

（5）同一臺(tái)搬運(yùn)設(shè)備在同一時(shí)刻只能搬運(yùn)一個(gè)工件，且搬運(yùn)過(guò)程不可中斷。

（6）AGV 搬運(yùn)耗時(shí)僅與生產(chǎn)節(jié)點(diǎn)之間的距離、AGV 運(yùn)輸速度相關(guān)，不考慮工件在設(shè)備上的裝卸時(shí)間。

（7）AGV 在各節(jié)點(diǎn)之間搬運(yùn)路線的選擇上遵循最短路徑原則，各AGV 執(zhí)行搬運(yùn)任務(wù)過(guò)程中互不干擾。

參數(shù)設(shè)置

j,l待加工工件編號(hào)

m加工設(shè)備編號(hào)

M0原料池

s,k搬運(yùn)設(shè)備編號(hào)

h,q加工工序編號(hào)

H一個(gè)極大的數(shù)

pjh:工序h的加工工時(shí)

J: 待加工工件集合，J={J1,J2,···,Jn}

M: 加工設(shè)備集合，M={M1,M2,···,Mm}

R: AGV 集合，R={R1,R2,···,Rr}；

Oj: 任意工件j的工序集合，Oj={Oj1,Oj2,···,Ojk}

Tjh: 工件j任意工序Ojh完工轉(zhuǎn)移到緊后工序Oj(h+1)的搬運(yùn)任務(wù)

bjh: 工序Ojh的加工開(kāi)始時(shí)間

fjh: 工序Ojh的加工完成時(shí)間

βjh,s搬運(yùn)任務(wù)Tjh由AGV 設(shè)備s執(zhí)行則為1，否則為0

δjh,lq搬運(yùn)任務(wù)Tjh優(yōu)先比搬運(yùn)任務(wù)Tlq執(zhí)行則為1，否則為0

γjh,lq搬運(yùn)任務(wù)Tjh與搬運(yùn)任務(wù)Tlq均由同一臺(tái)AGV 執(zhí)行則為1，否則為0

本文所考慮的優(yōu)化目標(biāo)為最小化最大完成時(shí)間，記為Cmax。

模型的相關(guān)約束條件如上所示，式（2）定義了最大完成時(shí)間為所有工件都完工時(shí)最后一道搬運(yùn)工序的完工時(shí)間；式（3）和（4）表示工件在執(zhí)行加工過(guò)程中不可中斷；式（5）表示工件加工工序的開(kāi)工時(shí)間需要考慮前一道工序的轉(zhuǎn)運(yùn)時(shí)間；式（6）和（7）表示一道工序的運(yùn)輸操作需等待其加工操作完成；式（8）表示加工設(shè)備執(zhí)行任務(wù)的唯一性；式（9）為一臺(tái)設(shè)備同一時(shí)刻只能加工一個(gè)工件；式（10）表示一個(gè)工件同一時(shí)刻只能由一臺(tái)設(shè)備加工；式（11）表示搬運(yùn)任務(wù)只能由一臺(tái)AGV 執(zhí)行；式（12）～（16）表示搬運(yùn)任務(wù)的唯一性：一臺(tái)AGV 同一時(shí)刻只能搬運(yùn)一個(gè)工件，一個(gè)搬運(yùn)任務(wù)僅可由一臺(tái)AGV 服務(wù)。式（17）表示忽略空載/裝載運(yùn)輸?shù)臅r(shí)間偏差。

2 基于組合規(guī)則的AGV 聯(lián)合調(diào)度算法

作業(yè)車間AGV 聯(lián)合調(diào)度問(wèn)題可以解耦成AGV選擇與加工工序排序兩個(gè)強(qiáng)關(guān)聯(lián)的子決策，如圖2所示對(duì)兩個(gè)子問(wèn)題進(jìn)行問(wèn)題特征提取與分析，構(gòu)建適應(yīng)問(wèn)題特征的規(guī)則庫(kù)，通過(guò)決策耦合將兩類規(guī)則算法進(jìn)行規(guī)則重組，最終生成求解聯(lián)合調(diào)度問(wèn)題的組合規(guī)則集合。

圖2 聯(lián)合調(diào)度組合規(guī)則算法框架

2.1 規(guī)則算法設(shè)計(jì)

啟發(fā)式規(guī)則是將任務(wù)、資源的某種特征屬性作為準(zhǔn)則對(duì)工件加工優(yōu)先級(jí)順序、AGV 選擇優(yōu)先級(jí)順序進(jìn)行設(shè)定以快速生成一個(gè)合適的解決方案。先設(shè)計(jì)不同的工序排序規(guī)則（加工設(shè)備前隊(duì)列的優(yōu)先級(jí)設(shè)定）、AGV 選擇規(guī)則（待轉(zhuǎn)運(yùn)的工件選擇AGV 的優(yōu)先級(jí)），再將規(guī)則嵌入圖2 所示的算法框架生成組合規(guī)則算法。通過(guò)相關(guān)文獻(xiàn)調(diào)研[9-10,14]，本文對(duì)經(jīng)典AGV 選擇與工序排序規(guī)則在聯(lián)合調(diào)度問(wèn)題下作出適應(yīng)性改進(jìn)，最終擬采用的規(guī)則集合如表2 所示。

表2 啟發(fā)式規(guī)則匯總分類

2.2 組合規(guī)則算法生成

通過(guò)對(duì)問(wèn)題特征分析后，將表2 所設(shè)計(jì)的3 種AGV 選擇規(guī)則與4 種工序排序規(guī)則導(dǎo)入圖2 所構(gòu)建的組合規(guī)則算法生成框架，共生成12 個(gè)組合調(diào)度規(guī)則。12 個(gè)組合調(diào)度算法執(zhí)行流程的偽代碼如下所示。

基于組合規(guī)則的作業(yè)車間AGV 聯(lián)合調(diào)度算法

1：輸入：工件集合JobSet，總工序集合T_OperSet，已完工工序集合F_OperSet，AGV 數(shù)量Num_AGV

2：初始化AGV 執(zhí)行任務(wù)信息矩陣MA、加工設(shè)備釋放時(shí)間矩陣MR、待加工工件狀態(tài)矩陣MJ

3：for i=1 : length(T_OperSet)

4：檢索JobSet 中未完工的工件集合UF_JSet；

5：for j=1 : length(UF_JSet)

6：鎖定待轉(zhuǎn)運(yùn)工件的位置Trans_P；

7：for k=1 : Num_AGV

8：鎖定第k 臺(tái)AGV 的所在位置節(jié)點(diǎn)AGV_P，統(tǒng)計(jì)AGV 空載與滿載運(yùn)輸時(shí)間

9：end for

10：按照組合規(guī)則的AGV 選擇規(guī)則選擇執(zhí)行搬運(yùn)任務(wù)的AGV

11：確定加工工件搬運(yùn)的目標(biāo)節(jié)點(diǎn)，計(jì)算工序的最早開(kāi)工與最晚完工時(shí)間

12：end for

13：按照組合規(guī)則的工序排序規(guī)則確定已轉(zhuǎn)運(yùn)任務(wù)的加工優(yōu)先級(jí)，更新MA、MR、MJ

14：end for

3 實(shí)驗(yàn)設(shè)計(jì)及分析

3.1 仿真算例設(shè)計(jì)

為進(jìn)一步探索前文所生成算法的有效性與場(chǎng)景適應(yīng)性，設(shè)計(jì)生產(chǎn)特征差異化的算例對(duì)組合規(guī)則算法進(jìn)行對(duì)比分析。參考ümit Bilge,[15]等人的研究，在已知車間布局、軌道導(dǎo)向與加工工件信息等條件下進(jìn)行小規(guī)模問(wèn)題的案例設(shè)計(jì)，下圖3 所示為小規(guī)模測(cè)試場(chǎng)景所涉及的4 種車間布局圖(編號(hào)分別記為a/b/c/d)，包含了4 臺(tái)加工設(shè)備與一個(gè)中轉(zhuǎn)倉(cāng)。中、大規(guī)模測(cè)試場(chǎng)景的車間布局參考Ham A[16]，其包含的加工設(shè)備節(jié)點(diǎn)數(shù)量分別為11、16 個(gè)，因中、大規(guī)模問(wèn)題車間布局(編號(hào)記為e/f)同質(zhì)化程度比較高且過(guò)于復(fù)雜，此處不予展示。作業(yè)車間AGV 小車的數(shù)量為2 臺(tái)，在軌道定向的前提下勻速行駛。

圖3 小規(guī)模測(cè)試案例的車間布局圖

本文擬采用美國(guó)Gurobi Optimization 開(kāi)發(fā)的新一代優(yōu)化求解器Gurobi 和組合規(guī)則算法進(jìn)行求解。將組合規(guī)則算法解與Gurobi 解對(duì)比以衡量規(guī)則解與最優(yōu)解的優(yōu)度差?？紤]到實(shí)際生產(chǎn)對(duì)運(yùn)算時(shí)效性的需求，設(shè)定Gurobi 的求解時(shí)間上限為1 800 s。

本文所開(kāi)發(fā)的作業(yè)車間調(diào)度仿真模型、組合規(guī)則算法與Gurobi 求解環(huán)境均采用Matlab R2019b 編程實(shí)現(xiàn)，其運(yùn)行環(huán)境如下：計(jì)算機(jī)系統(tǒng)為Windows10，處理器為Intel? Core? i5-10200H @ 2.40GHz，RAM內(nèi)存為16.0GB。

3.2 實(shí)驗(yàn)研究?jī)?nèi)容

通過(guò)對(duì)AGV 聯(lián)合調(diào)度問(wèn)題的文獻(xiàn)調(diào)研總結(jié)，了解到對(duì)規(guī)則算法性能產(chǎn)生影響的實(shí)驗(yàn)因素有車間布局(g)，任務(wù)規(guī)模(s)，工序排序規(guī)則(o)，AGV選擇策略(h)，AGV 行駛速度(v)。如表3 所示為本實(shí)驗(yàn)所涉及影響因子的匯總：車間布局按照節(jié)點(diǎn)數(shù)量、軌道導(dǎo)向路徑區(qū)分共有6 種規(guī)模；任務(wù)規(guī)模分為5/6/20 三個(gè)數(shù)量級(jí)；工序排序規(guī)則與AGV 選擇規(guī)則按照2.1 小節(jié)所設(shè)計(jì)的維度分別有4 種工序排序與3 種AGV 選擇規(guī)則；最后小車行駛速度作為搬運(yùn)設(shè)備的關(guān)鍵參量設(shè)置了1 m/s 與2 m/s 兩種水平。本文共設(shè)計(jì)了50 個(gè)算例，按照加工設(shè)備/任務(wù)數(shù)量可以劃分為40 個(gè)小規(guī)模場(chǎng)景測(cè)試案例與10 個(gè)中大規(guī)模場(chǎng)景測(cè)試案例。本文的實(shí)驗(yàn)路線按照以下3 個(gè)步驟推進(jìn)：

表3 實(shí)驗(yàn)影響因素匯總

（1）精確法求解最優(yōu)解：借助所構(gòu)建的混合整數(shù)規(guī)劃模型進(jìn)行精確法求解，即在有限時(shí)間范圍內(nèi)，通過(guò)Gurobi 求解小規(guī)模問(wèn)題的最優(yōu)解，以此作為衡量組合規(guī)則算法有效性的標(biāo)桿。

（2）組合規(guī)則算法有效性驗(yàn)證：將不同AGV選擇與工序排序規(guī)則耦合作用于聯(lián)合調(diào)度決策以生成組合規(guī)則，將組合規(guī)則嵌入仿真模型運(yùn)行出規(guī)則解的Cmax值，比較不同組合規(guī)則與最優(yōu)解標(biāo)桿之間在優(yōu)化目標(biāo)上的性能差異。

（3）組合規(guī)則算法適應(yīng)性分析：評(píng)估12 種組合規(guī)則在中、大規(guī)模場(chǎng)景算例的性能，評(píng)價(jià)指標(biāo)包括優(yōu)化目標(biāo)Cmax，AGV 平均利用率、AGV 平均空載距離和總運(yùn)輸距離等4 個(gè)指標(biāo)。

3.3 結(jié)果分析

3.3.1 精確法求解結(jié)果與分析

由于精確法僅能求解小規(guī)模問(wèn)題，故采用加工節(jié)點(diǎn)數(shù)量為4 臺(tái)設(shè)備的40 組算例進(jìn)行Gurobi 求解。分別統(tǒng)計(jì)每組案例的優(yōu)化目標(biāo)Cmax值和CPU 運(yùn)算時(shí)間tcpu，表4 與表5 依次為AGV 行駛速度1m/s 與2m/s 下Gurobi 的運(yùn)算結(jié)果。

表4 為AGV 行駛速度為1 m/s 時(shí)，Gurobi 的精確解結(jié)果。同一個(gè)車間布局方案下，不同算例之間的Cmax值之間存在一定的差異，差異的根源來(lái)自于算例之間在任務(wù)規(guī)模與任務(wù)的工藝路徑差異；再比較相同任務(wù)信息下，不同布局方案下各算例最優(yōu)解在Cmax和求解時(shí)間上的差異，可以發(fā)現(xiàn)不同布局方案對(duì)最終結(jié)果存在一定影響，差異不僅體現(xiàn)在解的質(zhì)量上，在運(yùn)算耗時(shí)上更為突出。因?yàn)樵O(shè)定了求解時(shí)間上限的緣故，所以在某些算例下Gurobi 只能求解出近似解。

表4 小規(guī)模問(wèn)題Gurobi 精確解結(jié)果(v=1 m/s)

表5 是設(shè)置AGV 行駛速度為2 m/s 的Gurobi 運(yùn)算結(jié)果，跟AGV 低速運(yùn)行結(jié)果的差異主要體現(xiàn)在Cmax值在各個(gè)算例下都有不同程度的提升，因?yàn)檫\(yùn)輸能力的提升使得各待加工工件的流轉(zhuǎn)周期得到一定程度的縮短，進(jìn)而減少了Cmax值；另外一方面，各算例在Gurobi 的運(yùn)算時(shí)間消耗不同程度地降低，且給定時(shí)間內(nèi)無(wú)法求解到最優(yōu)解（tcpu=1 800 s）的算例相對(duì)有所減少。

表5 小規(guī)模問(wèn)題Gurobi 精確解結(jié)果(v=2 m/s)

3.3.2 組合規(guī)則算法有效性驗(yàn)證

為評(píng)價(jià)組合算法的有效性，將12 種組合規(guī)則解與Gurobi 最優(yōu)解在40 個(gè)小規(guī)模問(wèn)題算例下進(jìn)行比較，并通過(guò)設(shè)置不同AGV 行駛速度以驗(yàn)證組合規(guī)則解與最優(yōu)解之間的差異，有效性實(shí)驗(yàn)結(jié)果如圖4 與圖5 所示。

圖4 各算法優(yōu)化目標(biāo)比較(v=1 m/s)

圖5 各算法優(yōu)化目標(biāo)比較(v=2 m/s)

如圖4 所示，AGV 行駛速度為1m/s 時(shí)，不同組合規(guī)則相比Gurobi 在求解質(zhì)量上存在不同程度的差異。從布局方案的角度進(jìn)行觀察：在布局方案a、b下，性能最優(yōu)的組合規(guī)則各在4 個(gè)算例下優(yōu)于Gurobi 求出的近優(yōu)解，因?yàn)樵谶@4 個(gè)算例下Gurobi都沒(méi)能在給定的時(shí)間內(nèi)求解出最優(yōu)解；布局方案c、d 下，表現(xiàn)最優(yōu)的組合規(guī)則也各在6 個(gè)算例下性能發(fā)揮勝于Gurobi 求出的近優(yōu)解。另外，觀察組合規(guī)則解與最優(yōu)解的差距，最大的偏離程度（布局方案c 的算例#5）也僅為34%，考慮到單個(gè)組合規(guī)則運(yùn)算時(shí)間消耗控制在毫秒級(jí)，雖然組合規(guī)則最優(yōu)方案要在所有組合規(guī)則都運(yùn)算完才能選出，但如表6所示，所有組合規(guī)則總耗時(shí)也不超過(guò)0.1 s。相比Gurobi 高耗時(shí)下的有限性能提升，組合規(guī)則算法的求解質(zhì)量是完全可以接受的。

表6 小規(guī)模問(wèn)題下組合規(guī)則算法運(yùn)算時(shí)間

圖5 為AGV 行駛速度為2 m/s 時(shí)優(yōu)化算法與組合規(guī)則算法的優(yōu)化目標(biāo)差異。通過(guò)觀察分析可以總結(jié)出，相比AGV 行駛速度設(shè)定為1m/s 時(shí)，AGV 以較高速度行駛的場(chǎng)景下組合規(guī)則算法僅能在少數(shù)算例上貼近或者勝過(guò)Gurobi 的解質(zhì)量：布局方案為a、c、d 時(shí)，組合規(guī)則僅在一個(gè)算例下勝過(guò)Gurobi；布局方案為b 時(shí)，有兩個(gè)算例等于或者勝過(guò)Gurobi，其中布局方案b 在算例#6 下組合規(guī)則(JAT+EFR)也達(dá)到了Gurobi 求解的最優(yōu)解。

綜上所述，AGV 在行駛速度設(shè)置較低時(shí)，組合規(guī)則算法能以極短的運(yùn)算時(shí)間得到性能接近Gurobi的近優(yōu)解。AGV 行駛速度設(shè)置變高，Gurobi 更容易求得最優(yōu)解，但組合規(guī)則算法性能發(fā)揮依舊可觀。

3.3.3 組合規(guī)則算法適應(yīng)性分析

經(jīng)過(guò)預(yù)實(shí)驗(yàn)測(cè)試，在給定時(shí)間內(nèi)Gurobi 求解器無(wú)法求得中、大規(guī)模問(wèn)題（布局方案e/f）的可行解，故此節(jié)將進(jìn)一步評(píng)估規(guī)則算法在中、大規(guī)模問(wèn)題算例上的適應(yīng)性發(fā)揮。算例#1-#5 為中等規(guī)模算例（加工設(shè)備11 臺(tái)，20 個(gè)待加工任務(wù)），算例#6-#10 為大規(guī)模算例（加工設(shè)備16 臺(tái)，20 個(gè)待加工任務(wù)）。

表7 為中大規(guī)模下組合規(guī)則算法的運(yùn)算時(shí)間，跟前文小規(guī)模運(yùn)算時(shí)間統(tǒng)計(jì)方法類似，運(yùn)算時(shí)間為所有組合規(guī)則在某一個(gè)案例下運(yùn)行的總耗時(shí)，通過(guò)觀察對(duì)比發(fā)現(xiàn)，中大規(guī)模下組合規(guī)則的運(yùn)算時(shí)間相比小規(guī)模問(wèn)題有明顯增加，但最長(zhǎng)運(yùn)行耗時(shí)的算例仍未超出1 s。在調(diào)度方案的性能評(píng)價(jià)指標(biāo)方面，除去優(yōu)化目標(biāo)Cmax值以外，還引入AGV 平均利用率、平均空載距離和總運(yùn)輸距離3 個(gè)觀察指標(biāo)來(lái)輔助分析組合規(guī)則的內(nèi)在特性。

表7 中大規(guī)模問(wèn)題下組合規(guī)則算法運(yùn)算時(shí)間

圖6 為AGV 行駛速度1 m/s 下，各組合規(guī)則算法在中、大規(guī)模算例下的表現(xiàn)性能。先從優(yōu)化目標(biāo)Cmax值分析，圖6a 中基于不同工件排序規(guī)則的組合規(guī)則算法出現(xiàn)多級(jí)分化的趨勢(shì)，JAT 和JEO類組合規(guī)則性能表現(xiàn)要完全勝過(guò)MER、JFO 類規(guī)則。通過(guò)分析AGV 利用率以解析優(yōu)化目標(biāo)的差異，不難發(fā)現(xiàn)JFO 類規(guī)則的AGV 平均利用率最為低下，說(shuō)明AGV 小車在JFO 類規(guī)則下頻繁的無(wú)效移動(dòng)造成了較長(zhǎng)的空載距離，圖6c、6d 的觀察指標(biāo)進(jìn)一步印證了這一結(jié)論。

圖6 組合規(guī)則算法大規(guī)模算例適應(yīng)性實(shí)驗(yàn)結(jié)果（v=1 m/s）

圖7 為AGV 行駛速度設(shè)定為2 m/s 時(shí)，各規(guī)則算法的性能比較。通過(guò)比較圖6a 與圖7a 可以發(fā)現(xiàn)所有規(guī)則算法在Cmax指標(biāo)上都有不同程度的性能提升，JAT、JEO 類規(guī)則相比MER、JFO 類規(guī)則在Cmax值上的差距有略微縮小。在AGV 平均利用率指標(biāo)上，由于搬運(yùn)效率的提升，造成了AGV 小車的有效運(yùn)輸時(shí)間減少，故AGV 利用率有所下降，且AGV 小車的平均空載距離也有所上升。最后，不同行駛速度設(shè)置下，各組合規(guī)則在AGV 總運(yùn)輸距離指標(biāo)上沒(méi)有顯著變化趨勢(shì)。

圖7 組合規(guī)則算法大規(guī)模算例適應(yīng)性實(shí)驗(yàn)結(jié)果(v=2 m/s)

綜上所述，工序排序規(guī)則在Cmax值上對(duì)組合規(guī)則的影響較為顯著，且JAT、JEO 類規(guī)則在AGV較低速度行駛時(shí)相比其他工序排序規(guī)則有明顯優(yōu)勢(shì)。

4 結(jié)語(yǔ)

本文以具有AGV 儲(chǔ)運(yùn)系統(tǒng)的作業(yè)車間聯(lián)合調(diào)度為研究對(duì)象，首先以最小化最大完成時(shí)間為優(yōu)化目標(biāo)構(gòu)建了聯(lián)合調(diào)度的混合整數(shù)規(guī)劃模型，然后分別從基于Gurobi 求解器的精確法與基于組合規(guī)則的近似算法兩套思路對(duì)問(wèn)題求解，最后，設(shè)計(jì)了具有不同布局方案、任務(wù)規(guī)模等生產(chǎn)特征的算例對(duì)所涉及的組合規(guī)則生成算法框架進(jìn)行有效性驗(yàn)證，實(shí)驗(yàn)結(jié)果表明：

（1）小規(guī)模問(wèn)題算例下，Gurobi 精確解普遍優(yōu)于組合規(guī)則算法解，但在AGV 速度較低時(shí)，組合規(guī)則算法與Gurobi 的解差異縮小。

（2）從算法的求解時(shí)間來(lái)看，Gurobi 算法無(wú)法在可觀時(shí)間內(nèi)求解大規(guī)模問(wèn)題精確解，甚至在小規(guī)模問(wèn)題上也要耗費(fèi)很多運(yùn)算時(shí)間，相比之下組合規(guī)則算法秒級(jí)的運(yùn)算時(shí)間具有很大優(yōu)勢(shì)。

（3）組合規(guī)則算法在不同布局方案下的Cmax值差異相對(duì)明顯，工序排序規(guī)則的選擇很大程度影響組合規(guī)則的性能表現(xiàn)。

未來(lái)研究可以考慮更多實(shí)際生產(chǎn)的動(dòng)態(tài)因素，例如工時(shí)不確定、AGV 故障等。引入交貨期類目標(biāo)做進(jìn)一步場(chǎng)景拓展也是一個(gè)潛在方向。