毛永年，唐秋華，張利平

(1.武漢科技大學(xué)冶金裝備及其控制教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430081; 2.武漢科技大學(xué)機(jī)械傳動與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢，430081)

自動化制造單元是一類以機(jī)器人為物料運(yùn)輸工具的自動化生產(chǎn)系統(tǒng)，應(yīng)用十分廣泛。工件在此類制造單元中的加工通常具有一定的彈性，也就是工件的加工時(shí)間可以在給定的上下限范圍(即時(shí)間窗口)內(nèi)變動。物料搬運(yùn)機(jī)器人必須在給定的時(shí)間窗口內(nèi)，將工件從當(dāng)前工作站轉(zhuǎn)移到下一工序所在的工作站。為了便于管理，自動化制造單元常采用循環(huán)生產(chǎn)模式，即物料搬運(yùn)機(jī)器人在每一個(gè)生產(chǎn)循環(huán)內(nèi)執(zhí)行相同的搬運(yùn)作業(yè)序列。規(guī)劃與調(diào)度機(jī)器人的搬運(yùn)作業(yè)對提高系統(tǒng)生產(chǎn)效率、保證產(chǎn)品質(zhì)量具有重要意義。

針對自動化制造單元調(diào)度問題，以數(shù)學(xué)規(guī)劃和分支定界為主的精確求解算法有一定的優(yōu)勢，但是，隨著問題的拓展和深入，此類方法易受到問題規(guī)模和輸入?yún)?shù)(例如時(shí)間窗口)的限制。部分研究者考慮用啟發(fā)式或元啟發(fā)式算法求解最基本的自動化制造單元調(diào)度問題。Lim[1]提出了基于機(jī)器人搬運(yùn)順序編碼的遺傳算法。李鵬等[2]采用工件加工時(shí)間編碼方式，將混沌思想引入遺傳算法求解此類問題。晏鵬宇等[3]使用啟發(fā)式方法構(gòu)造遺傳算法的初始種群，以增加其中的可行解數(shù)量。考慮到時(shí)間窗口約束導(dǎo)致問題可行解空間非常狹窄，王躍崗等[4]在使用量子進(jìn)化算法求解時(shí)，進(jìn)一步利用Levner等[5]提出的多項(xiàng)式算法來構(gòu)造初始種群，同時(shí)針對進(jìn)化過程中產(chǎn)生的不可行解引入了基于圖論的修復(fù)策略。Lei等[6]基于工件在工作站的初始分配，采用0-1編碼并使用啟發(fā)式方法構(gòu)造工件初始分配所對應(yīng)的機(jī)器人搬運(yùn)作業(yè)序列，同時(shí)提出了啟發(fā)式修復(fù)策略修復(fù)不可行解。該研究由于在量子進(jìn)化算法中融入了大量的啟發(fā)式策略，雖然算法的搜索效率明顯提高，但是針對特定類型案例的求解精度還有待于改善。

為了克服基本遺傳算法容易陷入局部最優(yōu)這一缺陷，本文設(shè)計(jì)一種改進(jìn)遺傳算法，采用基于循環(huán)序列的編碼排列方式并配合兩點(diǎn)交叉操作，以保證算法進(jìn)化過程中種群的多樣性。針對所研究問題可行解空間非常狹窄這一特點(diǎn)，本文提出啟發(fā)式目標(biāo)函數(shù)，以便在可行解很少甚至無可行解時(shí)，依然能夠指引種群朝著有利方向進(jìn)化。對于不可行解采用聯(lián)動修復(fù)機(jī)制，自適應(yīng)調(diào)整待修復(fù)的目標(biāo)基因片段。同時(shí)引入禁忌表記錄各基因的移動方向以避免對基因的盲目移動，從而保證算法的搜索效率和求解質(zhì)量。最后，使用現(xiàn)有文獻(xiàn)中的基準(zhǔn)案例來驗(yàn)證本文算法的有效性。

