含忽略工序和不相關(guān)機(jī)的混合流水車間調(diào)度

軒華，樊銀格，李冰

（鄭州大學(xué) 管理工程學(xué)院，河南 鄭州 450001）

含忽略工序的混合流水車間調(diào)度（hybrid flowshop scheduling with missing operation，HFSMO）在煉鋼、不銹鋼、塑料等制造工業(yè)較為常見。在經(jīng)典混合流水車間調(diào)度問題中，通常假定工件經(jīng)所有工序處理，但在實際生產(chǎn)中，工件會忽略某些工序，即一些工件可能不經(jīng)某些工序處理，如煉鋼-連鑄生產(chǎn)中，由電弧爐或轉(zhuǎn)爐生產(chǎn)的鋼水要在高溫下經(jīng)精煉和連鑄工序進(jìn)行加工，不同的鋼種對生產(chǎn)路線的要求會有所不同，像Q235普通碳鋼要略過RH（Ruhrstahl-Hausen）真空精煉爐階段[1]?？紤]到并行機(jī)的新舊程度或異構(gòu)性，由此衍生出本文所研究的帶不相關(guān)并行機(jī)的HFSMO。由于HFS (hybrid flowshop scheduling)問題是NP-hard[2]，帶不相關(guān)并行機(jī)的HFSMO 是HFS 問題的擴(kuò)展且其更為復(fù)雜，它不僅要確定工件的處理序列，還需確定工件在每道未忽略工序的機(jī)器分配，所以本文研究的更復(fù)雜的帶不相關(guān)并行機(jī)的HFSMO 也是NP-hard。

目前，已有不少學(xué)者研究HFSMO。就兩道工序的HFSMO 而言，Tseng 等[3]研究了工序1 有一臺機(jī)器且工序2 有兩臺同構(gòu)機(jī)的情況，假定工序1 可忽略，提出了一種啟發(fā)式算法以最小化最大完工時間。就含同構(gòu)并行機(jī)的多工序HFSMO 而言，為最小化最大完工時間，Saravanan 等[4-5]提出了遺傳算法、模擬退火算法和粒子群算法，Marichelvam等[6]基于遺傳算法和分散搜索算法提出了一種改進(jìn)的混合遺傳分散搜索算法，Dios 等[7-8]提出了一些分派規(guī)則和改進(jìn)啟發(fā)式來求解該問題；為最小化平均拖期，Saravanan 等[9]提出了遺傳算法與模擬退火算法；為最小化平均滯留時間、總提前、總拖期和關(guān)鍵機(jī)器跳過率的加權(quán)和，Li 等[10]針對鐵水系統(tǒng)提出了一種改進(jìn)離散人工蜂群算法；為了最小化最大完工時間、總等待時間以及處理時間與標(biāo)準(zhǔn)處理時間的偏差之和，Long 等[1]針對煉鋼-連鑄生產(chǎn)系統(tǒng)提出了一種改進(jìn)遺傳算法。

目前，已有不少學(xué)者在不相關(guān)并行機(jī)環(huán)境下研究HFS 問題。針對單目標(biāo)問題，Meng 等[11]研究了節(jié)能HFS，并提出改進(jìn)的遺傳算法以最小化機(jī)器閑置消耗。為最小化最大完工時間，Qin 等[12]研究了批量調(diào)度HFS，提出兩階段蟻群算法；羅函明等[13]針對多工序HFS，提出離散布谷鳥算法；軒華等[14]針對帶有限緩沖HFS，提出基于遺傳算法和禁忌搜索的混合啟發(fā)式算法。針對多目標(biāo)問題，Zhou 等[15]研究了帶模糊處理時間的HFS，設(shè)計差分進(jìn)化算法以最小化總加權(quán)交付損失和總能耗。Yu 等[16]針對帶機(jī)器能力約束和依賴加工序列設(shè)置時間的HFS，提出帶多重解碼框架的進(jìn)化算法以最小化總拖期和總設(shè)置時間。Zhou 等[17]研究了帶節(jié)能區(qū)間的HFS，提出新的帝國競爭算法以解決以總能耗和最大完工時間為目標(biāo)的雙目標(biāo)問題。

