基于軌跡映射模型的天車多目標調度方法

周炳海 廖秀梅

（同濟大學 機械與能源工程學院，上海201804）

摘? ?要：為有效解決生產過程中的多天車調度問題，在統籌考慮天車任務初始態和時空約束等特征的基礎上，提出一種全新的天車軌跡映射模型.結合傳統差分進化方法，將庫位分配規則和天車分配算法融合到調度算法的每一次迭代過程中以指導算法尋優.以最小化入庫訂單延遲成本和最小化出庫訂單等待成本作為評價指標，設計仿真試驗并與經典多目標優化算法進行對比，驗證了算法是有效可行的，進一步的數值試驗表明了合理的調度規則可以有效提高天車調度性能.

關鍵詞：天車軌跡映射;時空約束;多目標;啟發式算法

中圖分類號：TP391? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標志碼：A

Multi-objective Scheduling Method for Workshop Cranes Based

on Projection Model of Trajectories

ZHOU Binghai，LIAO Xiumei

（School of Mechanical and Energy Engineering，Tongji University，Shanghai 201804，China）

Abstract：To efficiently solve the multi-crane scheduling problem during the production process，a novel projection model of trajectories the proposed with the consideration of initial states of tasks and space-time constraints. Based on the differential evolution algorithm，stock allocation rules and a crane allocation algorithm were combined to guide the optimization process in each iteration. Taking the minimization of delay cost and waiting cost as the evaluation indices，the simulation experiment was designed and compared with the classical multi-objective optimization algorithms. The results show that the algorithm is effective and feasible. Further numerical experiments indicate that reasonable scheduling rules can effectively improve the crane scheduling performance.

Key words：projection of crane trajectories;space-time constraints;multi-objectives;heuristic algorithms

隨著制造業物流系統的日趨完善，車間天車調度問題（crane scheduling in workshop，CSW）引起了廣泛的關注.CSW屬于典型的NP難問題，具有多機多任務特點，如何科學有效地提升天車調度水平已成為生產過程中亟待解決的問題[1-2].

目前，已有諸多學者對CSW問題進行了研究.針對天車調度過程中的路徑沖突問題，文獻[3]考慮將車間分為多個平行區域，每臺天車只負責其所在區域內的搬運任務.文獻[4]分析了調度過程中天車的不可行路徑，通過建立混合整數規劃模型解決路徑沖突.文獻[5]創新性地提出了天車軌跡映射模型以減少決策變量，并通過移除決策樹中次優狀態的方法完成調度.文獻[6]從排隊論角度分析了車間天車調度問題，為提高天車利用率、減少浪費提供了新思路.

在天車調度過程中，考慮入庫和出庫訂單的聯合調度可以有效提升天車利用率.文獻[7]針對卷鋼存儲的特殊性，對卷鋼出庫過程的天車調度展開研究.文獻[8]在卷鋼出庫問題的基礎上，考慮了卷鋼入庫的聯合調度，分別設計了時空網絡流方法和近似動態規劃算法求解中小規模問題和大規模問題，但針對的是單天車調度.鮮有文獻考慮入庫和出庫訂單聯合調度背景下的CSW決策問題.

本文在考慮天車任務初始態和時空約束的基礎上，對聯合優化入庫、出庫訂單的車間多天車調度問題進行研究，提出天車多目標調度方法，并以入庫訂單延遲成本和出庫訂單等待成本為指標，評價調度性能.

1? ?問題描述

1.1? ?天車調度問題

天車作為連接上、下游工序之間的橋梁，其車間內布局如圖1所示.當上游工序M加工完成后，天車將半成品從卸料區送入庫位進行存儲，當下游工序N準備加工時，天車將半成品從庫位搬運至上料區等待加工.

為有效描述天車調度問題，做如下基本假設：1）訂單i包含兩個任務，天車將i從起始庫位（x i1，

y i1）起吊的操作為任務i1，將其運送到目標庫位（x i2，