1　問題描述和數(shù)學(xué)模型

圖1所示為本文研究的自動化制造單元，包括一個(gè)物料搬運(yùn)機(jī)器人、n個(gè)工作站、裝載站(編號為0)和卸載站(編號為n+1)。每個(gè)工件自裝載站進(jìn)入系統(tǒng)，依次從工作站1到工作站n后，被機(jī)器人卸載到站點(diǎn)n+1。裝載站和卸載站的容量設(shè)為無限大。每個(gè)工作站在任何時(shí)候最多只能加工一個(gè)工件。由于工作站之間沒有緩沖區(qū)，工件在當(dāng)前工作站完成加工后(要滿足時(shí)間窗口約束)，必須立即被機(jī)器人運(yùn)輸?shù)较乱粋€(gè)工序所在的工作站。

圖1　自動化制造單元示例

為了方便模型的表述，定義如下參數(shù)：①搬運(yùn)作業(yè)i，即機(jī)器人將工件從工作站i上取出，然后將其搬運(yùn)到工作站i+1并將其卸載的全部過程，0≤i≤n；②ai、bi分別為工件在工作站i上的加工時(shí)間下限和上限，1≤i≤n；③di為執(zhí)行搬運(yùn)作業(yè)i所需的時(shí)間，0≤i≤n；④ci,j為機(jī)器人空載時(shí)從工作站i到工作站j的移動時(shí)間，0≤i,j≤n+1；⑤M為一足夠大的正數(shù)。

該問題的混合整數(shù)規(guī)劃模型可以表示為：

minT

s.t.：

si-si-1+di-1≥ai-M(1-yi-1,i)，1≤i≤n

(1)

si-(si-1+di-1)≤bi+M(1-yi-1,i)，1≤i≤n

(2)

(si+T)-(si-1+di-1)≥ai-Myi-1,i，1≤i≤n

(3)

(si+T)-(si-1+di-1)≤bi+Myi-1,i，1≤i≤n

(4)

sj-si≥di+ci+1,j-M(1-yi,j)，0≤i,j≤n

(5)

si-sj≥dj+cj+1,i-Myi,j，0≤i,j≤n

(6)

s0=0

(7)

si≥0，1≤i≤n

(8)

T≥si+di+ci+1,0，0≤i≤n

(9)

模型的目標(biāo)函數(shù)是最小化周期長度T。式(1)～式(4)為時(shí)間窗口約束。yi-1,i=1時(shí)，即工件加工的開始和結(jié)束時(shí)間都在同一個(gè)周期內(nèi)，則工件的加工時(shí)長為si-(si-1+di-1)，而式(1)～式(2)表示這時(shí)工件的加工時(shí)長不小于其允許的下限值ai同時(shí)不大于上限值bi。yi-1,i=0時(shí)，即工件加工的開始時(shí)間要晚于其結(jié)束時(shí)間，這意味著工件在工作站i上的加工跨越了兩個(gè)周期，那么工件的實(shí)際加工時(shí)長為(si+T)-(si-1+di-1)，式(3)～式(4)表示這時(shí)工件的加工時(shí)長同樣不小于其下限值ai同時(shí)不大于上限值bi。式(5)～式(6)為機(jī)器人移動能力約束，即機(jī)器人完成一項(xiàng)搬運(yùn)任務(wù)后，必須有足夠的時(shí)間移動到下一個(gè)搬運(yùn)作業(yè)的開始位置。不失一般性，式(7)表示機(jī)器人在裝載站上開始裝載工件的時(shí)刻為一個(gè)周期的開始時(shí)刻。式(8)限制所有搬運(yùn)作業(yè)的開始時(shí)間為正。式(9)強(qiáng)調(diào)周期T的長度必須不小于任何搬運(yùn)作業(yè)完成后機(jī)器人回到裝載站的時(shí)間。

2　改進(jìn)遺傳算法的設(shè)計(jì)

2.1　編碼方式和種群初始化

