基于軌跡映射模型的天車多目標(biāo)調(diào)度方法

周炳海 廖秀梅

（同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海201804）

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

關(guān)鍵詞：天車軌跡映射;時空約束;多目標(biāo);啟發(fā)式算法

中圖分類號：TP391? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)志碼：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

隨著制造業(yè)物流系統(tǒng)的日趨完善，車間天車調(diào)度問題（crane scheduling in workshop，CSW）引起了廣泛的關(guān)注.CSW屬于典型的NP難問題，具有多機(jī)多任務(wù)特點，如何科學(xué)有效地提升天車調(diào)度水平已成為生產(chǎn)過程中亟待解決的問題[1-2].

目前，已有諸多學(xué)者對CSW問題進(jìn)行了研究.針對天車調(diào)度過程中的路徑?jīng)_突問題，文獻(xiàn)[3]考慮將車間分為多個平行區(qū)域，每臺天車只負(fù)責(zé)其所在區(qū)域內(nèi)的搬運任務(wù).文獻(xiàn)[4]分析了調(diào)度過程中天車的不可行路徑，通過建立混合整數(shù)規(guī)劃模型解決路徑?jīng)_突.文獻(xiàn)[5]創(chuàng)新性地提出了天車軌跡映射模型以減少決策變量，并通過移除決策樹中次優(yōu)狀態(tài)的方法完成調(diào)度.文獻(xiàn)[6]從排隊論角度分析了車間天車調(diào)度問題，為提高天車?yán)寐?、減少浪費提供了新思路.

在天車調(diào)度過程中，考慮入庫和出庫訂單的聯(lián)合調(diào)度可以有效提升天車?yán)寐?文獻(xiàn)[7]針對卷鋼存儲的特殊性，對卷鋼出庫過程的天車調(diào)度展開研究.文獻(xiàn)[8]在卷鋼出庫問題的基礎(chǔ)上，考慮了卷鋼入庫的聯(lián)合調(diào)度，分別設(shè)計了時空網(wǎng)絡(luò)流方法和近似動態(tài)規(guī)劃算法求解中小規(guī)模問題和大規(guī)模問題，但針對的是單天車調(diào)度.鮮有文獻(xiàn)考慮入庫和出庫訂單聯(lián)合調(diào)度背景下的CSW決策問題.

本文在考慮天車任務(wù)初始態(tài)和時空約束的基礎(chǔ)上，對聯(lián)合優(yōu)化入庫、出庫訂單的車間多天車調(diào)度問題進(jìn)行研究，提出天車多目標(biāo)調(diào)度方法，并以入庫訂單延遲成本和出庫訂單等待成本為指標(biāo)，評價調(diào)度性能.

1? ?問題描述

1.1? ?天車調(diào)度問題

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

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

y i1）起吊的操作為任務(wù)i1，將其運送到目標(biāo)庫位（x i2，

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

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

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

i<

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

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

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

根據(jù)假設(shè)2）～假設(shè)6），天車需滿足軌跡約束，包括：任意兩臺天車之間的安全距離約束，天車x和y方向上的速度約束，天車執(zhí)行任務(wù)時的位置約束，以及變量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）

根據(jù)假設(shè)7）、假設(shè)8），任意時刻的庫位層高均不能超過其規(guī)定層高，即需滿足：

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

天車軌跡映射模型

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

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

給定任意兩個有時空關(guān)系的訂單i和j，共生成4個任務(wù)：i1，i2，和j1，j2.天車執(zhí)行任務(wù)時將產(chǎn)生4種任務(wù)關(guān)系，分別為：

1）i1和 i2

（14）

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

根據(jù)天車和庫位狀態(tài)以及任務(wù)的開始時間，對式（6）～式（14）進(jìn)行整理，得

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

式中：

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

式中：

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

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

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

2? ?算法構(gòu)建

本文研究的車間天車調(diào)度需解決3個子問題：1）各訂單的執(zhí)行序列;2）各訂單的天車分配;3）入庫訂單的庫位分配.該問題屬于典型的組合優(yōu)化難題，用傳統(tǒng)解析數(shù)學(xué)方法無法對其有效求解.差分進(jìn)化（Differential Evolution，DE）是一種過程簡單、受控參數(shù)少和魯棒性強(qiáng)的全局優(yōu)化算法，與其他進(jìn)化算法相比，DE在解決復(fù)雜全局優(yōu)化問題時的性能更加優(yōu)秀，目前已廣泛應(yīng)用于各類調(diào)度問題[9-10].本文在構(gòu)建天車軌跡映射模型的基礎(chǔ)上，以DE為框架，提出了基于泛化反向?qū)W習(xí)的差分進(jìn)化算法，并設(shè)計天車分配算法和相應(yīng)的庫位分配規(guī)則以指導(dǎo)算法尋優(yōu).

