軒華，樊銀格，李冰

（鄭州大學 管理工程學院，河南 鄭州 450001）

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

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

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

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

1 問題描述與建模

1.1 問題描述

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

1）工件的開工應在其釋放時間之后；

2）機器準備時間與工件順序無關，且包含在處理時間中；

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

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

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

6）工序之間的轉移時間忽略不計；

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

1.2 模型構建

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

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

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

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

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

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

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

Bj1≥Rj,?j

式中Rj為工件j的釋放時間。該約束描述了工件只有到達生產系統才可開始處理。

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

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

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

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

2.1 編碼、解碼和適應度選擇

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

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

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

圖2 初始種群Fig.2 Initial population

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

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

2.2 交叉操作

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

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

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

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

式中：λ為當前迭代數；β為最大迭代數；Favg為當前種群的平均適應度值。

2.3 變異操作

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

1）基于隨機機器選擇的單點變異

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

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

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

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

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

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

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

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

1）鄰域搜索結構N1

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

2）鄰域搜索結構N2

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

3）鄰域搜索結構N3

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

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

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

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

3）領飛鳥進化。隨機產生[1,6]之間的一個整數r，若r=1，令Lmax=2，對領飛鳥執(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。該過程往復o次產生領飛鳥的o個鄰域解，若其中的最佳解優(yōu)于當前領飛鳥，則更新領飛鳥，取其余(o?1)個鄰域解中的最佳解加入共享鄰域解集XL和XR。

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

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

6）G1=G1+1，若G1

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

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

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

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

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

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

3）結合隨機程序和全局搜索產生初始種群；

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

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

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

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

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

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

3 仿真實驗

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

3.1 參數設置

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

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

3.2 數據實驗與結果分析

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

定義相對偏差為

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

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

續(xù)表 1

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

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

續(xù)表 3

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

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

續(xù)表 5

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

從表1～6 可知：

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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