本文采用整數(shù)編碼，直接將搬運(yùn)作業(yè)的序號作為染色體的基因組成。設(shè)X={x0,x1,…,xn}為種群中的一條染色體，其中xi為一個(gè)周期內(nèi)的第i次搬運(yùn)作業(yè)的編號。下面以6項(xiàng)搬運(yùn)任務(wù)為例來說明此類編碼方式。在傳統(tǒng)編碼方式中(見圖2(a))，通常將搬運(yùn)作業(yè)0作為序列的第一個(gè)搬運(yùn)任務(wù)?？紤]到所研究問題的循環(huán)特性，以任意搬運(yùn)作業(yè)為首的序列都可以等價(jià)轉(zhuǎn)換為以搬運(yùn)作業(yè)0為起始位置的序列。例如，圖2(b)中循環(huán)序列的編碼排列事實(shí)上與圖2(a)中的序列等價(jià)。為了克服算法容易陷入局部最優(yōu)這一缺點(diǎn)，本文采用如圖2(b)所示的以任意搬運(yùn)作業(yè)為首的編碼方式(循環(huán)序列)，并采用完全隨機(jī)初始化的方式保證搬運(yùn)作業(yè)序列的多樣化。

圖2　兩種等效的編碼方式

2.2　交叉、變異操作

為了使優(yōu)良的基因片段在進(jìn)化過程中被保留下來，本文采用兩點(diǎn)交叉操作，如圖3所示。首先用錦標(biāo)賽選擇法從種群中挑出兩條競爭獲勝的染色體，記為父代1和父代2。隨機(jī)從基因位置0～n中選取兩點(diǎn)p1和p2(p1

圖3　兩點(diǎn)交叉操作

2.3　啟發(fā)式評價(jià)函數(shù)

對于任意給定的一個(gè)可行染色體(機(jī)器人搬運(yùn)作業(yè)序列)，使用下式計(jì)算染色體適應(yīng)度值：

f1=T

(10)

根據(jù)染色體基因編碼可得到?jīng)Q策變量yi,j，則式(1)～式(9)可轉(zhuǎn)換為如下形式：

sj-si≥α+βT，0≤i,j≤n

(11)

式中：α為實(shí)數(shù)；β的取值為-1、0或1。

事實(shí)上，式(11)是一類特殊的線性規(guī)劃問題，可以用賦權(quán)有向圖[7]來描述，Levner等[8]將其歸納為帶參數(shù)的最短路徑問題，并基于Bellman-Ford算法提出計(jì)算復(fù)雜度為O(n2m)的多項(xiàng)式>算法，此處n為圖的節(jié)點(diǎn)數(shù)量，m為圖中弧的數(shù)量。

染色體X的不可行主要由機(jī)器人移動能力不能滿足工件的加工時(shí)間窗口所導(dǎo)致。當(dāng)yi-1,i=1時(shí)，若如圖4所示的部分序列i-1→…→i不可行，則整個(gè)染色體X一定不可行；當(dāng)yi-1,i=0>時(shí)，若如圖5所示的部分序列i-1→…→i不可行，則整個(gè)染色體X同樣不可行。

圖4　搬運(yùn)作業(yè)i在i-1之后

圖5　搬運(yùn)作業(yè)i在i-1之前

為了方便描述，定義序列Si為染色體X中分別以搬運(yùn)作業(yè)i-1開始、搬運(yùn)作業(yè)i結(jié)束的一串有序子序列i-1→…→i。由于一個(gè)完整的染色體X包含n個(gè)如圖4或圖5這樣的子序列，因此，任意一個(gè)子序列不可行都會導(dǎo)致整個(gè)染色體不可行。值得強(qiáng)調(diào)的是，交叉、變異操作會產(chǎn)生大量的不可行解，這些不可行解代表了種群的進(jìn)化信息，為了區(qū)分這些不可行解，記參數(shù)ω為所有不可行子序列S的個(gè)數(shù)之和，并采用式(12)來計(jì)算不可行染色體的適應(yīng)度值:

