人工蜂群算法求解混合約束流水車間調(diào)度問題

孫厚權(quán)，張其亮

(江蘇科技大學 電氣與信息工程學院，江蘇 張家港 215600)

0 引 言

流水車間調(diào)度問題是一類經(jīng)典的組合優(yōu)化問題，當機器數(shù)m>2時，該類問題被證明為NP-難問題[1]。傳統(tǒng)的FSS問題是在假設(shè)相鄰工序之間存在無限大的緩沖區(qū)這一前提下進行的，然而在實際生產(chǎn)過程中，工序之間的緩沖區(qū)往往是有限的甚至是不存在的。例如，在鋼鐵軋制過程中，為了防止金屬成分遭到破壞，在鋼板冷卻之前，板坯的一系列加熱過程必須連續(xù)進行，工件在工序之間的加工不能有停頓，此類流水車間調(diào)度問題被稱為無等待流水車間調(diào)度(no wait flow shop scheduling，NWFSS)問題；另外，在一些食品加工生產(chǎn)線，食品在一個工序加工完成后，若緊鄰下一道工序的加工機器非空閑，則加工食品將被阻塞在當前工序的加工機器上，直到緊鄰下一道工序的加工機器可用，該類問題被稱為阻塞流水車間調(diào)度(blocking flow shop scheduling，BFSS)問題。

相對于傳統(tǒng)的流水車間調(diào)度問題，NWFSS問題和BFSS問題更具有實際意義。查閱文獻知，國內(nèi)外已有不少專家學者對NWFSS問題、BFSS問題進行了研究，并取得了較好的成果。但是目前的研究大都假定所有工序間的約束是單一約束，對工序間可能具有不同緩沖約束的調(diào)度問題研究相對較少，目前類似的研究文獻主要有：文獻[2]將傳統(tǒng)BFSS問題定義為RSb(release when starting blocking)，在此基礎(chǔ)上提出了一種新的阻塞調(diào)度問題，稱之為RCb(release when completing blocking)，并對工序具有兩種混合阻塞約束的調(diào)度問題進行了分析和求解；文獻[3]針對工序間RSB約束和RCB約束及RCB*(release when completing blocking*)約束混合存在的流水車間調(diào)度問題設(shè)計了遺傳算法進行求解，算法雖然能得到較優(yōu)解，但是在樣本空間較大時，算法收斂速度較慢，效率不高；文獻[4]利用人工蜂群算法求解與文獻[3]相同的問題，取得了較好的解；文獻[5]進一步進行拓展，提出了Wb(without blocking)約束、RSB約束和RCB約束及RCB*約束混合存在的車間調(diào)度問題，并利用遺傳算法進行了求解；文獻[6]提出了阻塞約束和無等待約束混合的車間調(diào)度問題，并設(shè)計了分支限界法進行求解；文獻[7]將列車調(diào)度問題歸結(jié)為阻塞約束和與無等待約束混合的柔性車間調(diào)度問題，并將問題建立了析取圖模型，設(shè)計了兩階段混合啟發(fā)式算法進行求解，結(jié)果滿足列車運行要求。

雖然已有文獻對工序具有不同約束需求的調(diào)度問題進行了研究，但對于在流水車間調(diào)度中，工序具有不同緩沖需求問題的研究還很少。因此，在現(xiàn)有研究基礎(chǔ)上，文中設(shè)計了一個工序間具有無等待約束和阻塞約束兩種不同需求的流水車間調(diào)度(NW-BFSS)問題，并提出了求解的離散人工蜂群算法，并通過實驗證明算法的可行性和有效性。

1 NW-BFSS問題模型