y i2）的操作為任務i2;2）天車集合為C，其編號從左至右依次為：1，2，…，K;3）沿作業跨方向，相鄰兩天車的安全距離為Δd;4）天車滿載時沿x軸和y軸的速度分別為vx， f和vy， f，空載時為vx，e和vy，e;5）天車移動滿足切比雪夫距離，若大車沿作業跨方向以速度vx前后運動，小車以速度vy左右運動，則天車運輸i的時間為t = max{x i2-x i1/vx，y i1-y i2/vy};6）吊運任務必須起吊至安全高度后才能運輸，運輸必須停止才能將吊運任務放下，起吊和放下所需時間分別為δ i1和δ i2;7）入庫訂單Φ和出庫訂單Ω同時生成;8）產品按照庫位進行存儲，所有庫位均可被任一天車檢索，庫位最多可堆垛l層，存放于出庫訂單之上的產品為倒垛訂單;9）每臺天車每次只能執行一個任務;10）不考慮天車的失效和設備維護.

為方便描述，定義符號如下：Τ為所有訂單集合;αi為訂單i的單位等待成本，其中i∈Ω;βi為訂單i的單位延遲成本，其中i∈Φ;z （X，Y）（t）為庫位（X，Y）在時刻t的層高.決策變量：si 為任務i的開始時間;ai代表執行任務i的天車編號;xk（t）和yk（t）分別代表天車k在時刻t時x方向和y方向上的位置.

由于訂單庫位的存儲特性，任意訂單i和j之間均存在兩種不同的存儲狀態，分別是：

i<

i→j：i和j在相同庫位且i的存儲位在j之上.

根據庫位存儲特性，下層存儲位訂單必須在上層存儲位訂單起吊完成之后才能開始，即需滿足：

（x i1，y i1） ≠ （x j1，y j1），？坌i<

根據假設2）～假設6），天車需滿足軌跡約束，包括：任意兩臺天車之間的安全距離約束，天車x和y方向上的速度約束，天車執行任務時的位置約束，以及變量xk（t），yk（t）的取值范圍約束，即需滿足：

xk′（t）-xk（t）≥（k′-k）·Δd，？坌k′，k∈C，k′>k

xk（t）-vxΔt≤xk（t+Δt）≤xk（t）+vxΔt，

？坌t，Δt≥0，vx∈{vx， f，vx，e}

yk（t）-vyΔt≤yk（t+Δt）≤yk（t）+vyΔt，

？坌t，Δt≥0，vy∈{vy， f，vy，e}

（x ai（t），y ai（t））=（xi，yi），？坌t∈[si，si + δi]，i∈T，ai∈C

xk（t），yk（t）∈R（2）

根據假設7）、假設8），任意時刻的庫位層高均不能超過其規定層高，即需滿足：

調度目標由兩部分組成，g（s i1）為最小化入庫訂單延遲成本，f（s i2）為最小化出庫訂單等待成本.

天車軌跡映射模型

天車的軌跡映射模型由Peterson等人[5]于2014年首次提出，其基本思想是變量之間的等效轉換.通過研究約束條件與si和ai之間的映射關系，實現變量xk（t）和yk（t）的等效消除，從而減少決策變量.

在本文中，由于天車滿載和空載時速度不同，導致天車在執行不同任務時的初始狀態不一，同時由于訂單上下堆垛的存儲特性，使得調度問題兼具時空復雜性，所以天車軌跡映射模型不僅需要考慮前后兩個任務之間的關系，還需考慮任務初始態和時空約束.

給定任意兩個有時空關系的訂單i和j，共生成4個任務：i1，i2，和j1，j2.天車執行任務時將產生4種任務關系，分別為：

1）i1和 i2

（14）

這里，i1和i2為同一臺天車先后執行的兩個任務.其中，式（6）、式（7）、式（9）、式（12）確保當兩個任務由同一臺天車執行時，天車執行完第一個任務后有足夠的時間執行第二個任務;式（8）、式（10）、式（13）表示當兩個任務不能同時完成時，一臺天車必須等待另一臺天車任務完成后才可以執行任務;式（11）、式（14）表示庫位相同時前后兩任務的時間約束.