f2=ω3

(12)

為了統(tǒng)一染色體適應(yīng)度值的計(jì)算，本文采用式(13)來計(jì)算任意一個(gè)染色體的適應(yīng)度值。

F=T+ω3

(13)

對于子序列Si={i-1,…,i}，可采用下面的算法來判斷其可行性。

輸入：子序列Si。

輸出：0 或 1。∥0表示子序列Si可行，1表示子序列Si不可行。

步驟1計(jì)算子序列Si的長度，記為R，設(shè)置t[0]←0。

步驟2

Forj=1 toR-1do

t[j]←t[j-1]+dSi[j-1]+cSi[j-1]+1,Si[j];

Fork=0 toj-1do

IfSi[k]+1=Si[j],then

t[j]←max(t[j],t[k]+dSi[k]+aSi[k]+1)

End

End

End

步驟3Ift[R-1]≤t[0]+dSi[0]+bSi[0]+1,

thenreturn0;

elsereturn1。

2.4　不可行解修復(fù)策略

針對不可行解的修復(fù)策略對提高算法的運(yùn)行效率十分關(guān)鍵。由于機(jī)器人移動能力約束和時(shí)間窗口約束具有很強(qiáng)的耦合性，僅僅修復(fù)某個(gè)特定的子序列往往會導(dǎo)致其它的子序列不可行，從而嚴(yán)重影響修復(fù)策略的實(shí)際效果。本文提出在修復(fù)不可行子片段Si時(shí)采用聯(lián)動機(jī)制，即在修復(fù)Si子片段后同時(shí)修復(fù)與其相關(guān)的上游子片段Si-1或者下游子片段Si+1，并根據(jù)搜索進(jìn)程不斷更新修復(fù)目標(biāo)S，直到滿足終止條件。同時(shí)，使用方向禁忌表v記錄染色體X中各基因的移動方向，從而避免迂回搜索。不可行解修復(fù)策略的具體操作步驟如下。

輸入：染色體X，修復(fù)次數(shù)η。

輸出：染色體X′。

步驟1設(shè)置向量v[]←0；參數(shù)obj←1，g1←0，g2←0，p1←0，p2←0，n←0。

步驟2Ifn>η，then進(jìn)入步驟7；

elsen←n+1，進(jìn)入步驟3。

步驟3∥找到需要修復(fù)的子片段Si。

探測染色體X的每一個(gè)子序列S，找到最大不可行子片段Si。分別設(shè)置g1、g2為片段Si的第一個(gè)元素以及最后一個(gè)元素，同時(shí)設(shè)置p1為g1在染色體X中的位置，設(shè)置p2為g2在染色體X中的位置。

步驟4∥確定需要移動的目標(biāo)基因obj，若obj=1，表示移動基因g1，否則移動基因g2。

Ifv[g1]!=-1 &&v[g2]=1，then

obj←1，v[g1]←1；

elseifv[g1]=-1 &&v[g2]！=1，thenobj←0，v[g2]←-1；

elseifv[g1]=-1 &&v[g2]=1，then

進(jìn)入步驟7；

else

IfRand()<0.5，thenobj←1，v[g1]←1；

elseobj←0，v[g2]←-1；

End

End

步驟5∥移動目標(biāo)基因。

Ifobj=1，then在染色體X中順時(shí)針移動基因g1直到子序列S={g1,…,g2}可行；

else在X中逆時(shí)針移動g2直到子序列S={g1,…,g2}可行。

分別用p1、p2記錄g1、g2在染色體X中的位置。

步驟6∥探測上游或下游序列是否可行。

Ifobj=1，then探測序列Sg1(以g1-1為首的子序列)是否可行，如果該序列可行，則進(jìn)入步驟2，否則，設(shè)置g1←g1-1，g2←g1+1，obj←1，v[g1]←1，進(jìn)入步驟5。