NW-BFSS問題可描述為：工件具有相同的加工工藝，n個工件按順序在m道工序(一道工序具有一臺加工機器)上進行加工；某一時刻每臺機器只能加工一個工件；部分工序間具有阻塞約束，部分工序間具有無等待約束。第i(0

令π={π1,π2,…,πn}為該問題的一個加工序列，Ri,j表示工件πi釋放機器j的時間，Si,j表示工件πi在機器j上的開始加工時間，Ci,j為工件πi在機器j上的完工的時間。給出NW-BFSS問題的數(shù)學模型如下：

minCmax(π)=minCn,m

(1)

s.t.

Ri,j≥Ri-1,j+1,i∈{2,3,…,n},k∈{1,2,…,m}

(2)

Ri,j=max(Ri,j-1+Pi,k,Ri-1,j+1),i=2,3,…,n,j=2,3,…,m-1

(3)

Si,j=Ri,j-1,j={2,3,…,m}

(4)

Si,j=Ci,j-1,j={2,3,…,m}

(5)

Ci,j=Ri,j(i=1,2,…,n,j=1,2,…,m)

(6)

其中，式1為問題目標，即最小化最大完工時間；式2描述了加工工件在機器上加工時的阻塞約束；式3表示阻塞約束下工件釋放機器時間的計算方法；式4表示阻塞約束下工件在機器上開始加工時間的計算方法；式5、式6表示工件在機器上加工時的無等待約束關(guān)系。

2 基本人工蜂群算法

人工蜂群算法(ABC)是根據(jù)蜜蜂尋找食物的過程演化而來，是一種新的群體智能算法[8]。在ABC算法中，問題的優(yōu)化解對應(yīng)食物源，食物源的蜂蜜價值即為優(yōu)化問題中的目標函數(shù)。算法根據(jù)分工將種群分為雇傭蜂、跟隨蜂和偵查蜂三類，雇傭蜂負責在食物源周圍進行搜索，以尋找到更好的食物源；雇傭蜂經(jīng)搜索后把食物源的信息帶回，守在蜂巢中的跟隨蜂則根據(jù)概率選擇較好的食物源進一步進行搜索；經(jīng)過若干周期后，如果食物源沒有更新，則該雇傭蜂轉(zhuǎn)變?yōu)閭刹榉?，在整個解空間中隨機搜索新的食物源?；続BC算法的主要步驟為：

(1)隨機初始化SN個食物源；

(2)雇傭蜂階段：在食物源附近進行鄰域搜索，產(chǎn)生鄰域解；

(3)跟隨蜂階段：選擇較好的食物源進一步進行搜索；

(4)偵查蜂階段：在解空間內(nèi)隨機選擇新的食物源替代有限周期內(nèi)沒有更新的食物源；

(5)判斷算法是否終止。如果終止，則輸出最優(yōu)解，否則轉(zhuǎn)步驟2執(zhí)行。

3 求解NW-BFSS問題的離散人工蜂群算法

文獻[9-10]等都利用人工蜂群解決了作業(yè)調(diào)度問題，但縱觀現(xiàn)有文獻，大都利用ABC算法求解連續(xù)優(yōu)化問題，為此文中對ABC算法進行了離散化以求解離散NW-BFSS問題。

3.1 問題編碼

文中采用排列編碼形式，每一個食物源表示問題的一個解，每個解都由n個不重復的工件構(gòu)成，工件在解中的順序代表了工件的加工次序。比如：有6個工件的NW-BFSS問題，食物源{3,2,6,4,1,5}表示工件的加工順序為：工件3首先加工，依次是工件2,6,4,1，工件5最后加工。

3.2 初始解集構(gòu)建

為了保證初始解的質(zhì)量及多樣性，借助PF_NEH(λ)算法[11]構(gòu)造部分初始優(yōu)化解，剩余的解隨機產(chǎn)生。初始解的產(chǎn)生策略如下：

(1)forλ=2 ton利用PF_NEH(λ)算法產(chǎn)生問題解，并將解按照目標值由小到大的順序排列放入到隊列μ；

(2)從隊列μ的隊首依次取出k個解，并將此k個解作為初始解；

(3)Cnt=k；

(4)若Cnt=n，則終止初始化過程，否則隨機產(chǎn)生一個初始解。若該隨機解不同于Cnt個解中的任何一個，則將該解作為一個初始解，Cnt=Cnt+1；否則，將該解忽略；

(5)跳轉(zhuǎn)到步驟4。