根據天車和庫位狀態以及任務的開始時間，對式（6）～式（14）進行整理，得

s i1≥max{B1i1（j1），B2i1（j2）}，？坌j

式中：

x{B1i2（i1），B2i2（j1），B3i2（j2）}，？坌j

式中：

其中，BNi（j），N = 1，2，3表示任務i在任務j之

后開始，（i | j）x > 0表示xi+（aj-ai）·Δd-xj > 0.

由此，通過建立天車軌跡映射模型，調度問題的約束條件可轉化為式（3）、式（15）、式（16），決策變量減少為：任務i的開始時間si和執行任務i的天車ai.

2? ?算法構建

本文研究的車間天車調度需解決3個子問題：1）各訂單的執行序列;2）各訂單的天車分配;3）入庫訂單的庫位分配.該問題屬于典型的組合優化難題，用傳統解析數學方法無法對其有效求解.差分進化（Differential Evolution，DE）是一種過程簡單、受控參數少和魯棒性強的全局優化算法，與其他進化算法相比，DE在解決復雜全局優化問題時的性能更加優秀，目前已廣泛應用于各類調度問題[9-10].本文在構建天車軌跡映射模型的基礎上，以DE為框架，提出了基于泛化反向學習的差分進化算法，并設計天車分配算法和相應的庫位分配規則以指導算法尋優.

2.1? ?庫位分配規則

庫位分配規則在式（15）、式（16）的基礎上，以天車路徑不沖突和負重移動距離最短為原則，可在調度過程中解決子問題3）.為方便描述，作如下定義：

定義1? ?中心搜尋規則（center search rule，CS）.記訂單當前所在庫位為（X，Y），CS規則為先固定X列，令 i=1，搜尋庫位{（X，Y-i），（X，Y+i）}，選擇可用空間大的庫位作為訂單分配的位置.若無可用空間，則令i=i+1，繼續搜尋直至X列搜尋完畢.若當前X列均無可用空間，則按同樣的方法搜尋X+1列和 X-1列，直至找到可用空間為止.

定義2? ?中心向右搜尋規則（center to right search rule，CTR）.基本步驟與CS相同，當X列搜尋完畢后，CTR只搜尋X+1列，直至找到可用空間.

定義3? ?中心向左搜尋規則（center to left? search rule，CTL）.基本步驟與CS相同，當X列搜尋完畢后，CTL只搜尋X-1列，直至找到可用空間.

假設種群規模為NP，基因數為nVar，當前庫位為S（X，Y），其基本步驟為：

1） for p=1 ∶ NP

2） for k=1 ∶ 2*nVar

3） ? if k∈{i2}，i2∈T ＼ Ω

4） ? ? 記第j個任務分配的天車為aj;

5） ? ? 記aj的前置任務為i;

6） ? ? if? ?ai > aj∧xj - xi< （ai - aj）·d

7） ? ? S（X，Y） = （xi - （ai - aj）·d，yj）;

8） ? ? ? 根據CTL為j分配庫位;

9） ? ? ?else if? ai < aj∧xj - xi< （aj - ai）·d

10） ? ? ? ? ?S（X，Y） = （xi + （aj - ai）·d，yj）;

11） ? ? ? ? ?根據CTR為j分配庫位;

12） ? ? ?else

13） ? ? ?S（X，Y） = （xj，yj）;

14） ? ? ? ? 根據CS為j分配庫位;

15） ? ? ?end if

16） ? ? end if

17） ? end for

18） end for

2.2? ?天車分配算法

天車分配算法可在較短的時間內解決子問題2），并得到較為優質的天車分配方案.基本步驟為：

步驟1? ?為平衡各天車間的任務負載，按照天車編號，將K臺天車按照1，2，…，K進行循環升序排列，直至排列總數達到N.

