基于改進(jìn)多種群候鳥遷徙算法的混合流水車間調(diào)度

張素君, 楊文強(qiáng), 顧幸生

(1. 河南科技學(xué)院 機(jī)電學(xué)院, 河南 新鄉(xiāng) 453003; 2. 華東理工大學(xué) 能源化工過程智能制造教育部重點(diǎn)實驗室, 上海 200237)

帶順序依賴準(zhǔn)備時間的混合流水車間調(diào)度[1](HFS-SDST)問題是混合流水車間調(diào)度[2](HFS)問題的一個重要分支.HFS-SDST廣泛存在于鋼鐵、電子、化工、流程工業(yè)及離散智能制造等調(diào)度問題中[2],70%的實際工業(yè)過程需要考慮SDST,若不能正確處理該問題,將使用超過20%的機(jī)器容量[1],而且考慮SDST時,92%的訂單會達(dá)到交貨期[3].因此,雖然在HFS問題中考慮SDST更貼近生產(chǎn)實際,但建模難度會增加,設(shè)計調(diào)度算法時考慮的約束更多,尋找全局最優(yōu)解更加困難[4].

HFS-SDST問題的調(diào)度涉及工件的排序和機(jī)器分配,是典型的組合優(yōu)化問題,已經(jīng)證明HFS-SDST是非確定性多項式難(NP-hard)的問題[5].因此,利用精確算法理論上可以求解,但隨著問題規(guī)模的增大出現(xiàn)組合爆炸問題,幾乎不可能在合理的時間內(nèi)找到最優(yōu)調(diào)度解,難以滿足實際生產(chǎn)需要.啟發(fā)式算法依據(jù)某些規(guī)則對調(diào)度解進(jìn)行構(gòu)造,大大縮短了尋找調(diào)度解的時間,Moccellin等[6]提出基于最短處理時間(SPT)和最長處理時間(LPT)規(guī)則的啟發(fā)式算法,求解針對機(jī)器阻塞、順序依賴、順序獨(dú)立準(zhǔn)備時間的HFS問題,結(jié)果證明了對于HFS-SDST問題,最長處理和準(zhǔn)備時間(LPS)規(guī)則優(yōu)于其他規(guī)則.然而,對于較大規(guī)模的復(fù)雜調(diào)度問題,啟發(fā)式規(guī)則構(gòu)造的調(diào)度解質(zhì)量不高,因此,采用智能優(yōu)化算法為快速求解組合優(yōu)化問題提供了可能;文獻(xiàn)[7]中提出基于超啟發(fā)式學(xué)習(xí)增強(qiáng)的迭代貪心算法求解HFS-SDST問題,采用該算法對一個實際生產(chǎn)實例的設(shè)備數(shù)據(jù)進(jìn)行求解可以達(dá)到較好的效果;周炳海等[8]提出蟻群算法求解雙目標(biāo)HFS問題,但該算法僅限于求解較小規(guī)模的問題;文獻(xiàn)[9]中提出基于代理的改進(jìn)遺傳算法,融合了多智能體和遺傳算法的優(yōu)點(diǎn)求解HFS-SDST問題,并通過實驗得到一些算例的下限值;Pan等[10]列出6個局部搜索算法和3個群智能優(yōu)化算法,其中3個群智能算法為改進(jìn)的果蠅優(yōu)化算法(FOA)、改進(jìn)的候鳥遷徙優(yōu)化(IMBO)和離散人工蜂群(DABC)算法,并給出一種協(xié)同優(yōu)化策略,通過仿真測試對比可知,對于大部分算例,DABC優(yōu)于其他8個算法;Tian等[11]提出基于pareto的自適應(yīng)變鄰域搜索算法,證明了變鄰域搜索求解HFS-SDST問題的有效性;Khare等[12]提出了混合松鼠搜索、反向鯨魚及離散灰狼3個群智能算法,并且為了提高算法的性能,在松鼠算法中引入變鄰域搜索和混合局部搜索,在鯨魚算法中引入反向?qū)W習(xí)策略,優(yōu)化目標(biāo)為總提早和拖期.文獻(xiàn)[10,12]中為群智能算法求解HFS-SDST問題的有效性提供了依據(jù).雖然針對HFS-SDST問題已有一些研究,但算法方面還未形成系統(tǒng)理論成果,因此,研究更高性能的調(diào)度算法具有深刻的理論和實際應(yīng)用意義.

