基于組合規則的作業車間AGV 聯合調度優化＊

鐘宏揚 彭乘風 廖 勇 李 翔

（①廣東工業大學廣東省計算機集成制造重點實驗室，廣東 廣州 510006；②湘南學院物理與電子電氣工程學院，湖南 郴州 423000）

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

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

表1 作業車間環境下AGV 聯合調度文獻

本文對研究問題進行結構化分析后，構建數學模型并設計一套組合規則算法框架，通過導入分屬不同子決策的規則以生成大量組合規則算法。鑒于組合規則的耦合性能受到任務和資源等多方面因素的影響，設計差異化的算例實驗，以評估不同組合規則受實驗參量敏感程度，進而驗證算法的有效性與穩定性。

1 研究問題及數學模型

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

圖1 運輸能力有限的作業車間運行示意圖

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

（2）所有加工/搬運設備在零時刻都處在空閑狀態，且設備在生產過程中一直可用，不考慮各類機器故障。

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

（4）同一臺加工設備在同一時刻只可以加工一個工件，且工序一旦開始加工就不可中斷。

（5）同一臺搬運設備在同一時刻只能搬運一個工件，且搬運過程不可中斷。

（6）AGV 搬運耗時僅與生產節點之間的距離、AGV 運輸速度相關，不考慮工件在設備上的裝卸時間。

（7）AGV 在各節點之間搬運路線的選擇上遵循最短路徑原則，各AGV 執行搬運任務過程中互不干擾。

參數設置

j,l待加工工件編號

m加工設備編號

M0原料池

s,k搬運設備編號

h,q加工工序編號

H一個極大的數

pjh:工序h的加工工時

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

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

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

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

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

bjh: 工序Ojh的加工開始時間

fjh: 工序Ojh的加工完成時間

βjh,s搬運任務Tjh由AGV 設備s執行則為1，否則為0

δjh,lq搬運任務Tjh優先比搬運任務Tlq執行則為1，否則為0

γjh,lq搬運任務Tjh與搬運任務Tlq均由同一臺AGV 執行則為1，否則為0

本文所考慮的優化目標為最小化最大完成時間，記為Cmax。

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

2 基于組合規則的AGV 聯合調度算法

作業車間AGV 聯合調度問題可以解耦成AGV選擇與加工工序排序兩個強關聯的子決策，如圖2所示對兩個子問題進行問題特征提取與分析，構建適應問題特征的規則庫，通過決策耦合將兩類規則算法進行規則重組，最終生成求解聯合調度問題的組合規則集合。

圖2 聯合調度組合規則算法框架

2.1 規則算法設計

啟發式規則是將任務、資源的某種特征屬性作為準則對工件加工優先級順序、AGV 選擇優先級順序進行設定以快速生成一個合適的解決方案。先設計不同的工序排序規則（加工設備前隊列的優先級設定）、AGV 選擇規則（待轉運的工件選擇AGV 的優先級），再將規則嵌入圖2 所示的算法框架生成組合規則算法。通過相關文獻調研[9-10,14]，本文對經典AGV 選擇與工序排序規則在聯合調度問題下作出適應性改進，最終擬采用的規則集合如表2 所示。

表2 啟發式規則匯總分類

2.2 組合規則算法生成

通過對問題特征分析后，將表2 所設計的3 種AGV 選擇規則與4 種工序排序規則導入圖2 所構建的組合規則算法生成框架，共生成12 個組合調度規則。12 個組合調度算法執行流程的偽代碼如下所示。

基于組合規則的作業車間AGV 聯合調度算法

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

2：初始化AGV 執行任務信息矩陣MA、加工設備釋放時間矩陣MR、待加工工件狀態矩陣MJ

3：for i=1 : length(T_OperSet)

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

5：for j=1 : length(UF_JSet)

6：鎖定待轉運工件的位置Trans_P；

7：for k=1 : Num_AGV

8：鎖定第k 臺AGV 的所在位置節點AGV_P，統計AGV 空載與滿載運輸時間

9：end for

10：按照組合規則的AGV 選擇規則選擇執行搬運任務的AGV

11：確定加工工件搬運的目標節點，計算工序的最早開工與最晚完工時間

12：end for

13：按照組合規則的工序排序規則確定已轉運任務的加工優先級，更新MA、MR、MJ

14：end for

3 實驗設計及分析

3.1 仿真算例設計

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

圖3 小規模測試案例的車間布局圖

本文擬采用美國Gurobi Optimization 開發的新一代優化求解器Gurobi 和組合規則算法進行求解。將組合規則算法解與Gurobi 解對比以衡量規則解與最優解的優度差。考慮到實際生產對運算時效性的需求，設定Gurobi 的求解時間上限為1 800 s。

本文所開發的作業車間調度仿真模型、組合規則算法與Gurobi 求解環境均采用Matlab R2019b 編程實現，其運行環境如下：計算機系統為Windows10，處理器為Intel? Core? i5-10200H @ 2.40GHz，RAM內存為16.0GB。