步驟2? ?取序列中的第一臺天車成對進行排列.

步驟3? ?令i=2，將序列中第i臺天車成對插入到前面i×（i+1）/2個可能的位置，結合庫位分配規則為入庫和倒垛訂單分配庫位，利用快速非支配排序取目標值較優的排列作為新的排列.

步驟4? ?令i=i+1，重復步驟3，直至所有天車分配完畢.

2.3? ?基于泛化反向學習的差分進化算法

泛化反向學習（Generalized Opposition Based Learning，GOBL）指的是在種群的初始化階段和代跳躍階段使用GOBL機制生成變換種群，對于種群 PG，其變換種群GOPr，j，G為：

GOPr，j，G = k（aj+bj）-Pr，j，G，if GOPr，j，G∈[aj，bj]rand（aj，bj），? otherwise

式中：k = rand（0，1）;Pr，j，G∈[aj，bj].基于GOBL的差分進化在每一次迭代中融合庫位分配規則和天車分配算法以指導尋優進程.

步驟1? ?編碼.采用雙層編碼機制，如圖2所示.第一層編碼中，訂單總數為N，每個訂單的第一個位置為訂單編號，第二個位置為隨機實數.所有隨機實數從小到大排列，決定了訂單的執行序列.第二層編碼為天車編號，編碼長度為2N，代表2N個任務（對應N個訂單）分配的天車.

上下層編碼的對應關系為：從下層編碼開始，第一個天車編號對應第一個訂單的第一個任務，第二個天車編號若與第一個相同，則執行上層編碼第一個訂單的第二個任務，否則執行第二個訂單的第一個任務，依此類推.

步驟2? ?初始化.1）針對上層種群，采用隨機生成的方法，為每個訂單分配一個隨機實數，并將其從小到大排列，產生一個初始目標向量.針對下層種群，①令i=1，生成[1，K]之間的隨機整數，填入位置i;②令i = i+1，重復步驟①，直至i = 2N.上下層目標向量共同構成種群P0.2）采用GOBL機制生成P0的變換種群GOP0;3）結合庫位分配規則，為P0和GOP0分配庫位;4）同時評價P0和GOP0，利用快速非支配排序選擇最優的NP個個體組成新的種群P0′，將P0′作為初始種群.

步驟3? ?變異.傳統DE算法的變異率F一般為固定實數，以對差分量進行縮小和放大控制.F過大，算法近似隨機搜索，最優解精度降低;F過小，種群多樣性降低，算法易早熟收斂.故本文提出自適應變異算子F1和學習算子F2進行改善.在算法初期，F1具有較大值，有利于保持個體多樣性，隨著算法的推進，F1逐步減小，可以增加搜索到全局最優解的概率.F2則根據歷代的狀態調節數值大小，學習訂單在前幾代中的排序.根據文獻[11]的設計規則，得：

F2 = sin（Δkj/Δkmaxj? ? ·π）

式中：F0為縮放因子;Gm為外層最大進化代數;G為當前外層代數;Δkj為訂單j在第G代和第G-1代的位置差;Δkmaxj? ? 為訂單j在歷代進化中的最大位置差.

變異機制為：

vr，j，G+1=xr，j，G+F1（xbest，j，G-xr，j，G）+F2（x r1，j，G-x r2，j，G）

式中：xr，j，G，xbest，j，G，x r1，j，G，x r2，j，G分別表示第G代中個體r，best，r1，r2第j個訂單的基因，r≠r1≠r2.

步驟4? ?交叉.對父代種群PG中的個體xr，G及變異的中間體vr，G+1進行個體間交叉操作，得到子代種群PG+1，用公式表示為：

ur，j，G+1=vr，j，G+1，if rand（j）≤CR or j = rd（j）xr，j，G，? otherwise

式中：CR為交叉因子;rand（j）為評價訂單j時產生的隨機數;rd（j）為隨機選擇的整數.