Duman等[13]在2012年提出的候鳥遷徙優(yōu)化(MBO)算法,因調(diào)整參數(shù)少、結(jié)構(gòu)簡單等優(yōu)點(diǎn),得到了廣泛應(yīng)用,但該算法容易早熟收斂且不能直接應(yīng)用于組合優(yōu)化問題,因此,Pan等[14]和Han等[15]分別提出改進(jìn)的離散MBO算法求解HFS問題,且在此基礎(chǔ)上,Pan等[10]對文獻(xiàn)[14]中提出的IMBO進(jìn)行了改進(jìn).Sioud等[3]針對帶SDST的置換流水車間調(diào)度(PFSP)問題提出增強(qiáng)的候鳥遷徙優(yōu)化(EMBO)算法,利用禁忌表控制混合鄰域策略產(chǎn)生鄰域解的多樣性;Meng等[16]和湯洪濤等[17]分別提出采用和聲搜索(HS)策略以及變鄰域搜索策略產(chǎn)生鄰域解的離散MBO,求解批量流車間調(diào)度問題.然而,MBO算法是一種鄰域搜索算法,因此鄰域的選擇對算法的優(yōu)化效果影響較大,而變鄰域搜索是一種可以系統(tǒng)地利用鄰域變化思想的算法;Bez等[18]提出結(jié)合貪心隨機(jī)自適應(yīng)力(GRASP)和變鄰域搜索的混合算法求解帶SDST的平行機(jī)調(diào)度問題.為了改善MBO的早熟收斂問題,文獻(xiàn)[3]中采用重置機(jī)制提高算法的全局搜索能力,此外,采用多種群智能優(yōu)化算法為提高該能力提供了另一種思路;Han等[19]提出改進(jìn)的多種群離散差分進(jìn)化算法,求解多用途批處理設(shè)備調(diào)度問題;Gao等[20]提出一種動態(tài)洗牌的多微種群候鳥遷徙優(yōu)化(SM2-MBO)算法,利用多微子種群并行搜索,求解多資源約束柔性作業(yè)車間調(diào)度問題,但該算法不能在子種群信息交互時產(chǎn)生更好新個體;Tongur等[21]提出了基于粒子群優(yōu)化(PSO)算法的改進(jìn)多種群MBO(IMFMBO)算法,在多種群MBO框架下,通過另一種算法促進(jìn)子種群之間的信息交互,提高算法的全局搜索能力.因此,本文結(jié)合候鳥遷徙優(yōu)化、子種群交互策略和多種群并行搜索思想,提出IMMBO算法求解HFS-SDST問題.

1 HFS-SDST問題

HFS-SDST問題描述如下:n個工件在m個階段的流水線上加工,每個工件j(j=1, 2, …,n)依次按相同的順序通過階段k(k=1, 2, …,m),m個階段至少有一個階段的機(jī)器數(shù)量Mk>1,每個工件可以在階段k的任意一臺機(jī)器上加工.加工過程滿足假設(shè):①任意時刻每個工件只能在一臺機(jī)器上加工;②每臺機(jī)器同一時間只能加工一個工件;③工件在某階段機(jī)器上一旦開始加工不允許中斷.優(yōu)化目標(biāo)為通過確定工件的加工順序以及每階段工件在機(jī)器上的分配情況,使工件的最大加工完成時間(makespan)即Cmax最小.

考慮SDST,n個工件在第1階段機(jī)器上的加工順序一旦確定,依據(jù)工件在可用機(jī)器上的加工完成時間最短的標(biāo)準(zhǔn),工件在后續(xù)階段機(jī)器上的加工順序會相應(yīng)確定.若工件在第1階段的加工順序為π,π=(π1,π2, …,πn),則給出如下HFS-SDST問題的數(shù)學(xué)模型.

若第1階段和階段k(k=2, 3, …,m)的第i(i=1, 2, …,Mk)臺機(jī)器沒有加工過其他工件,則工件πj的完成時間Ck, πj, i分別由下式給出:

Ck, πj, i=Sk, πj, πj+pk, πj,k=1

(1)

Ck, πj, i=max{Sk, πj, πj,Ck-1, πj}+pk, πj,

k=2,…,m

(2)

