基于改進多種群候鳥遷徙算法的混合流水車間調度

張素君, 楊文強, 顧幸生

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

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

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

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

1 HFS-SDST問題

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

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

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

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

Ck, πj, i=

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

(3)

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

其作業完成時間為

Ck, πj=minCk, πj, i

(4)

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

(5)

2 IMMBO

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

步驟1設置算法相關參數.利用MNEH算法初始化種群,并把最好的1/3 分到每個子種群作為其領飛鳥,剩下2/3個體隨機分配到各子種群,每個子種群包括兩個跟飛鳥.

步驟2保存本代最優個體.

步驟3子種群領飛鳥利用串行變鄰域搜索策略產生鄰域個體,若鄰域個體中最好的優于領飛鳥,替換領飛鳥.

步驟4子種群跟飛鳥利用并行變鄰域搜索策略產生鄰域個體,若鄰域個體中最好的優于該跟飛鳥,替換跟飛鳥,若跟飛鳥優于本群的領飛鳥,二者交換.

步驟5檢查是否達到巡回次數,若未達到,轉到步驟3,否則轉到步驟6.

步驟6各子種群領飛鳥利用離散鯨魚優化策略進行交叉,完成子種群之間的信息交互.

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

步驟8更新各子種群領飛鳥的年齡變量,若某子種群的領飛鳥年齡達到設定年齡限制,啟動多樣化控制機制,重新產生一個個體放入種群.

步驟9判斷算法迭代是否達到最大迭代次數,若未達到,轉到步驟2,否則,算法結束,輸出最優個體及其Cmax值.

2.1 編碼和解碼

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

2.2 初始化種群

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

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

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

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

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

2.3 子種群領飛鳥進化

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

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

輸入π; 輸出π

k=1

whilek<=3

switchk

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

如果Cmax(π′)

π=π′,k=1

否則

k=k+1

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

如果Cmax(π′)

π=π′,k=2

否則

k=k+1

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

如果Cmax(π′)

π=π′,k=3

否則

k=k+1

End switch

End while

2.4 子種群跟飛鳥進化

產生跟飛鳥鄰域個體的策略,要兼具鄰域個體的質量和多樣性,因此子種群中的跟飛鳥領域個體采用并行變鄰域搜索產生,即按照一定概率選擇插入或交換兩種鄰域之一產生跟飛鳥鄰域個體.在生產調度問題中,插入更易產生較好的鄰域個體,因此,設置選擇插入鄰域結構的概率設為Pm=0.6,即產生一個隨機數r,r∈[0, 1],如果r

2.5 巡回

多個子種群領飛鳥和跟飛鳥依據2.3節和2.4節循環G次,利用其鄰域解,完成領飛鳥和跟飛鳥的充分開發.

2.6 子種群信息交互

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

圖1 次序交叉操作

圖2 隨機交叉操作

圖3 兩段交叉操作

(1) 次序交叉(OX).

步驟1隨機選擇兩個交叉點r1和r2,且 1≤r1

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

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

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

(2) 隨機交叉(JBX).

步驟1構造兩個子序列S1,S2.

步驟2把P1中對應S1的元素復制到C1;把P2中對應S2的元素復制到P2.

步驟3把P2中對應S2的元素復制到C1;把P1中對應的S1的元素復制到C2.

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

(3) 兩段交叉(TSX).

步驟1隨機選擇兩個交叉點r1和r2,且1≤r1

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

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

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

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

(6)

For 每個個體

如果p<0.5

如果r>Pb

種群最優個體與當前個體執行次序交叉(OX)

否則

當前個體與隨機選擇個體進行隨機交叉(JBX)

End if

否則

種群最優個體與當前個體執行兩段交叉(TSX)

End if

End for

2.7 LS能力增強

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

圖4 局部搜索算法流程圖

2.8 種群多樣化控制

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

3 仿真研究

3.1 仿真環境和算例

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

為了驗證實驗效果,選擇適用于帶SDST的流水或HFS問題的算例,即基于Ta的自適應算例[24],通過測試該算例進行參數調整及算法的有效性驗證.

3.2 參數調整

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

表1 正交實驗參數/水平表

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

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

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

表3 參數等級及均值響應

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

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

3.3 算法各部分有效性測試

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

表4 IMMBO算法4個變體測試P3情況均值響應表

(7)

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

3.4 算法性能測試

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

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

(8)

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

表6 4個算法測試8個自適應算例的運行時間對比

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

4 結語

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