步驟5? ?結合天車分配算法和庫位分配規則為交叉得到的個體分配天車和庫位.同時，令P = PG + PG+1，從而得到待評價種群P.

步驟6? ?種群代跳躍.在種群代跳躍階段，每次

均需生成一個0到1之間的隨機數rand（0，1）.若

rand（0，1）

步驟7? ?結合天車分配算法和庫位分配規則，為變換種群GOPG+1中的每個個體分配天車和庫位，并更新待評價種群P = P ∪GOPG+1.

步驟8? ?選擇.根據Pareto非支配排序和擁擠

距離排序選擇種群P中最優的NP個個體進入下

一代.

算法流程圖如圖3所示.

3? ?仿真試驗分析

3.1? ?參數分析

本試驗在基于Windows 10操作系統的Core i5/2.5GHz內存4 GB的計算機上進行.

由于此問題的真實帕累托前沿很難得到，本文在進行試驗時采用以下方法獲得近似帕累托前沿：算法獨立運行多次后記錄每次的帕累托解集，從所有帕累托前沿中獲得新的帕累托解作為近似前沿.試驗參數按照文獻[11-13]中的設計規則，選取不同的參數組合進行多次試驗.當設置種群規模nPop = 50，迭代次數G = 3 000，種群代跳躍概率J = 0.3，縮放因子F0 = 0.5，交叉概率CR = 0.6，最大與最小允許變異的值mumax、mumin分別為4和0時，算法以較高質量求解.

為測試天車分配算法以及庫位分配規則在求解問題中的表現，設計未使用天車分配算法、未使用庫位分配規則的差分進化（GOBL-DE）進行對比，得到不同訂單組合下的目標函數和求解時間，試驗結果如表1所示.

由表1可知，結合了天車分配算法和庫位分配規則的GOBL-DECS（GOBL-DE-Crane allocation algorithm-Stock allocation rule）在對作業進行調度時，平均延遲成本和平均等待成本均明顯低于GOBL-DE算法.這是由于GOBL-DE算法在求解時，無法合理分配天車以及入庫訂單和倒垛訂單的位置，導致天車避讓和空行程的增加.

對任務數為50，訂單組合為C（30，10，10）的情況進行分析，得到迭代結束時兩種算法的帕累托前沿，如圖4所示.從圖中可以看出，GOBL-DECS算法的帕累托前沿能向更優解逼近.盡管GOBL-DECS求解時增加了一定的時間成本，但算法表現卻得到了極大的提高.可見本文提出的天車分配算法和庫位分配規則在解決車間多天車多任務調度問題時具有良好的性能.

3.2? ?數值分析

為測試本文提出的算法在求解車間天車多目標調度問題時的整體性能，設計具有代表性的多目標優化NSGA-Ⅱ和SPEA-Ⅱ算法進行對比計算試驗.以帕累托解的個數（NF），解的平均擁擠距離（crowding distance，CD，CD越大代表解的分散性越好），單次迭代運行時間（CPU）作為評價算法性能的指標，取任務數分別為10、30、50、70、90 5種情況下的調度問題進行仿真試驗，結果如表2所示.

由表2可知，在不同任務數組合下，本文提出的GOBL-DECS算法得到的帕累托解的個數和解的平均擁擠距離均優于NSGA-Ⅱ.與SPEA-Ⅱ對比，GOBL-DECS的CD值也更優.盡管GOBL-DECS算法在時間表現上稍顯劣勢，但結合考慮解的優度之后，本文認為GOBL-DECS在時間上的差距對計算成本影響甚微.

圖5和圖6分別以任務數為30和90的一組數據為例，給出了分別運行GOBL-DECS、NSGA-Ⅱ和SPEA-Ⅱ3種算法的帕累托解的情況.從圖中可以看出，NSGA-Ⅱ和SPEA-Ⅱ在算法表現上較為相近.當問題規模較小時，GOBL-DECS算法和其他兩種算法得到的部分解集相互支配，但總體而言GOBL-DECS得到的解集更優.隨著問題規模的增大，GOBL-DECS算法的優勢更加明顯，具有更好的跳出局部最優解的能力，可以引導種群向更優的帕累托前沿逼近.