式中:Ck, πj, i和pk, πj分別為工件πj在階段k的第i臺機(jī)器上的作業(yè)完成時間和作業(yè)時間;Sk, πj, πj為工件πj在k階段的準(zhǔn)備時間.

如果階段k的第i臺機(jī)器加工πj前已經(jīng)加工過其他工件,則工件πj的加工完成時間為

Ck, πj, i=

max{Ck,πτk, i+Sk,πτk, i, πj,Ck-1, πj}+pk, πj

(3)

式中:Ck,πτk, i為階段k的第i臺機(jī)器在加工πj的前1個工件πτk, i的加工完成時間;Sk,πτk, i, πj為πj在階段k的準(zhǔn)備時間.工件πj在階段k的機(jī)器選擇依據(jù)πj在該階段的作業(yè)完成時間最短的原則,即πj在階段k加工完成時間最短的機(jī)器為

其作業(yè)完成時間為

Ck, πj=minCk, πj, i

(4)

最后一個工件在最后階段機(jī)器上的加工完成時間的最大值為

(5)

2 IMMBO

IMMBO算法把初始化種群分成多個子種群,各個子種群利用MBO機(jī)制平行搜索,子種群之間利用離散鯨魚優(yōu)化策略對各子種群的領(lǐng)飛鳥優(yōu)化完成信息交互;同時設(shè)計局部搜索增強(qiáng)和種群多樣化控制機(jī)制提高算法的探索和開發(fā)能力,IMMBO算法框架如下.

步驟1設(shè)置算法相關(guān)參數(shù).利用MNEH算法初始化種群,并把最好的1/3 分到每個子種群作為其領(lǐng)飛鳥,剩下2/3個體隨機(jī)分配到各子種群,每個子種群包括兩個跟飛鳥.

步驟2保存本代最優(yōu)個體.

步驟3子種群領(lǐng)飛鳥利用串行變鄰域搜索策略產(chǎn)生鄰域個體,若鄰域個體中最好的優(yōu)于領(lǐng)飛鳥,替換領(lǐng)飛鳥.

步驟4子種群跟飛鳥利用并行變鄰域搜索策略產(chǎn)生鄰域個體,若鄰域個體中最好的優(yōu)于該跟飛鳥,替換跟飛鳥,若跟飛鳥優(yōu)于本群的領(lǐng)飛鳥,二者交換.

步驟5檢查是否達(dá)到巡回次數(shù),若未達(dá)到,轉(zhuǎn)到步驟3,否則轉(zhuǎn)到步驟6.

步驟6各子種群領(lǐng)飛鳥利用離散鯨魚優(yōu)化策略進(jìn)行交叉,完成子種群之間的信息交互.

步驟7對種群中的最優(yōu)個體執(zhí)行局部搜索(LS).

步驟8更新各子種群領(lǐng)飛鳥的年齡變量,若某子種群的領(lǐng)飛鳥年齡達(dá)到設(shè)定年齡限制,啟動多樣化控制機(jī)制,重新產(chǎn)生一個個體放入種群.

步驟9判斷算法迭代是否達(dá)到最大迭代次數(shù),若未達(dá)到,轉(zhuǎn)到步驟2,否則,算法結(jié)束,輸出最優(yōu)個體及其Cmax值.

2.1 編碼和解碼

連續(xù)的優(yōu)化算法不能直接應(yīng)用于組合優(yōu)化問題HFS-SDST,故需要設(shè)計離散形式的優(yōu)化算法,而設(shè)計離散優(yōu)化算法需要對算法中個體進(jìn)行離散編碼和解碼.針對HFS問題,常用的編碼和解碼方法有矩陣和向量兩種,本文在考慮SDST的同時采用向量編碼,即基于所有工件的一個調(diào)度順序?qū)€體編碼[12],然后,將工件按照排列的順序分配到第1階段的空閑機(jī)器上加工.解碼方法為:考慮準(zhǔn)備時間,工件在第1階段按照編碼順序加工,第k(k=2, …,m)階段的工件加工順序則依據(jù)在該階段加工完成時間最短的原則,重新排列得到工件在階段k的加工順序.

2.2 初始化種群

(1) 計算每個工件的ψj,對ψj升序排列,得到工件在第1階段的排序π=(π1,π2, …,πn).