3.2 實驗研究內容

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

表3 實驗影響因素匯總

（1）精確法求解最優解：借助所構建的混合整數規劃模型進行精確法求解，即在有限時間范圍內，通過Gurobi 求解小規模問題的最優解，以此作為衡量組合規則算法有效性的標桿。

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

（3）組合規則算法適應性分析：評估12 種組合規則在中、大規模場景算例的性能，評價指標包括優化目標Cmax，AGV 平均利用率、AGV 平均空載距離和總運輸距離等4 個指標。

3.3 結果分析

3.3.1 精確法求解結果與分析

由于精確法僅能求解小規模問題，故采用加工節點數量為4 臺設備的40 組算例進行Gurobi 求解。分別統計每組案例的優化目標Cmax值和CPU 運算時間tcpu，表4 與表5 依次為AGV 行駛速度1m/s 與2m/s 下Gurobi 的運算結果。

表4 為AGV 行駛速度為1 m/s 時，Gurobi 的精確解結果。同一個車間布局方案下，不同算例之間的Cmax值之間存在一定的差異，差異的根源來自于算例之間在任務規模與任務的工藝路徑差異；再比較相同任務信息下，不同布局方案下各算例最優解在Cmax和求解時間上的差異，可以發現不同布局方案對最終結果存在一定影響，差異不僅體現在解的質量上，在運算耗時上更為突出。因為設定了求解時間上限的緣故，所以在某些算例下Gurobi 只能求解出近似解。

表4 小規模問題Gurobi 精確解結果(v=1 m/s)

表5 是設置AGV 行駛速度為2 m/s 的Gurobi 運算結果，跟AGV 低速運行結果的差異主要體現在Cmax值在各個算例下都有不同程度的提升，因為運輸能力的提升使得各待加工工件的流轉周期得到一定程度的縮短，進而減少了Cmax值；另外一方面，各算例在Gurobi 的運算時間消耗不同程度地降低，且給定時間內無法求解到最優解（tcpu=1 800 s）的算例相對有所減少。

表5 小規模問題Gurobi 精確解結果(v=2 m/s)

3.3.2 組合規則算法有效性驗證

為評價組合算法的有效性，將12 種組合規則解與Gurobi 最優解在40 個小規模問題算例下進行比較，并通過設置不同AGV 行駛速度以驗證組合規則解與最優解之間的差異，有效性實驗結果如圖4 與圖5 所示。

圖4 各算法優化目標比較(v=1 m/s)

圖5 各算法優化目標比較(v=2 m/s)

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

表6 小規模問題下組合規則算法運算時間

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

綜上所述，AGV 在行駛速度設置較低時，組合規則算法能以極短的運算時間得到性能接近Gurobi的近優解。AGV 行駛速度設置變高，Gurobi 更容易求得最優解，但組合規則算法性能發揮依舊可觀。

3.3.3 組合規則算法適應性分析

經過預實驗測試，在給定時間內Gurobi 求解器無法求得中、大規模問題（布局方案e/f）的可行解，故此節將進一步評估規則算法在中、大規模問題算例上的適應性發揮。算例#1-#5 為中等規模算例（加工設備11 臺，20 個待加工任務），算例#6-#10 為大規模算例（加工設備16 臺，20 個待加工任務）。

表7 為中大規模下組合規則算法的運算時間，跟前文小規模運算時間統計方法類似，運算時間為所有組合規則在某一個案例下運行的總耗時，通過觀察對比發現，中大規模下組合規則的運算時間相比小規模問題有明顯增加，但最長運行耗時的算例仍未超出1 s。在調度方案的性能評價指標方面，除去優化目標Cmax值以外，還引入AGV 平均利用率、平均空載距離和總運輸距離3 個觀察指標來輔助分析組合規則的內在特性。

表7 中大規模問題下組合規則算法運算時間

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

圖6 組合規則算法大規模算例適應性實驗結果（v=1 m/s）

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

圖7 組合規則算法大規模算例適應性實驗結果(v=2 m/s)

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

4 結語

本文以具有AGV 儲運系統的作業車間聯合調度為研究對象，首先以最小化最大完成時間為優化目標構建了聯合調度的混合整數規劃模型，然后分別從基于Gurobi 求解器的精確法與基于組合規則的近似算法兩套思路對問題求解，最后，設計了具有不同布局方案、任務規模等生產特征的算例對所涉及的組合規則生成算法框架進行有效性驗證，實驗結果表明：

（1）小規模問題算例下，Gurobi 精確解普遍優于組合規則算法解，但在AGV 速度較低時，組合規則算法與Gurobi 的解差異縮小。

（2）從算法的求解時間來看，Gurobi 算法無法在可觀時間內求解大規模問題精確解，甚至在小規模問題上也要耗費很多運算時間，相比之下組合規則算法秒級的運算時間具有很大優勢。

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

未來研究可以考慮更多實際生產的動態因素，例如工時不確定、AGV 故障等。引入交貨期類目標做進一步場景拓展也是一個潛在方向。