else探測序列S(g2+1)(以g2為首的子序列)是否可行。如果該序列可行，則進(jìn)入步驟2，否>則，設(shè)置g1←g2，g2←g1+1，obj←0，v[g2]←-1，進(jìn)入步驟5。

End

步驟7輸出染色體X′，停止。

2.5　局部鄰域搜索

上節(jié)所述的不可行解修復(fù)策略對算法進(jìn)化過程中產(chǎn)生的不可行染色體進(jìn)行了高強(qiáng)度的鄰域搜索。為了提高算法的運(yùn)行效率和收斂速度，局部搜索策略只針對可行染色體。具體搜索過程為：以交叉、變異操作后種群中出現(xiàn)的可行染色體為參照對象，對每個(gè)基因采用右鄰基因交換的方式產(chǎn)生新解，選取產(chǎn)生的n+1個(gè)新解中最好的一個(gè)個(gè)體與參照對象進(jìn)行對比，只要該新解的適應(yīng)度值不大于參照對象的適應(yīng)度值，則用該新解替換參照對象。

2.6　改進(jìn)遺傳算法步驟

綜上，本文設(shè)計(jì)的改進(jìn)遺傳算法步驟如下:

步驟1設(shè)置種群規(guī)模N、交叉概率Pc、變異概率Pm、最大修復(fù)循環(huán)次數(shù)η以及最大迭代次數(shù)π1和π2，并初始化迭代計(jì)數(shù)器n←0、μ←0。

步驟2隨機(jī)初始化種群。

步驟3評價(jià)當(dāng)前種群，如果有優(yōu)于全局最優(yōu)解的新解產(chǎn)生，則保存該新解并設(shè)置μ←0，否則，運(yùn)用精英保留策略，即用全局最優(yōu)解替換當(dāng)前種群中的最差解，同時(shí)設(shè)置μ←μ+1。

步驟4設(shè)置n←n+1。如果n>π1或者μ>π2，算法停止。

步驟5進(jìn)行交叉、變異操作。

步驟6對當(dāng)前種群中的可行解進(jìn)行局部鄰域搜索，對種群中的不可行解進(jìn)行可行性修復(fù)。跳轉(zhuǎn)到步驟3。

3　算法驗(yàn)證

為了檢驗(yàn)算法的有效性，在CPU主頻為2.30GHz的PC機(jī)上使用C++語言對所提出的改進(jìn)遺傳算法進(jìn)行編碼。相關(guān)參數(shù)設(shè)置為：種群規(guī)模N=20，交叉概率Pc=0.9，變異概率Pm=0.1，不可行解的最大修復(fù)循環(huán)次數(shù)η=5，最大迭代次數(shù)π1=1000以及π2=100。

采用本文提出的基于啟發(fā)式目標(biāo)函數(shù)和不可行解修復(fù)策略的改進(jìn)遺傳算法(HIGA)求解現(xiàn)有文獻(xiàn)中的基準(zhǔn)案例，包括P&U、P&U(mini)、Lignel、 Ligne2、 Bo1、Bo2、Copper 和Zinc。這些案例的原始數(shù)據(jù)來源于文獻(xiàn)[9-11]，其中案例P&U(mini)是案例P&U問題規(guī)?？s小后的版本，使用的原始數(shù)據(jù)在表1中列出。值得強(qiáng)調(diào)的是，本文首次使用元啟發(fā)式算法求解了基準(zhǔn)案例Copper和Zinc并報(bào)道了求解結(jié)果。全部案例的測試結(jié)果分別在表2～表5中列出，作為對照，表中同時(shí)給出了遺傳算法(GA)[1]、量子進(jìn)化算法(QEA)[4]以及基于啟發(fā)式的量子進(jìn)化算法(HQEA)[6]的測試結(jié)果。表2～表5中，“Gap”表示算法所獲得的最好解與最優(yōu)解之間的百分偏差,“—”表示該算法無法獲得可行解。