(2) 依據(jù)第1階段的機(jī)器數(shù)M1,把π分成兩個子序列π1=(π1,π2, …,πM1)和π2=(πM1+1,πM1+2, …,πn),π=π1∪π2.

(3) 隨機(jī)調(diào)換π2中工件的順序得到π2′,與π1合并得到一個新的第1階段工件的排序π′=π1∪π2′.

(4) 重復(fù)(3), 得到與種群規(guī)模相同的工件在第 1 階段機(jī)器上的加工順序,并分別求出其Cmax.

針對初始種群,按種群中個體的Cmax值升序排列,其中前1/3分配到各個子種群,作為領(lǐng)飛鳥;其余2/3隨機(jī)分配到各子種群,作為跟飛鳥.子種群的規(guī)模為3,即1個領(lǐng)飛鳥和2個跟飛鳥.

2.3 子種群領(lǐng)飛鳥進(jìn)化

領(lǐng)飛鳥是一個子種群中最好的個體,領(lǐng)飛鳥的質(zhì)量決定子種群的搜索方向.各子種群中的領(lǐng)飛鳥通過其鄰域個體更新.文獻(xiàn)[22]中已經(jīng)證明插入、交換及迭代貪婪(IG)算法中的破壞重建(DC)操作在流水車間調(diào)度問題中是較好的鄰域解產(chǎn)生策略,因此,領(lǐng)飛鳥的鄰域個體由插入、交換以及DC串聯(lián)起來的串行變鄰域搜索策略產(chǎn)生,即依次執(zhí)行插入、交換和DC,只要采用某一策略能夠產(chǎn)生更好的鄰域個體就繼續(xù)使用,反之,則執(zhí)行下一個策略,直到結(jié)束.

串行變鄰域策略偽代碼如下:

輸入π; 輸出π

k=1

whilek<=3

switchk

case 1 隨機(jī)選擇位置r1上的工件,1≤r1≤n,插入到π的所有可能位置,并依據(jù)指標(biāo)Cmax,找到最好的π′

如果Cmax(π′)

π=π′,k=1

否則

k=k+1

case 2 隨機(jī)選擇位置r1上的工件,1≤r1≤n,與π的其他所有位置上工件交換,并依據(jù)指標(biāo)Cmax,找到最好的π′

如果Cmax(π′)

π=π′,k=2

否則

k=k+1

case 3 對π執(zhí)行破壞重建(DC),得到π′

如果Cmax(π′)

π=π′,k=3

否則

k=k+1

End switch

End while

2.4 子種群跟飛鳥進(jìn)化

產(chǎn)生跟飛鳥鄰域個體的策略,要兼具鄰域個體的質(zhì)量和多樣性,因此子種群中的跟飛鳥領(lǐng)域個體采用并行變鄰域搜索產(chǎn)生,即按照一定概率選擇插入或交換兩種鄰域之一產(chǎn)生跟飛鳥鄰域個體.在生產(chǎn)調(diào)度問題中,插入更易產(chǎn)生較好的鄰域個體,因此,設(shè)置選擇插入鄰域結(jié)構(gòu)的概率設(shè)為Pm=0.6,即產(chǎn)生一個隨機(jī)數(shù)r,r∈[0, 1],如果r

2.5 巡回

多個子種群領(lǐng)飛鳥和跟飛鳥依據(jù)2.3節(jié)和2.4節(jié)循環(huán)G次,利用其鄰域解,完成領(lǐng)飛鳥和跟飛鳥的充分開發(fā).

2.6 子種群信息交互

IMMBO算法采用多種群并行搜索,但隨著算法的執(zhí)行,子種群內(nèi)部個體失去多樣性,因此需要通過子種群之間的信息交互,產(chǎn)生更好的個體.鯨魚優(yōu)化算法(WOA)[23]是最優(yōu)個體引領(lǐng)搜索方向的算法,這是利用鯨魚可以通過螺旋上升過程中泡泡網(wǎng)圍攻以及隨機(jī)搜索獵物完成捕食過程.因此,設(shè)計離散鯨魚優(yōu)化算法(DWOA)完成子種群之間的信息交互.最優(yōu)個體存在于各子種群的領(lǐng)飛鳥中,因此,DWOA只對它們優(yōu)化,同時利用3種交叉策略模擬鯨魚的捕食過程.鯨魚圍攻和螺旋上升過程分別利用當(dāng)前個體和最優(yōu)個體進(jìn)行次序交叉和兩段交叉模擬,分別以50%的概率完成局部搜索,產(chǎn)生一個隨機(jī)數(shù)p,p∈[0, 1],若p<0.5,執(zhí)行次序交叉,否則執(zhí)行兩段交叉;隨機(jī)搜索獵物過程則利用當(dāng)前個體和種群中隨機(jī)個體進(jìn)行隨機(jī)交叉模擬完成全局搜索.3種交叉的具體操作如圖1～3所示,其中P1和P2為兩個父代個體,C1和C2為兩個子代交叉?zhèn)€體.