就目前查閱的文獻(xiàn)而言，HFSMO 已引起眾多學(xué)者的關(guān)注，既有的研究聚焦于同構(gòu)機(jī)環(huán)境?，F(xiàn)有的帶不相關(guān)并行機(jī)的HFS 不考慮帶忽略工序特性，關(guān)于不相關(guān)并行機(jī)環(huán)境下HFSMO 問題的研究尚缺乏，還有待進(jìn)一步探討。就優(yōu)化算法而言，文獻(xiàn)[1,3-10] 的研究說明了進(jìn)化算法求解HFSMO 問題有較大潛力，如文獻(xiàn)[4,9]利用單獨的遺傳算法和模擬退火算法求解含同構(gòu)機(jī)的最大完工時間問題?；旌纤惴ㄍǔＤ軘U(kuò)大搜索的范圍，提高解的質(zhì)量，因此關(guān)于混合算法求解這類問題的研究還有待進(jìn)一步探討。候鳥優(yōu)化（migrating birds optimization，MBO）算法作為一種新興的群智能優(yōu)化算法，已廣泛應(yīng)用于生產(chǎn)調(diào)度領(lǐng)域，如流水車間調(diào)度[18-21]、混合流水車間調(diào)度[22-23]和柔性作業(yè)車間調(diào)度[24-26]，它最早是由Duman 等[27]提出并應(yīng)用于二次分配問題。因此，本文結(jié)合全局搜索、自適應(yīng)遺傳算法和候鳥優(yōu)化提出一種遺傳候鳥優(yōu)化算法（genetic migrating birds optimization algorithm,GMBOA）解決含不相關(guān)并行機(jī)的HFSMO，通過仿真實驗驗證所提算法的有效性和可行性。

1 問題描述與建模

1.1 問題描述

含不相關(guān)并行機(jī)的HFSMO 問題包括來自集合J={1,2,···,n}且將在h道工序上處理的n個工件，每道工序s有ms臺不相關(guān)并行機(jī)，即對于每道工序，工件在ms臺并行機(jī)上的處理時間相互獨立，僅取決于工件與機(jī)器的匹配程度。每個工件可能會忽略某些工序。每臺機(jī)器一次只能處理一個工件，而每個工件一次至多在一臺機(jī)器進(jìn)行處理。調(diào)度目標(biāo)是確定工件處理序列和機(jī)器分配，以最小化最大完工時間。所研究問題的其他假設(shè)如下：

1）工件的開工應(yīng)在其釋放時間之后；

2）機(jī)器準(zhǔn)備時間與工件順序無關(guān)，且包含在處理時間中；

3）所有機(jī)器在整個計劃時間段內(nèi)連續(xù)可用；

4）工件一旦在某臺機(jī)器上開始處理后，不允許中斷，直至該工序完成；

5）工件處理無優(yōu)先級要求；

6）工序之間的轉(zhuǎn)移時間忽略不計；

7）相鄰工序之間的緩沖區(qū)容量無限。

1.2 模型構(gòu)建

由前述可知，每個工件j實際訪問的總工序數(shù)Oj≤h，雖然工件需經(jīng)h道工序完成其處理任務(wù)，但部分工件j的處理略過了h?Oj道工序，即這些工件未經(jīng)h?Oj道工序處理而直接進(jìn)入后續(xù)工序。含不相關(guān)并行機(jī)的HFSMO 模型如下：

所研究問題的目標(biāo)是滿足所有約束條件下最小化最大完工時間Cmax，即

式中：Cjh表示工件j（j=1,2,···,n）在工序h的完工時間。式(2)通過檢查工件在最終工序h的完工時間，確定最大完工時間。

式中：ms為工序s（s=1,2,···,h）可利用的機(jī)器數(shù)；F為一個足夠大的數(shù)；Pjks為工件j在工序s的機(jī)器k（k=1,2,···,ms）上的處理時間；Wjs為二元參數(shù)，若工件j在工序s上處理，其值為1，否則為0；Bjs表示工件j在工序s的開工時間；Xjks為二元變量，若工件j在工序s的機(jī)器k上處理，其值為1，否則為0。式(3)定義了工件在每道工序的完工時間，若工件j未在工序s處理，則它在該工序的完工時間為它在緊前未忽略工序的完工時間。

該約束確保每個工件在任一工序只能分派到一臺機(jī)器進(jìn)行處理。

Cjs≤Bj,s+1,s∈{1,2,···,h?1},?j

該約束說明了每個工件只完完成前一工序的處理任務(wù)后方可開始下一道工序的處理。

Bj1≥Rj,?j

式中Rj為工件j的釋放時間。該約束描述了工件只有到達(dá)生產(chǎn)系統(tǒng)才可開始處理。