表1　本文使用的基準(zhǔn)案例P&U(mini)的測試數(shù)據(jù)

表2基準(zhǔn)案例P&U和P&U(mini)的測試結(jié)果

Table2TestresultsofbenchmarkproblemsP&UandP&U(mini)

算法P&U運(yùn)行時(shí)間/s最好解Gap/%　P&U(mini)運(yùn)行時(shí)間/s最好解Gap/%GA65．773340．724．12840QEA82．5521039．82840HQEA5．4252104．262840HIGA1．0452100．022840

表3基準(zhǔn)案例Bo1和Bo2的測試結(jié)果

Table3TestresultsofbenchmarkproblemsBo1andBo2

算法Bo1運(yùn)行時(shí)間/s最好解Gap/%　Bo2運(yùn)行時(shí)間/s最好解Gap/%GA64．7340．920．959．2322．415．4QEA93．1281．9074．4279．30HQEA9．87327．016．05．04279．30HIGA0．79281．900．78279．30

表4基準(zhǔn)案例Ligne1和Ligne2的測試結(jié)果

Table4TestresultsofbenchmarkproblemsLigne1andLigne2

算法Ligne1運(yùn)行時(shí)間/s最好解Gap/%　Ligne2運(yùn)行時(shí)間/s最好解Gap/%GA64．848122．769．782512．4QEA85．63920150．47220HQEA7．894114．845．387220HIGA1．87539201．5327220

表5基準(zhǔn)案例Copper和Zinc的測試結(jié)果

Table5TestresultsofbenchmarkproblemsCopperandZinc

算法Copper運(yùn)行時(shí)間/s最好解Gap/%　Zinc運(yùn)行時(shí)間/s最好解Gap/%GA——————QEA1432146．716．2———HQEA——————HIGA0．501847．201．751743．40

從測試結(jié)果來看，使用文獻(xiàn)[1]中的GA求解這些基準(zhǔn)案例的效果非常不理想，而使用了啟發(fā)式初始化和修復(fù)策略的QEA獲得了常規(guī)基準(zhǔn)案例P&U、P&U(mini)、Lignel、Ligne2、Bo1和Bo2的最優(yōu)解。HQEA考慮到問題特征，采用啟發(fā)式方法進(jìn)行解碼，從而縮減了算法搜索的解空間，因此其求解效率要明顯高于QEA，但是啟發(fā)式的解碼方法難免丟失最優(yōu)解，從而導(dǎo)致HQEA在求解某些案例時(shí)存在局限性。對于案例Bo1和Ligne1，HQEA給出的結(jié)果和最優(yōu)解有一定的偏差；對于案例Copper和Zinc，HQEA則不能給出任何可行或者較滿意的解。

本文提出的基于啟發(fā)式目標(biāo)函數(shù)和不可行解修復(fù)策略的改進(jìn)遺傳算法(HIGA)，以最短的運(yùn)行時(shí)間給出了全部基準(zhǔn)案例的最優(yōu)解，其原因在于：一方面，算法進(jìn)化過程中產(chǎn)生的大量不可行解代表了種群的進(jìn)化信息，如果全部平等對待則會丟失部分有用的信息，從而導(dǎo)致算法進(jìn)入盲目的無序搜索狀態(tài)，尤其是當(dāng)可行解數(shù)量非常有限時(shí)(例如案例Copper和Zinc)，如果不用啟發(fā)式目標(biāo)函數(shù)對不可行解進(jìn)行篩選，則很難在迭代過程中將有用信息進(jìn)行積聚從而為發(fā)現(xiàn)可行解提供可能；另一方面，本文采用的不可行解修復(fù)策略不是簡單修復(fù)某一串基因，而是使用聯(lián)動修復(fù)機(jī)制對不可行染色體進(jìn)行反復(fù)深度修復(fù)，從而使染色體最大可能地朝著目標(biāo)函數(shù)優(yōu)化的方向進(jìn)行調(diào)整。