圖1 次序交叉操作

圖2 隨機(jī)交叉操作

圖3 兩段交叉操作

(1) 次序交叉(OX).

步驟1隨機(jī)選擇兩個交叉點(diǎn)r1和r2,且 1≤r1

步驟2把P1和P2中r1～r2的工件分別復(fù)制到C1和C2中的r1～r2位置.

步驟3把P1不包含在C2中的工件依次復(fù)制到C2; 把P2不包含在C1中的工件依次復(fù)制到C1.

步驟4將C1和C2中Cmax值較小的作為交叉結(jié)果.

(2) 隨機(jī)交叉(JBX).

步驟1構(gòu)造兩個子序列S1,S2.

步驟2把P1中對應(yīng)S1的元素復(fù)制到C1;把P2中對應(yīng)S2的元素復(fù)制到P2.

步驟3把P2中對應(yīng)S2的元素復(fù)制到C1;把P1中對應(yīng)的S1的元素復(fù)制到C2.

步驟4將C1和C2中Cmax值較小的作為交叉結(jié)果.

(3) 兩段交叉(TSX).

步驟1隨機(jī)選擇兩個交叉點(diǎn)r1和r2,且1≤r1

步驟2把P1中r1～r2的工件復(fù)制到子序列sub1;從P2中去除sub1中工件,剩余的工件作為子序列sub2.

步驟3把子序列sub1和sub2復(fù)制到C1,把子序列sub2和sub1復(fù)制到C2.

步驟4如果r<0.5,C1作為交叉結(jié)束,否則C2作為交叉結(jié)果.

在DWOA中,LS和全局搜索平衡至關(guān)重要.為達(dá)到更好的優(yōu)化效果,通過一個選擇概率Pb完成算法探索和開發(fā)的切換,Pb采用非線性的正弦函數(shù)替代WOA[23]中的線性函數(shù),由下式給出:

(6)

For 每個個體

如果p<0.5

如果r>Pb

種群最優(yōu)個體與當(dāng)前個體執(zhí)行次序交叉(OX)

否則

當(dāng)前個體與隨機(jī)選擇個體進(jìn)行隨機(jī)交叉(JBX)

End if

否則

種群最優(yōu)個體與當(dāng)前個體執(zhí)行兩段交叉(TSX)

End if

End for

2.7 LS能力增強(qiáng)

為了進(jìn)一步提高全局最優(yōu)個體的質(zhì)量,對其進(jìn)行LS.但最優(yōu)個體是經(jīng)過多次進(jìn)化所得,直接進(jìn)行LS可能進(jìn)入循環(huán)搜索,因此,首先對最優(yōu)個體進(jìn)行干擾,然后再執(zhí)行LS.LS算法流程圖如圖4所示.

圖4 局部搜索算法流程圖

2.8 種群多樣化控制

隨著IMMBO算法進(jìn)化,種群中個體失去多樣性,因此,為各子種群的領(lǐng)飛鳥設(shè)置一個年齡變量,可記錄其更新程度,年齡越大,說明更新能力越差.年齡變量初始值為0,如果個體更新,年齡變量清0,否則增加1,并與設(shè)置的最大年齡限制,即alimit比較,當(dāng)某個體年齡大于該值時,可能在它的鄰域循環(huán)搜索,此時,啟動種群多樣化控制機(jī)制,產(chǎn)生一個新的個體替換該個體.但隨機(jī)產(chǎn)生的個體質(zhì)量可能更差,導(dǎo)致算法收斂速度下降,而且被放棄的個體進(jìn)化了多代,必然攜帶較好個體信息,其鄰域可能就是更好的可行區(qū)域.為兼顧隨機(jī)性和質(zhì)量,對被放棄的個體執(zhí)行3次插入干擾,產(chǎn)生一個領(lǐng)域個體,但該鄰域個體很難保證質(zhì)量.為了找到較好的鄰域個體,使算法朝著期望的區(qū)域搜索,重復(fù)上述操作τ次,產(chǎn)生τ個鄰域個體,將其中最好的一個個體放入種群替換原個體.考慮新個體的質(zhì)量和算法效率,將τ設(shè)置為10.