1）建立了考慮天車任務初始態和時空約束的

軌跡映射模型，采用雙層編碼機制，將訂單排序和天車分配問題映射統一，為解決車間天車調度問題提供了新的研究思路.

2）仿真試驗的對比驗證表明了算法具有良好

的求解性能，證明了算法的有效性和可行性.

3）研究補充了車間天車調度中聯合調度入庫、出庫作業的短缺，豐富了此類調度問題的理論方法.

4）本文僅對單一運行速度下的天車調度進行

了探討，今后將結合能源節約的目標，對搬運過程中速度可變的車間多天車調度問題進行深入研究.

參考文獻

[1]? ?KITAMURA S，MURAO H. Simulation-based optimization model and metaheuristic solution of multiple crane scheduling problems [C]//Proceedings of 2004 IEEE International Conference on Systems，Man and Cybernetics. Washington D C：IEEE，2004：1469—1474.

[2]? ?FENG J，CHU C，CHE A. Cyclic job shop hoist scheduling with multi-capacity reentrant tanks and time-window constraints [J]. Computers & Industrial Engineering，2018，120：382—391.

[3]? ?ZHOU Z，LI L. A solution for cyclic scheduling of multi-hoists without overlapping [J]. Annals of Operations Research，2009，168（1）：5—21.

[4]? ?MAO Y N，TANG Q H，LI Z X，et al. Mixed-integer linear programming method for multi-degree and multi-hoist cyclic scheduling with time windows [J]. Engineering Optimization，2018，50（11）：1—18.

[5]? ?PETERSON B，HARJUNKOSKI I，HODA S，et al. Scheduling multiple factory cranes on a common track [J]. Computers & Operations Research，2014，48：102—112.

[6]? ?YANG X，LI S. Research of crane scheduling based on birth and death chain in the production shop field [C]//Proceedings of 2015 International Conference on Computer Science and Mechanical Automation （CSMA）. Washington D C：IEEE，2015：246—250.

[7]? ?XIE X，ZHENG Y，LI Y. Multi-crane scheduling in steel coil warehouse [J]. Expert Systems with Applications，2014，41（6）：2874—2885.

[8]? ? YUAN Y，TANG L. Novel time-space network flow formulation and approximate dynamic programming approach for the crane scheduling in a coil warehouse [J]. European Journal of Operational Research，2017，262（2）：424—437.

[9]? ? LIN Q，ZHU Q，HUANG P，et al. A novel hybrid multi-objective immune algorithm with adaptive differential evolution [J]. Computers & Operations Research，2015，62：95—111.

[10]? ZHOU B H，SHEN C Y. Multi-objective optimization of material delivery for mixed model assembly lines with energy consideration [J]. Journal of Cleaner Production，2018，192：293—305.

[11]? 周炳海，王科.帶多重加工前約束的單機MOPJ調度方法[J].哈爾濱工業大學學報，2017，49（7）：158—164.

ZHOU B? H，WANG K. Scheduling method of multi-order-per-job for a single machine with multiple preprocess constraints [J]. Journal of Harbin Institute of Technology，2017，49（7）：158—164.（In Chinese）

[12]? 吳亮紅，王耀南，袁小芳，等.多目標優化問題的差分進化算法研究[J]. 湖南大學學報（自然科學版），2009，36（2）：53—57.

WU L H，WANG Y N，YUAN X F，et al. Research on differential evolution algorithm for MOPs[J]. Journal of Hunan University（Natural Sciences），2009，36（2）：53—57.（In Chinese）

[13]? MEMARI A，RAHIM A R A，HASSAN A，et al. A tuned NSGA-II to optimize the total cost and service level for a just-in-time distribution network [J]. Neural Computing and Applications，2017，28（11）：3413—3427.