式中：Zjiks為二元變量，若工件i和j在工序s的機(jī)器k上處理且工件j早于工件i，其值為1，否則為0。這兩個約束表示：同一道工序分派在同一臺機(jī)器處理的兩個工件之間的優(yōu)先級關(guān)系，若Zjiks=0且Wjs=Wis=1，約束式(4)描述了工件j在工序s的機(jī)器k上的開工時間必須在工件i的完工時間之后，若Zjiks=1且Wjs=Wis=1，約束式(5)描述了工件i在工序s的機(jī)器k上的開工時間必須在工件j的完工時間之后。

約束式(6)、(7)定義了變量取值范圍。

2 遺傳候鳥優(yōu)化算法

遺傳算法已廣泛用于求解HFSMO 問題，為使遺傳算法有效求解含不相關(guān)并行機(jī)的HFSMO 問題，設(shè)計基于機(jī)器號的編碼方案，采用考慮機(jī)器處理時間的全局搜索和隨機(jī)程序生成初始種群以提高初始解的質(zhì)量，設(shè)計自適應(yīng)更新策略以計算交叉概率 ξ及變異概率 ψ，以此執(zhí)行交叉和變異操作。最后，引入結(jié)合鄰域搜索的候鳥優(yōu)化算法以擴(kuò)大遺傳算法解的鄰域搜索范圍，從而獲得較好的近優(yōu)解。

2.1 編碼、解碼和適應(yīng)度選擇

含不相關(guān)并行機(jī)的HFSMO 需確定工件在每道工序的機(jī)器分配，因此設(shè)計基于機(jī)器號的整數(shù)編碼方案以表述機(jī)器分配序列 σ?？紤]到HFS 的多工序處理需求，令每個工件所忽略的工序數(shù)不超過h?2，根據(jù)忽略工序比例p，隨機(jī)產(chǎn)生每個工件的未忽略工序信息序列 τ，如圖1（n=5,h=5和p=0.6），其中表示工件j在階段s的工序；然后基于 τ生成相應(yīng)工件的機(jī)器號，為平衡并行機(jī)器的負(fù)荷，令其值滿足[1,ms]的均勻分布，從而形成長度為n·h·(1?p)的一個染色體，其中每個元素（即工序位上的數(shù)值）為對應(yīng)工件所在工序分配的機(jī)器號。

圖1 未忽略工序信息序列Fig.1 Information sequence of unmissing operations

初始化種群時，由于每道工序所含的機(jī)器為不相關(guān)并行機(jī)，考慮不同的機(jī)器處理同一工件的時間不同，而最大完工時間與工件的處理時間相關(guān)。因此，基于張國輝等[28]的研究提出考慮處理時間的全局搜索以產(chǎn)生一個個體，而其他個體則由隨機(jī)程序生成。令數(shù)組θ={ps11,ps21,···,,ps12,···,,ps1h,ps2h,···,}為記錄從工序1 到工序h的每臺機(jī)器的累計處理時間的一維數(shù)組，其初始值均設(shè)為0，全局搜索從任一工件j開始，對它的第一道未忽略工序u，將可利用并行機(jī)的工件處理時間分別與數(shù)組 θ內(nèi)該機(jī)器位置的數(shù)值相加，即對k=1,2,···,mu，計算{Pjku+psku}，從中選擇累計處理時間最短的機(jī)器k′作為工件j在工序u所分配的機(jī)器，將該機(jī)器號填入個體內(nèi)工序位(h(1?p)(j?1)+1)，令psuk′=min{Pjku+psku}，更新數(shù)組θ；然后，對工件j的第2,3,···,h(1?p)道工序重復(fù)上述過程，從而完成該工件所有工序的機(jī)器分配。接著，再從剩余工件集內(nèi)隨機(jī)選擇一個工件執(zhí)行上述過程，直至完成所有工件未忽略工序的機(jī)器分配。結(jié)合隨機(jī)程序產(chǎn)生的(e?1)個個體共同構(gòu)成了如圖2 所示的種群規(guī)模為e的初始種群。

圖2 初始種群Fig.2 Initial population

為計算最大完工時間，需為分配至同一臺機(jī)器的工件進(jìn)行排序，為此，設(shè)計了基于最短處理時間的解碼方案，即對于機(jī)器分配序列 σ，當(dāng)s=1時，將分派到在同一臺機(jī)器處理的工件按照最短處理時間規(guī)則進(jìn)行排序，當(dāng)s>1時，對同一臺機(jī)器上處理的工件采用先到先加工規(guī)則生成處理序列，然后基于最早空閑機(jī)器原則依次將各工件安排在所分配機(jī)器。對于工件的忽略工序，則按照約束式(3)確定其在忽略工序的完工時間。