3 仿真研究

3.1 仿真環(huán)境和算例

算法采用MATLAB R2016b 編寫,并在Intel(R) Core(TM) i5-9600KF/3.7 GHz/ 16.0 GB,系統(tǒng)為Windows 10的平臺運(yùn)行.

為了驗證實驗效果,選擇適用于帶SDST的流水或HFS問題的算例,即基于Ta的自適應(yīng)算例[24],通過測試該算例進(jìn)行參數(shù)調(diào)整及算法的有效性驗證.

3.2 參數(shù)調(diào)整

參數(shù)設(shè)置對于智能優(yōu)化算法性能影響較大,為了使IMMBO算法在最佳狀態(tài)下對HFS-SDST問題求解,需要對其參數(shù)進(jìn)行調(diào)整.參數(shù)調(diào)整通過測試中等規(guī)模的Ta42衍生的8個自適應(yīng)算例進(jìn)行,Ta42算例的工件數(shù)n為50,階段數(shù)m為10,每個階段的機(jī)器數(shù)有2種情況:3臺(P3)或者服從1～3臺(P13)之間的統(tǒng)一分布,同時準(zhǔn)備時間考慮4種情況,分別為平均加工時間的10%(SSD10)、50%(SSD50)、100%(SSD100)、125%(SSD125).根據(jù)上述每個階段機(jī)器數(shù)和準(zhǔn)備時間情況產(chǎn)生的8個自適應(yīng)算例記作:SSD10_P13_50、SSD50_P13_50、SSD100_P13_50、SSD125_P13_50、SSD10_P3_50、SSD50_P3_50、SSD100_P3_50和SSD125_P3_50.IMMBO算法中涉及參數(shù)較多,通過前期測試,可知對算法優(yōu)化效果影響較大的5個參數(shù)及其大致范圍.為了確定參數(shù)的值,采用正交實驗法對算法中的5個參數(shù)的4個水平進(jìn)行測試.5個參數(shù)分別為子種群個數(shù)Np、巡回次數(shù)G、 最大年齡alimit、破壞重建中的破壞程度d和最大進(jìn)化代數(shù)tmax.正交表如表1所示.

表1 正交實驗參數(shù)/水平表

如果對IMMBO算法的5個參數(shù)的4個水平全部組合進(jìn)行測試,需要進(jìn)行45=1 024 組實驗,但采用正交實驗法只需測試42=16組,即可為算法選出合適的參數(shù)值,顯然,用正交實驗法可以使參數(shù)選擇效率大幅度提高.16種參數(shù)組合及測試上述8個算例的結(jié)果如表2所示.

表2 L16(45)正交表和實驗結(jié)果

表2最后一列測試結(jié)果為每種參數(shù)組合測試8個算例,對每個算例算法獨(dú)立測試5次,共40次實驗測得的Cmax平均值.表3為5個參數(shù),4種水平的平均值以及標(biāo)準(zhǔn)偏差(SD),據(jù)此選擇參數(shù)的水平.4行中每一列的最小值所對應(yīng)的水平值,表示較好的參數(shù)水平值.SD為該參數(shù)各個水平的標(biāo)準(zhǔn)偏差, SD值越大,對算法的優(yōu)化效果影響越大, 表中最后一行為5個參數(shù)按照SD值降序排列.5個參數(shù)在不同水平的平均Cmax(AVG)的變化曲線如圖5所示,其中AVG最小的水平即為該參數(shù)的最佳設(shè)置值.

表3 參數(shù)等級及均值響應(yīng)

圖5 IMMBO算法中的5個參數(shù)在4個水平變化趨勢圖

由圖5和表3可以看出,alimit對算法的優(yōu)化效果影響最大,子種群個數(shù)Np的影響最小.因此,設(shè)置參數(shù)Np=15,d=5,alimit=20,G和tmax分別設(shè)為3和600.

