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

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

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

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

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

1 HFS-SDST問(wèn)題

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

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

若第1階段和階段k(k=2, 3, …,m)的第i(i=1, 2, …,Mk)臺(tái)機(jī)器沒(méi)有加工過(guò)其他工件,則工件πj的完成時(shí)間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臺(tái)機(jī)器上的作業(yè)完成時(shí)間和作業(yè)時(shí)間;Sk, πj, πj為工件πj在k階段的準(zhǔn)備時(shí)間.

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

Ck, πj, i=

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

(3)

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

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

Ck, πj=minCk, πj, i

(4)

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

(5)

2 IMMBO

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

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

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

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

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

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

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

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

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

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

2.1 編碼和解碼

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

2.2 初始化種群

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

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

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

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

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

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

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

如果Cmax(π′)

π=π′,k=3

否則

k=k+1

End switch

End while

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

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

2.5 巡回

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

2.6 子種群信息交互

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

圖1 次序交叉操作

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

圖3 兩段交叉操作

(1) 次序交叉(OX).

步驟1隨機(jī)選擇兩個(gè)交叉點(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)造兩個(gè)子序列S1,S2.

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

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

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

(3) 兩段交叉(TSX).

步驟1隨機(jī)選擇兩個(gè)交叉點(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)化效果,通過(guò)一個(gè)選擇概率Pb完成算法探索和開(kāi)發(fā)的切換,Pb采用非線性的正弦函數(shù)替代WOA[23]中的線性函數(shù),由下式給出:

(6)

For 每個(gè)個(gè)體

如果p<0.5

如果r>Pb

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

否則

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

End if

否則

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

End if

End for

2.7 LS能力增強(qiáng)

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

圖4 局部搜索算法流程圖

2.8 種群多樣化控制

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

3 仿真研究

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

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

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

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

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

表1 正交實(shí)驗(yàn)參數(shù)/水平表

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

表2 L16(45)正交表和實(shí)驗(yàn)結(jié)果

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

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

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

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

3.3 算法各部分有效性測(cè)試

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

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

(7)

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

3.4 算法性能測(cè)試

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

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

(8)

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

表6 4個(gè)算法測(cè)試8個(gè)自適應(yīng)算例的運(yùn)行時(shí)間對(duì)比

圖7 算例Ta60中SSD50_P13_50的4個(gè)算法收斂曲線圖

4 結(jié)語(yǔ)

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