3.3 鄰域結(jié)構(gòu)

文中設(shè)計了三種鄰域搜索的方法，鄰域結(jié)構(gòu)分別定義如下：

交換鄰域，記為N1。產(chǎn)生鄰域的策略為：對工件序列π，隨機選擇一個位置i，將位置i所對應(yīng)的工件πi與π中所有其他位置工件進行交換，選取目標值最小的序列替換π。

插入鄰域，記為N2。產(chǎn)生鄰域的策略為：隨機在個體π中選擇兩個位置a、b，a≠b，若ab，則將πa插入到序列π中b位置之前，可得到序列π'={π1,…,πa,πb,πb+1,…,πa-1,πa+1,…,πn}。

組插入鄰域，記為N3。產(chǎn)生鄰域的策略為：隨機在個體π中選擇位置a，將位置[a,a+λ](λ>0)所對應(yīng)的工件作為一組工件子序列π'，并從π中刪除π'得到序列π''，將π'插入到π''中所有可能位置，取目標值最小的序列替換π。

3.4 信息交換策略

為了能使蜂群在搜索過程中進行信息共享，設(shè)計了兩種信息交換策略R1、R2，定義如下：

R1即為Path_relinking策略，其信息交換的步驟為：

(1)對于當前解π，選擇要進行信息交換的更優(yōu)解π'，定義k=0；

(3)k=k+1，返回步驟2；

(4)從L中選擇目標值最小的解πmin，π=πmin。

3.5 局部搜索策略

基于傳統(tǒng)的迭代貪婪算法，設(shè)計了一種分段破壞的局部搜索策略，用于在給定解的周圍進一步搜索優(yōu)化解。該策略將工件序列分為若干段，基于每段進行破壞，破壞后執(zhí)行構(gòu)建操作，選擇最優(yōu)解，并基于該最優(yōu)解進行下一分段的破壞，算法的具體描述如圖1所示。

3.6 雇傭蜂階段

雇傭蜂的主要任務(wù)是在給定的食物源上進一步進行搜索，找到更好的食物源。文中設(shè)計的離散ABC算

圖1 局部搜索策略執(zhí)行步驟

法中，雇傭蜂的搜索步驟為：

(1)對當前解集中每個食物源分配一個雇傭蜂；

3.7 跟隨蜂階段

跟隨蜂主要負責選擇優(yōu)質(zhì)食物源，并在食物源周圍繼續(xù)深入搜索?；続BC算法采用輪盤賭方式[12]選擇繼續(xù)開采的食物源，為了進一步搜索優(yōu)化解并避免算法陷入局部最優(yōu)，采用按比例選擇較優(yōu)食物源和較差食物源的方式進行。跟隨蜂的具體操作如下：

(1)對所有解按照目標值由小到大順序進行排列，并放入隊列L；

3.8 偵查蜂階段

基本ABC算法中，偵查蜂只有一個，哪個食物源在指定的次數(shù)內(nèi)未更新，就轉(zhuǎn)變?yōu)閭刹榉?，在解空間隨機產(chǎn)生一個解替換原來的解。為了增加算法的全局搜索能力，設(shè)計的偵查蜂過程為：

(1)找到指定次數(shù)內(nèi)未更新的所有解，利用PF_NEH(λ)算法隨機產(chǎn)生一個解，并替換原來的解；

(2)對剩余的解，利用N1鄰域結(jié)構(gòu)進行擾動，利用擾動后得到的解替換原解。

4 實驗結(jié)果及分析

4.1 測試實例

算法基于VC++6.0實現(xiàn)，在處理器為Intel 2-Core-i3-3240、3.4 GHz，內(nèi)存為4 G的PC機上運行。為了驗證算法的有效性，采用表1的實例數(shù)據(jù)進行測試。該實例共有20個工件，5道工序,表中數(shù)字代表該工件分別在5道工序機器上的加工時間。

表1 實例數(shù)據(jù)

工序間的約束如表2所示，無等待約束和阻塞約束混合存在。

表2 工序間約束關(guān)系

