毛永年，唐秋華，張利平

(1.武漢科技大學冶金裝備及其控制教育部重點實驗室，湖北 武漢，430081; 2.武漢科技大學機械傳動與制造工程湖北省重點實驗室，湖北 武漢，430081)

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

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

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

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

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

圖1　自動化制造單元示例

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

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

2　改進遺傳算法的設計

2.1　編碼方式和種群初始化

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

圖2　兩種等效的編碼方式

2.2　交叉、變異操作

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

圖3　兩點交叉操作

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

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

f1=T

(10)

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

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

(11)

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

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

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

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

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

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

f2=ω3

(12)

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

F=T+ω3

(13)

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

輸入：子序列Si。

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

步驟1計算子序列Si的長度，記為R，設置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　不可行解修復策略

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

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

輸出：染色體X′。

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

步驟2Ifn>η，then進入步驟7；

elsen←n+1，進入步驟3。

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

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

步驟4∥確定需要移動的目標基因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

進入步驟7；

else

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

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

End

End

步驟5∥移動目標基因。

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

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

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

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

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

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

End

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

2.5　局部鄰域搜索

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

2.6　改進遺傳算法步驟

綜上，本文設計的改進遺傳算法步驟如下:

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

步驟2隨機初始化種群。

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

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

步驟5進行交叉、變異操作。

步驟6對當前種群中的可行解進行局部鄰域搜索，對種群中的不可行解進行可行性修復。跳轉到步驟3。

3　算法驗證

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

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

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

表2基準案例P&U和P&U(mini)的測試結果

Table2TestresultsofbenchmarkproblemsP&UandP&U(mini)

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

表3基準案例Bo1和Bo2的測試結果

Table3TestresultsofbenchmarkproblemsBo1andBo2

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

表4基準案例Ligne1和Ligne2的測試結果

Table4TestresultsofbenchmarkproblemsLigne1andLigne2

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

表5基準案例Copper和Zinc的測試結果

Table5TestresultsofbenchmarkproblemsCopperandZinc

算法Copper運行時間/s最好解Gap/%　Zinc運行時間/s最好解Gap/%GA——————QEA1432146．716．2———HQEA——————HIGA0．501847．201．751743．40

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

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

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

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

Fig.6ConvergencecurveofbenchmarkproblemZincbyHIGA

4　結語

針對帶時間窗口的自動化制造單元調度問題，本文提出了一種改進遺傳算法。以啟發(fā)式目標函數(shù)引導種群進化方向，采用循環(huán)序列的編碼排列方式并配合兩點交叉操作，盡可能地保證了進化過程中種群的多樣性。在評價種群時，為了提高算法運行效率，首先對染色體的可行性進行判別從而減少了采用精確算法評價種群個體的計算復雜度。針對不可行解，采用聯(lián)動修復機制，根據(jù)修復過程自適應調整待修復目標片段，同時引入禁忌搜索的思想避免了算法的盲目搜索，提高了算法的搜索效率和求解質量。對現(xià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)單元調度方法[J].系統(tǒng)工程，2008,26(11)：75-80.

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

[4]王躍崗，車阿大.基于混合量子進化算法的自動化制造單元調度[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.