2.1? ?庫位分配規(guī)則

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

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

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

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

假設(shè)種群規(guī)模為NP，基因數(shù)為nVar，當(dāng)前庫位為S（X，Y），其基本步驟為：

1） for p=1 ∶ NP

2） for k=1 ∶ 2*nVar

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

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

5） ? ? 記aj的前置任務(wù)為i;

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

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

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

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

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

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

12） ? ? ?else

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

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

15） ? ? ?end if

16） ? ? end if

17） ? end for

18） end for

2.2? ?天車分配算法

天車分配算法可在較短的時間內(nèi)解決子問題2），并得到較為優(yōu)質(zhì)的天車分配方案.基本步驟為：

步驟1? ?為平衡各天車間的任務(wù)負(fù)載，按照天車編號，將K臺天車按照1，2，…，K進(jìn)行循環(huán)升序排列，直至排列總數(shù)達(dá)到N.

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

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

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

2.3? ?基于泛化反向?qū)W習(xí)的差分進(jìn)化算法

泛化反向?qū)W習(xí)（Generalized Opposition Based Learning，GOBL）指的是在種群的初始化階段和代跳躍階段使用GOBL機(jī)制生成變換種群，對于種群 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的差分進(jìn)化在每一次迭代中融合庫位分配規(guī)則和天車分配算法以指導(dǎo)尋優(yōu)進(jìn)程.

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

上下層編碼的對應(yīng)關(guān)系為：從下層編碼開始，第一個天車編號對應(yīng)第一個訂單的第一個任務(wù)，第二個天車編號若與第一個相同，則執(zhí)行上層編碼第一個訂單的第二個任務(wù)，否則執(zhí)行第二個訂單的第一個任務(wù)，依此類推.

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

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

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

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

變異機(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進(jìn)行個體間交叉操作，得到子代種群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時產(chǎn)生的隨機(jī)數(shù);rd（j）為隨機(jī)選擇的整數(shù).

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

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

均需生成一個0到1之間的隨機(jī)數(shù)rand（0，1）.若

rand（0，1）

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

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

距離排序選擇種群P中最優(yōu)的NP個個體進(jìn)入下

一代.

算法流程圖如圖3所示.

3? ?仿真試驗分析

3.1? ?參數(shù)分析

本試驗在基于Windows 10操作系統(tǒng)的Core i5/2.5GHz內(nèi)存4 GB的計算機(jī)上進(jìn)行.

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

為測試天車分配算法以及庫位分配規(guī)則在求解問題中的表現(xiàn)，設(shè)計未使用天車分配算法、未使用庫位分配規(guī)則的差分進(jìn)化（GOBL-DE）進(jìn)行對比，得到不同訂單組合下的目標(biāo)函數(shù)和求解時間，試驗結(jié)果如表1所示.

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

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

3.2? ?數(shù)值分析

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

由表2可知，在不同任務(wù)數(shù)組合下，本文提出的GOBL-DECS算法得到的帕累托解的個數(shù)和解的平均擁擠距離均優(yōu)于NSGA-Ⅱ.與SPEA-Ⅱ?qū)Ρ?，GOBL-DECS的CD值也更優(yōu).盡管GOBL-DECS算法在時間表現(xiàn)上稍顯劣勢，但結(jié)合考慮解的優(yōu)度之后，本文認(rèn)為GOBL-DECS在時間上的差距對計算成本影響甚微.

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

1）建立了考慮天車任務(wù)初始態(tài)和時空約束的

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

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

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

3）研究補(bǔ)充了車間天車調(diào)度中聯(lián)合調(diào)度入庫、出庫作業(yè)的短缺，豐富了此類調(diào)度問題的理論方法.

4）本文僅對單一運行速度下的天車調(diào)度進(jìn)行

了探討，今后將結(jié)合能源節(jié)約的目標(biāo)，對搬運過程中速度可變的車間多天車調(diào)度問題進(jìn)行深入研究.

參考文獻(xiàn)

[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]? 周炳海，王科.帶多重加工前約束的單機(jī)MOPJ調(diào)度方法[J].哈爾濱工業(yè)大學(xué)學(xué)報，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]? 吳亮紅，王耀南，袁小芳，等.多目標(biāo)優(yōu)化問題的差分進(jìn)化算法研究[J]. 湖南大學(xué)學(xué)報（自然科學(xué)版），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.