設(shè)定迭代次數(shù)為100，解集大小為10，雇傭蜂數(shù)量E=10，跟隨蜂數(shù)量O=10。根據(jù)所設(shè)計的離散人工蜂群算法求解該NW-BFSS問題，計算得到最優(yōu)解的序列為：{10,12,3,18,19,2,8,14,4,15,7,17,6,9,5,11,1,16,0,13}，調(diào)度甘特圖如圖2所示。由圖2可以看出，在第1道工序和第3道工序滿足無等待約束，在第2道工序和第4道工序工件加工時滿足阻塞約束，圖中黑色矩形為阻塞時間?？梢姡惴ㄇ蠼釴W-BFSS問題是可行的、有效的。

圖2 調(diào)度甘特圖

為了進一步驗證算法的求解質(zhì)量，以Taillard[13]經(jīng)典實例作為測試數(shù)據(jù)，測試問題規(guī)模從20×5到200×20。由于沒有相同問題的研究結(jié)果，故在比較算法有效性時對問題做了特殊化，將所有工序約束歸為無等待約束，從而使文中算法與現(xiàn)有文獻中的算法具有可比性。

算法中設(shè)置的關(guān)鍵參數(shù)為：解集大小為10，雇傭蜂數(shù)量E=10，跟隨蜂數(shù)量O=10；算法的終止條件為迭代的次數(shù)，迭代的次數(shù)在n=20時設(shè)置為G=2 000,在n=50時設(shè)置為G=5 000，在n=100時設(shè)置為G=15 000。

4.2 結(jié)果比較及分析

以ARPD(average relative percentage deviation)作為評價指標，將算法與其他解決該問題的算法進行比較，計算公式為：

(7)

其中，Ci為算法在第i次實驗中得到的解；C*為文獻[14]的求解結(jié)果；M為計算次數(shù)。

算法計算得到的ARPD越小，表明所求得的解越優(yōu)。表3為文中算法與HGA[14]算法、TMIIG[15]算法、HDTPL[16]算法在求解NW-BFSS時的比較結(jié)果。

表3 算法比較結(jié)果

問題規(guī)模n×mHGA(ARPD)TMIIG(ARPD)HDTPL(ARPD)文中算法(ARPD)20×50.030.000.000.0020×100.060.000.000.0020×200.030.000.000.0050×50.550.180.240.0650×100.470.060.190.0450×200.470.050.180.03100×50.840.420.410.21100×100.850.120.330.05100×200.910.100.410.06200×101.680.390.620.30200×201.520.210.630.16

從表3可以看出，在較小規(guī)模n=20時，文中算法與其他算法一致，在n=50和n=100規(guī)模時，文中算法要優(yōu)于其他算法。

4.3 收斂性分析

為了體現(xiàn)算法的收斂性，給出了算法在求解n=100時實例Ta061的收斂曲線，如圖3所示?？梢钥闯?，算法在迭代初期收斂速度較快，但隨著迭代次數(shù)的增加收斂變緩，甚至出現(xiàn)局部收斂。而算法在局部收斂后，能跳出局部搜索，最終得到較優(yōu)化的解。

圖3 Ta061實例收斂曲線

5 結(jié)束語

在傳統(tǒng)流水車間調(diào)度問題、阻塞流水車間調(diào)度問題及無等待流水車間調(diào)度問題的基礎(chǔ)上，提出了一個工序間對阻塞約束和無等待約束有不同需求的流水車間調(diào)度問題，并提出了求解的離散人工蜂群算法。通過PF_NEH(λ)算法得到初始優(yōu)質(zhì)食物源，利用雇傭蜂階段的分段破壞迭代貪婪算法，跟隨蜂階段的Path_relingking算法，對解空間進行深入搜索。利用標準數(shù)據(jù)進行測試發(fā)現(xiàn)，算法具有較高的求解質(zhì)量。單目標的流水車間調(diào)度相對簡單，多目標的流水車間調(diào)度問題及混合流水車間調(diào)度具有更高的復雜度，因此下一步將繼續(xù)改進算法，使其能解決更復雜的調(diào)度問題。