圖6為HIGA求解案例Zinc的收斂曲線。由圖6可見，最好解的迭代曲線跳躍很大。在第15代以前，算法沒有找到任何可行解。在第15代時(shí)找到可行解3289.8，之后算法連續(xù)約20代沒有進(jìn)化，隨后又突然找到可行解1791.1，最后停滯30代后找到了最優(yōu)解1743.4。雖然種群的平均適應(yīng)度值一直上下波動，但是總體趨勢是變小的。這說明，雖然大多數(shù)時(shí)候最好解沒有得到更新，但是種群始終是向好的方向進(jìn)化的，因此算法獲得更好解的概率隨迭代的累積而不斷增大。

圖6　HIGA求解案例Zinc的收斂曲線

Fig.6ConvergencecurveofbenchmarkproblemZincbyHIGA

4　結(jié)語

針對帶時(shí)間窗口的自動化制造單元調(diào)度問題，本文提出了一種改進(jìn)遺傳算法。以啟發(fā)式目標(biāo)函數(shù)引導(dǎo)種群進(jìn)化方向，采用循環(huán)序列的編碼排列方式并配合兩點(diǎn)交叉操作，盡可能地保證了進(jìn)化過程中種群的多樣性。在評價(jià)種群時(shí)，為了提高算法運(yùn)行效率，首先對染色體的可行性進(jìn)行判別從而減少了采用精確算法評價(jià)種群個(gè)體的計(jì)算復(fù)雜度。針對不可行解，采用聯(lián)動修復(fù)機(jī)制，根據(jù)修復(fù)過程自適應(yīng)調(diào)整待修復(fù)目標(biāo)片段，同時(shí)引入禁忌搜索的思想避免了算法的盲目搜索，提高了算法的搜索效率和求解質(zhì)量。對現(xiàn)有文獻(xiàn)中基準(zhǔn)案例的測試結(jié)果驗(yàn)證了本文算法求解此類問題的有效性。

[1]Lim J M. A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line[J].Computers and Industrial Engineering,1997,33(3/4):789-792.

[2]李鵬，車阿大.基于混沌遺傳算法的自動化生產(chǎn)單元調(diào)度方法[J].系統(tǒng)工程，2008,26(11)：75-80.

[3]晏鵬宇，車阿大，李鵬，等. 具有柔性加工時(shí)間的機(jī)器人制造單元調(diào)度問題改進(jìn)遺傳算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2010，16(2)：404-410.

[4]王躍崗，車阿大.基于混合量子進(jìn)化算法的自動化制造單元調(diào)度[J].計(jì)算機(jī)集成制造系統(tǒng)，2013，19(9)：2193-2201.

[5]Levner E, Kats V, Levit V E. An improved algorithm for cyclic flowshop scheduling in a robotic cell[J].European Journal of Operational Research,1997,97(3):500-508.

[6]Lei W D, Manier H, Manier M A, et al. A hybrid quantum evolutionary algorithm with improved decoding scheme for a robotic flowshop scheduling problem[J].Mathematical Problems in Engineering, 2017,2017:3064724.

[7]KatsV,LevnerE.Cyclicroutingalgorithmsingraphs: performance analysis and applications to robot scheduling[J].Computers and Industrial Engineering,2011,61(2):279-288.

[8]Levner E, Kats V. A parametric critical path problem and an application for cyclic scheduling[J].Discrete Applied Mathematics,1998,87(1-3):149-158.

[9]Phillips L W, Unger P S. Mathematical programming solution of a hoist scheduling program[J].AIIE Transactions,1976,8(2):219-225.

[10] Chtourou S, Manier M A, Loukil T. A hybrid algorithm for the cyclic hoist scheduling problem with two transportation resources[J]. Computers and Industrial Engineering,2013, 65(3):426-437.

[11] Leung J M Y, Zhang G Q, Yang X G, et al. Optimal cyclic multi-hoist scheduling: a mixed integer programming approach[J]. Operations Research, 2004,52(6):965-976.