本文的目標(biāo)是最小化最大完工時間，故將適應(yīng)度函數(shù)表示為目標(biāo)函數(shù)的倒數(shù)，即個體g的適應(yīng)度函數(shù)為F(g)=1/Cmax(g)。采用輪盤賭選擇法，個體適應(yīng)度值越大，被選擇的概率也越大。

2.2 交叉操作

采用單點交叉和均勻兩點交叉兩種方式執(zhí)行交叉操作。在0 和1 中隨機(jī)生成一個整數(shù)v，當(dāng)v=0時，執(zhí)行單點交叉，即隨機(jī)選擇兩個父代個體E1和E2，隨機(jī)生成一個工序位x(1≤x≤n·h·(1?p))，交換E1和E2中所選工序位x的機(jī)器號，保持其他工序位的機(jī)器號不變，從而生成子代個體D1和D2，如圖3。當(dāng)v=1時，執(zhí)行均勻兩點交叉，首先，隨機(jī)選擇兩個父代個體E1和E2，隨機(jī)生成兩個工序位x和y(1≤x

圖3 單點交叉Fig.3 Single-point crossover

圖4 均勻兩點交叉（q=1）Fig.4 Uniform two-point crossover（q=1）

采用自適應(yīng)更新策略確定交叉概率ξ，用以確定是否執(zhí)行上述交叉操作，計算如下[29]：

式中：λ為當(dāng)前迭代數(shù)；β為最大迭代數(shù)；Favg為當(dāng)前種群的平均適應(yīng)度值。

2.3 變異操作

變異操作是根據(jù)變異概率通過改變父代個體的機(jī)器號以產(chǎn)生子代個體的過程。本文提出了基于隨機(jī)機(jī)器選擇的單點變異和基于機(jī)器最短處理時間的多點變異兩種方式。

1）基于隨機(jī)機(jī)器選擇的單點變異

從父代個體E1中隨機(jī)選擇一個工序位x(1≤x≤n·h·(1?p))，將該工序位的機(jī)器號重新在[1,ms]之間隨機(jī)生成，如圖5。

圖5 基于隨機(jī)機(jī)器選擇的單點變異Fig.5 Single point mutation based on random machine selection

2）基于機(jī)器最短處理時間的多點變異

推廣Chang 等[29]的研究，提出基于機(jī)器最短處理時間的多點變異操作。從父代個體E1依次取出工序位x的機(jī)器號，比較從區(qū)間[0,1]生成的隨機(jī)數(shù)w與變異概率 ψ，若w<ψ，則從工序位x可利用的并行機(jī)中選擇處理時間最短的機(jī)器替換原有機(jī)器號，否則，保持原有機(jī)器號不變，對個體內(nèi)所有工序位完成上述操作后，生成新個體D1，如圖6。

圖6 基于機(jī)器最短處理時間的多點變異Fig.6 Multi-point mutation based on the shortest processing time of the machine

自適應(yīng)變異概率ψ由式(8)確定：

2.4 基于3 種鄰域搜索結(jié)構(gòu)的候鳥優(yōu)化

為提高算法的搜索能力，進(jìn)一步改善遺傳算法解的質(zhì)量，設(shè)計引入基于工件、機(jī)器和工序位的3 種鄰域搜索結(jié)構(gòu)的候鳥優(yōu)化算法。

1）鄰域搜索結(jié)構(gòu)N1

隨機(jī)選擇一個工序u，從在該工序處理的工件集中隨機(jī)生成兩個工件 π1和 π2，將它們在該工序處理的機(jī)器號進(jìn)行交換，重復(fù)該過程直至達(dá)到最大循環(huán)次數(shù)Lmax。

2）鄰域搜索結(jié)構(gòu)N2

從機(jī)器集中尋找處理工件數(shù)超過兩個的機(jī)器，分別計算每臺機(jī)器上工件處理時間之和，從中獲取具有最大總處理時間的機(jī)器k′，進(jìn)而得到它對應(yīng)的工序u，從該機(jī)器處理的工件集中選取處理時間最長的工件 π，將 min{Pπku}(k=1,2,···,mu)對應(yīng)的機(jī)器作為該工件分配的機(jī)器。

3）鄰域搜索結(jié)構(gòu)N3

隨機(jī)生成一個工序位x，確定它所對應(yīng)的工件π=和工序u=x?π·h·(1?p)，將該工序位的機(jī)器號依次設(shè)置為1,2,···,mu，分別計算相應(yīng)個體的適應(yīng)度值，從中選取適應(yīng)度值最大的機(jī)器號填入該工序位，重復(fù)該過程直至達(dá)到最大循環(huán)次數(shù) ηmax。

引入上述鄰域搜索結(jié)構(gòu)執(zhí)行候鳥優(yōu)化算法，具體步驟如下：

1）參數(shù)初始化。設(shè)置Lmax、ηmax以及候鳥優(yōu)化最大迭代數(shù) γ，巡回數(shù)Gmax，令=1，G1=1，α=1，候鳥種群規(guī)模為 δ。

2）初始種群生成。設(shè)計初始種群由3 部分構(gòu)成：①對每個工件的未忽略工序，從可利用的并行機(jī)中選擇工件處理時間最短的機(jī)器作為該工件分配的機(jī)器，從而產(chǎn)生一個個體；②應(yīng)用前述全局搜索方法產(chǎn)生 50%(δ?1)個個體；③從GA 解中選取最好的 50%(δ?1)個個體。從 δ個個體中選取最大完工時間最小的個體作為領(lǐng)飛鳥，其余均為跟飛鳥，若跟飛鳥與領(lǐng)飛鳥相同，則將領(lǐng)飛鳥通過基于機(jī)器最短處理時間的多點變異或鄰域搜索結(jié)構(gòu) N1(Lmax=2)產(chǎn)生新跟飛鳥；若新跟飛鳥與其余跟飛鳥相同，則對新跟飛鳥繼續(xù)應(yīng)用鄰域搜索結(jié)構(gòu) N1進(jìn)行更新，直至產(chǎn)生與其余跟飛鳥不同的新跟飛鳥。

3）領(lǐng)飛鳥進(jìn)化。隨機(jī)產(chǎn)生[1,6]之間的一個整數(shù)r，若r=1，令Lmax=2，對領(lǐng)飛鳥執(zhí)行 N1；若r=2，則執(zhí)行 N2；若r=3，令ηmax=1，執(zhí)行 N3；若r=4，令Lmax=4，執(zhí)行 N1；若r=5，令ηmax=2，執(zhí)行N3；若r=6，令Lmax=6，執(zhí)行 N1。該過程往復(fù)o次產(chǎn)生領(lǐng)飛鳥的o個鄰域解，若其中的最佳解優(yōu)于當(dāng)前領(lǐng)飛鳥，則更新領(lǐng)飛鳥，取其余(o?1)個鄰域解中的最佳解加入共享鄰域解集XL和XR。

4）右側(cè)跟飛鳥進(jìn)化。對右側(cè)隊列中每個個體g，執(zhí)行與3）相同的鄰域搜索過程產(chǎn)生(o?1)個鄰域解，構(gòu)成集合DR，找到XR∪DR內(nèi)的最佳解，若其優(yōu)于當(dāng)前解，則更新跟飛鳥，清空XR，從XR∪DR未用的解集中選擇最好的鄰域解加入XR。

5）左側(cè)跟飛鳥進(jìn)化。對左側(cè)隊列中每個個體g，仍采用與3）相同的鄰域搜索過程產(chǎn)生(o?1)個鄰域解，構(gòu)成集合DL，若XL∪DL內(nèi)最佳解優(yōu)于當(dāng)前解，則更新跟飛鳥，清空XL，將XL∪DL未用的解集中最好的鄰域解加入XL。

6）G1=G1+1，若G1

7）領(lǐng)飛鳥更新。若 α=1，將左側(cè)隊列的第一個跟飛鳥作為新領(lǐng)飛鳥，將原領(lǐng)飛鳥移至左側(cè)隊列末端，令 α=0；否則，將右側(cè)隊列的第一個跟飛鳥作為新領(lǐng)飛鳥，把原領(lǐng)飛鳥移至右側(cè)隊列末端，令 α=1。

2.5 遺傳候鳥優(yōu)化算法流程

首先，考慮本文研究的問題是含不相關(guān)機(jī)的HFSMO，其不僅與工件的處理序列有關(guān)，還與工件在每道工序的機(jī)器分配相關(guān)，因此本文設(shè)計基于機(jī)器號的編碼方案，在解碼時采用最短處理時間和先進(jìn)先出規(guī)則確定工件處理序列；采用考慮機(jī)器處理時間的全局搜索產(chǎn)生一個個體，用隨機(jī)程序生成剩余(e?1)個個體以生成種群規(guī)模為e的初始種群；計算適應(yīng)度，根據(jù)輪盤賭法選擇個體生成新種群；對新種群根據(jù)自適應(yīng)更新策略計算交叉概率 ξ及變異概率 ψ，以此執(zhí)行交叉和變異操作，得到遺傳進(jìn)化后的最佳解并記錄歷史最佳解。最后，當(dāng)最佳解T次沒變時，按照基于3 種鄰域搜索結(jié)構(gòu)的候鳥優(yōu)化產(chǎn)生新解，若新解優(yōu)于歷史最佳解，則更新歷史最佳解，否則保持原解不變，重復(fù)上述過程直至滿足算法的停止標(biāo)準(zhǔn)。

綜上所述，所研究的GMBOA 執(zhí)行如下：

1）設(shè)置種群規(guī)模e，最大迭代數(shù) β和累計數(shù)T，令Z?=F，λ=1，t=1；

2）若 λ>β或CPU 達(dá)到最大運行時間，程序停止，輸出最佳解；否則，執(zhí)行3）；

3）結(jié)合隨機(jī)程序和全局搜索產(chǎn)生初始種群；

4）計算每個個體的適應(yīng)度值，使用輪盤賭選擇法獲取適應(yīng)度值高的個體；

5）根據(jù)交叉概率ξ，從單點交叉和均勻兩點交叉2 種方式隨機(jī)選擇1 種生成新個體；

6）根據(jù)變異概率 ψ，隨機(jī)執(zhí)行基于隨機(jī)機(jī)器選擇的單點變異或基于機(jī)器最短處理時間的多點變異；

7）若當(dāng)前迭代得到的最佳解Zλ≠Z?，Z?=min{Zλ,Z?}，t=1，λ=λ+1，轉(zhuǎn)至2）；否則，t=t+1，執(zhí)行8）；

8）若t=T，執(zhí)行9），否則，λ=λ+1，轉(zhuǎn)至2）；

9）調(diào)用候鳥優(yōu)化算法，若得到的最佳解優(yōu)于Z?，更新Z?，否則，保留Z?不變；t=1，λ=λ+1，轉(zhuǎn)至2）。

3 仿真實驗

本文所提的遺傳候鳥優(yōu)化算法將全局搜索、自適應(yīng)遺傳算法和候鳥優(yōu)化相結(jié)合，為了驗證所提出的算法性能，從傳統(tǒng)算法、與其他算法結(jié)合的混合算法、解碼規(guī)則、已發(fā)表的文獻(xiàn)的算法4 個角度選擇傳統(tǒng)遺傳算法(traditional genetic algorithm,TGA)，結(jié)合3 種領(lǐng)域搜索結(jié)構(gòu)候鳥優(yōu)化算法(migrating birds optimization &neighborhood search,MBO&NS)、基于最長處理時間規(guī)則解碼的遺傳候鳥優(yōu)化算法(genetic migrating birds optimization algorithm L,GMBOAL)、結(jié)合局域搜索的自適應(yīng)遺傳算法(adaptive genetic algorithm &local search,AGA&LS)與文獻(xiàn)[30]的改進(jìn)人工蜂群算法(improved artificial bee colony,IDABC)進(jìn)行對比。采用Matlab R2014b 進(jìn)行編程，在CPU 為Inter Core i5-5200U，內(nèi)存為4 GB，主頻2.2 GHz 的微機(jī)上運行。

3.1 參數(shù)設(shè)置

為公平比較TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 這6 種算法，TGA中的 ξ 和 ψ的取值通過仿真實驗得到最佳的一組設(shè)置，即 ξ=0.8 和 ψ=0.2；GMBOAL、AGA&LS 和GMBOA 中的 ξmax、ξmin、ψmax和 ψmin的取值是通過仿真實驗得到最佳的一組設(shè)置，即ξmax=0.9、ξmin=0.5、ψmax=0.2 和ψmin=0.02；參考文獻(xiàn)[22]，并經(jīng)過仿真實驗測試GMBOA 中的 δ=31、γ=10、Gmax=10、o=3；基于GA 的4 種算法和IDABC 的種群規(guī)模e=100；由于MBO&NS 的種群規(guī)模必須為奇數(shù)，所以其種群規(guī)模e=101；IDABC 的參數(shù)與文獻(xiàn)[30]的設(shè)置相同，最大迭代數(shù) β=100，最大CPU 時間為720 s；考慮到GA 的運行時間較短，將MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 的停止時間設(shè)為TGA 運行100 次所需時間。

問題產(chǎn)生如下：n={20,30,40,50,80,100,120,150}，h={5,10,15,20}，ms=5。借鑒Dios 等[7-8]關(guān)于忽略工序比例的設(shè)定，將本文的忽略工序比例p分別取為20%、40%和60%。每個工件在同一道工序不同機(jī)器上的處理時間Pjks不同且滿足[1,99]之間的均勻分布。

3.2 數(shù)據(jù)實驗與結(jié)果分析

參數(shù){n,h,p}的不同組合產(chǎn)生96 組問題規(guī)模，每種規(guī)模隨機(jī)運行10 個實例，取10 次測試結(jié)果的平均值作為對應(yīng)規(guī)模問題的測試結(jié)果。

定義相對偏差為

由于本文所提的算法迭代100 次的CPU 時間略長，為在較短的運行時間內(nèi)測試所提算法的有效性，兼顧算法對比的公平性，將TGA 迭代100次所需的時間作為對比算法MBO&NS、GMBOAL、AGA&LS、IDABC 和所提出算法GMBOA 的停止條件，以此對比算法的性能，所以表1～6 列出的CPU 時間為TGA 迭代100 次的時間。表1～6 列出了5 種算法求解不同規(guī)模問題的實驗結(jié)果。

表1 忽略工序比例為20%時中小規(guī)模問題的測試結(jié)果Table 1 Testing results for small and medium scale problems with the proportion 20% of missing operations

續(xù)表 1

表2 忽略工序比例為20%時大規(guī)模問題測試結(jié)果Table 2 Testing results for large scale problems with the proportion 20% of missing operations

表3 忽略工序比例為40%時中小規(guī)模問題測試結(jié)果Table 3 Testing results for small and medium scale problems with the proportion 40% of missing operations

續(xù)表 3

表4 忽略工序比例為40%時大規(guī)模問題測試結(jié)果Table 4 Testing results for large scale problems with the proportion 40% of missing operations

表5 忽略工序比例為60%時中小規(guī)模問題測試結(jié)果Table 5 Testing results for small and medium scale problems with the proportion 60% of missing operations

續(xù)表 5

表6 忽略工序比例為60%時大規(guī)模問題測試結(jié)果Table 6 Testing results for large scale problems with the proportion 60% of missing operations

從表1～6 可知：

1）當(dāng)p=20%時，對于中小規(guī)模問題，在平均CPU 時間75.63 s 內(nèi)，由TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 得到的平均目標(biāo)值分別為479.1、478.4、403.2、391.8、412.3、381.5。GMBOA 得到的目標(biāo)值較TGA 改進(jìn)25.86%，較MBO&NS 改進(jìn)25.30%，較GMBOAL 改進(jìn)6.46%，較AGA&LS 改進(jìn)3.05%，較IDABC 改進(jìn)8.91%。

對于大規(guī)模問題，在平均CPU 時間166.81 s內(nèi)，由TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 得到的平均目標(biāo)值分別為917.1、885.0、761.6、738.7、740.9、723.1。GMBOA 的目標(biāo)值較TGA 改進(jìn)26.68%，較MBO&NS 改進(jìn)22.84%，較GMBOAL 改進(jìn)6.05%，較AGA&LS 改進(jìn)2.00%，較IDABC 改進(jìn)3.34%。

從平均性能來看，對于不同規(guī)模問題，在總平均時間121.22 s 內(nèi)，TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 的平均目標(biāo)值分別為698.1、681.7、582.4、565.3、576.6、552.3。GMBOA的目標(biāo)值較TGA 改進(jìn)26.27%，較MBO&NS 改進(jìn)24.07%，較GMBOAL 改進(jìn)6.26%，較AGA&LS 改進(jìn)2.53%，較IDABC 改進(jìn)6.13%。整體來看，在相同CPU 時間內(nèi)，GMBOA 的表現(xiàn)明顯優(yōu)于TGA、MBO&NS、GMBOAL、AGA&LS、IDABC。

2）當(dāng)p=40%時，對于中小規(guī)模問題，在平均CPU 時間70.15 s 內(nèi)，由TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 得到的平均目標(biāo)值分別為368.3、363.1、305.9、303.9、320.1、293.0。GMBOA 的目標(biāo)值較TGA 改進(jìn)26.12%，較MBO&NS 改進(jìn)23.53%，較GMBOAL 改進(jìn)4.83%，較AGA&LS 改進(jìn)3.82%，較IDABC 改進(jìn)9.34%。

對于大規(guī)模問題，在平均CPU 時間151.07 s內(nèi)，由TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 得到的平均目標(biāo)值分別為685.0、658.2、561.7、551.8、555.8、537.5。GMBOA 的目標(biāo)值較TGA 改進(jìn)26.74%，較MBO&NS 改進(jìn)22.90%，較GMBOAL 改進(jìn)5.04%，較AGA&LS 改進(jìn)3.08%、較IDABC 改進(jìn)4.39%。

從平均性能來看，對于不同規(guī)模問題，在總平均時間110.61 s 內(nèi)，TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 的平均目標(biāo)值分別為526.7、510.7、433.8、427.9、438.0、415.3。GMBOA的目標(biāo)值較TGA 改進(jìn)26.43%，較MBO&NS 改進(jìn)23.22%，較GMBOAL 改進(jìn)4.94%，較AGA&LS 改進(jìn)3.45%，較IDABC 改進(jìn)6.87%。因此，GMBOA比TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 產(chǎn)生了較好的解。

3）當(dāng)p=60%時，對于中小規(guī)模問題，在平均CPU 時間63.86 s 內(nèi)，由TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 得到的平均目標(biāo)值分別為264.2、251.9、212.2、216.8、233.5、207.5。GMBOA 的目標(biāo)值較TGA 改進(jìn)27.12%，較MBO&NS 改進(jìn)20.30%，較GMBOAL 改進(jìn)2.39%，較AGA&LS 改進(jìn)5.09%，較IDABC 改進(jìn)13.43%。

對于大規(guī)模問題，在平均CPU 時間135.28 s內(nèi)，由TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 得到的平均目標(biāo)值分別為468.3、439.1、371.4、374.6、376.0、360.8。GMBOA的目標(biāo)值較TGA 改進(jìn)29.83%，較MBO&NS 改進(jìn)21.14%，較GMBOAL 改進(jìn)3.16%，較AGA&LS 改進(jìn)4.29%、較IDABC 改進(jìn)4.97%。

雖然小規(guī)模問題20×10、20×15 和20×20 的3 個實例中GMBOA 的目標(biāo)值略差于AGA&LS或GMBOAL，但隨著問題規(guī)模的增大，GMBOA得到的解的質(zhì)量一致優(yōu)于其他5 種算法。

從平均性能來看，對于不同規(guī)模問題，在總平均時間99.57s 內(nèi)，TGA、MBO&NS、GMBOAL、AGA&LS、IDABC 和GMBOA 的平均目標(biāo)值分別為366.3、345.5、291.8、295.7、304.8、284.2。GMBOA的目標(biāo)值較TGA 改進(jìn)28.48%，較MBO&NS 改進(jìn)20.72%，較GMBOAL 改進(jìn)2.78%，較AGA&LS 改進(jìn)4.69%，較IDABC 改進(jìn)9.20%。因此，GMBOA表現(xiàn)最好，尤其是對于大規(guī)模問題。

4）綜上可知，在相同CPU 時間內(nèi)，雖然當(dāng)忽略工序比例較高時GMBOA 求解小規(guī)模問題的一些實例的表現(xiàn)略差于其他算法，但平均性能均優(yōu)于TGA、MBO&NS、GMBOAL、AGA&LS、IDABC。

4 結(jié)束語

本文研究了含忽略工序和不相關(guān)并行機(jī)的混合流水車間調(diào)度問題，以最小化最大完工時間為目標(biāo)建立了整數(shù)規(guī)劃模型，進(jìn)而結(jié)合全局搜索、自適應(yīng)遺傳算法和候鳥優(yōu)化提出一種遺傳候鳥優(yōu)化算法以獲取近優(yōu)解。首先，設(shè)計基于機(jī)器號的編碼方案，采用全局搜索和隨機(jī)程序生成初始種群，然后執(zhí)行隨迭代進(jìn)化過程而調(diào)整的自適應(yīng)交叉和變異操作，從而得到改進(jìn)的GA 解，引入基于3 種鄰域結(jié)構(gòu)的候鳥優(yōu)化算法擴(kuò)大解的搜索空間以更新GA 解。大量隨機(jī)數(shù)據(jù)的仿真實驗證明所提遺傳候鳥優(yōu)化算法能夠在相同的CPU 時間內(nèi)得到滿意的近優(yōu)解。未來研究可將所提算法推廣到多目標(biāo)HFSMO 問題或嘗試其他近似算法（如禁忌搜索、人工蜂群等）求解含不相關(guān)并行機(jī)的HFSMO 問題。