3.3 算法各部分有效性測試

通過測試IMMBO的4個變體分別說明算法各部分的有效性.選擇32個自適應(yīng)算例進(jìn)行測試,即Ta算例(Ta32,Ta34, …, Ta46),自適應(yīng)考慮4種準(zhǔn)備時間且每個階段3臺機(jī)器情況.IMMBO的4個變體分別為:去掉領(lǐng)飛鳥鄰域搜索策略中的DC(IMMBO_NDC)、 去掉子種群交互機(jī)制的DWOA算法(IMMBO_NDWOA)、 去掉LS的算法(IMMBO_NLS)和去掉種群多樣化控制機(jī)制(IMMBO_NR).表4中所列出的值表示選擇不同準(zhǔn)備時間時,每個變體獨(dú)立運(yùn)行5次測試8個算例(8×5=40)的Cmax平均值,表達(dá)式為

表4 IMMBO算法4個變體測試P3情況均值響應(yīng)表

(7)

表4的同一組算例中,CAVG越大,說明去掉的對應(yīng)算子對優(yōu)化結(jié)果影響越大.可知,鄰域搜索中的DC和種群多樣化控制機(jī)制對算法優(yōu)化效果影響最大,子種群交互機(jī)制對算法的影響次之,LS對算法的影響最小.

3.4 算法性能測試

為了驗證IMMBO算法求解HFS-SDST問題的效果,將IMMBO和文獻(xiàn)[10]中求解同一問題的ILSMRLS、IMBO和DABC算法通過測試Ta32～Ta60的自適應(yīng)算例進(jìn)行比較,準(zhǔn)備時間和機(jī)器數(shù)同3.2節(jié)算例設(shè)計,總算例數(shù)目為15×4×2=120,每個算法獨(dú)立運(yùn)行5次測試所有算例,結(jié)果如表5所示.表5中所列出的值表示每個算法獨(dú)立運(yùn)行5次測試15個算例(15×5=75)的Cmax平均值,表達(dá)式為

表5 IMMBO/IMBO/DABC/ILSMRLS算法針對P13和P3算例的測試結(jié)果對比

(8)

表5中4個算法相比,可知, IMMBO算法對各種機(jī)器配置和準(zhǔn)備時間算例都有較好的優(yōu)化效果.表6為上述4個算法分別測試8個自適應(yīng)Ta算例的運(yùn)行時間.可以看出,測試相同算例時,4個算法的運(yùn)行時間由小到大依次是DABC、IMBO、ILSMRLS、IMMBO,雖然IMMBO所用時間稍長于IMBO 和ILSMRLS,但可以得到更好的優(yōu)化效果.圖6和圖7分別為4個算法測試算例Ta56的SSD125_P3_50和Ta60的SSD50_P13_50的收斂曲線.由圖可知,IMMBO算法與其他3個算法相比,無論是進(jìn)化前期的收斂速度還是后期的收斂精度都是較優(yōu)的.

表6 4個算法測試8個自適應(yīng)算例的運(yùn)行時間對比

圖7 算例Ta60中SSD50_P13_50的4個算法收斂曲線圖

4 結(jié)語

針對有較強(qiáng)工業(yè)背景的HFS-SDST問題,提出IMMBO算法,優(yōu)化調(diào)度目標(biāo)是找到使最大完成時間最短的工件在第1階段機(jī)器上的加工順序,即使Cmax最小的調(diào)度解.首先,采用MNEH初始化種群,并將其隨機(jī)分配到各子種群,子種群規(guī)模為3,由1個領(lǐng)飛鳥和2個跟飛鳥組成.然后采用多種群候鳥遷徙算法的各子種群獨(dú)立并行搜索和 DWOA算法實現(xiàn)子種群信息交互,同時加入LS和種群多樣化控制策略平衡算法的探索和開發(fā)能力.為了使算法在最佳狀態(tài)下求解HFS-SDST問題,針對IMMBO算法進(jìn)行參數(shù)調(diào)整和算法各部分的性能測試,為了驗證算法的有效性,與ILSMRLS、IMBO和DABC算法進(jìn)行比較.結(jié)果表明,IMMBO的優(yōu)化效果優(yōu)于其他算法,且在進(jìn)化前期所提算法有較快的收斂速度,后期能夠跳出局部最優(yōu).