姚 妮

(鄭州輕工業(yè)學院 計算機與通信工程學院， 鄭州 450002)

?

混合候鳥遷徙優(yōu)化算法求解柔性作業(yè)車間調(diào)度問題

姚 妮*

(鄭州輕工業(yè)學院 計算機與通信工程學院， 鄭州 450002)

將基本候鳥遷徙優(yōu)化(Migrating birds optimization， MBO)算法與變鄰域搜索策略相結(jié)合，提出了一種混合候鳥遷徙優(yōu)化(Hybrid migrating birds optimization， HMBO)算法求解以最小化最大完工時間為目標的柔性作業(yè)車間調(diào)度問題(Flexible job shop scheduling problem， FJSP).首先，給出了兩段式編碼/解碼方式.為了保證初始解的質(zhì)量和多樣性，設計了一種兩階段種群初始化方法；其次，引入了一種個體重置機制，以避免算法陷入局部最優(yōu)解.根據(jù)FJSP問題的特點，采用3種鄰域結(jié)構(gòu)用于構(gòu)造個體鄰域解，并以此為基礎設計了一種變鄰域搜索算法，增強算法的局部搜索能力.最后，通過基準算例測試了算法的性能，實驗數(shù)據(jù)驗證了本文算法在求解FJSP問題方面的有效性.

柔性作業(yè)車間調(diào)度； 最大完工時間； 候鳥遷徙優(yōu)化算法； 變鄰域搜索策略

柔性作業(yè)車間調(diào)度問題(Flexible job shop scheduling problem， FJSP)比經(jīng)典作業(yè)車間調(diào)度問題(Job shop scheduling problem， JSP)更為復雜，前者是后者的一個擴展形式，已被證明具有NP難的特性[1].與JSP問題相比，F(xiàn)JSP問題中減少了機器約束，增加了調(diào)度的靈活性，這使其能夠更貼近于實際的生產(chǎn)[2].

目前已有很多學者對FJSP問題進行了積極的探索和研究，并取得了大量的成果.近幾十年來國內(nèi)外很多學者采用智能優(yōu)化算法對FJSP問題進行了研究，為FJSP問題的求解提供了新的思路和方法.Kacem等[3-4]針對多目標FJSP問題采用遺傳算法進行求解，使車間內(nèi)工件的最大完工時間、機器總負載以及關鍵機負載最小.Brandimarte[5]基于禁忌搜索算法對FJSP問題進行了研究.Xing等[6]將知識模型和蟻群算法有效結(jié)合，提出了一種基于知識的蟻群算法求解FJSP問題.Ziaee[7]提出了一種高效的啟發(fā)式算法求解以最大完工時間為目標的FJSP問題.賀仁杰等[8]提出了一種知識型協(xié)同演化方法對FJSP問題進行求解.各種群采用不同進化方法和參數(shù)設置，通過種群間的資源競爭和信息共享向前推動算法的進化過程.Rahmati和Zandieh[9]將生物地理學算法應用于FJSP問題的求解，并通過與遺傳算法的比較驗證了算法的有效性.

近些年，隨著智能優(yōu)化算法的迅速發(fā)展，出現(xiàn)了模擬自然界候鳥遷徙行為的候鳥遷徙優(yōu)化(Migrating birds optimization， MBO)算法[10].目前國內(nèi)外學者已將MBO算法成功運用于生產(chǎn)調(diào)度問題的求解[11-13]，但這些研究多集中于流水車間內(nèi)的調(diào)度問題.因此，本文在基本候鳥遷徙優(yōu)化算法的基礎上進行一系列改進，提出了適用于FJSP問題的混合型候鳥遷徙優(yōu)化(Hybrid migrating birds optimization， HMBO)算法.采用兩階段種群初始化方法，引入個體重置機制，設計三種鄰域結(jié)構(gòu)用于構(gòu)造個體的鄰域解，并在算法中嵌入變鄰域搜索策略進一步增強局部尋優(yōu)能力.通過基準算例測試了算法的性能，并驗證了其有效性.

1 柔性作業(yè)車間調(diào)度問題

FJSP問題可描述為：車間內(nèi)n個工件在m臺機器上加工.各工件均包含一道或多道工序，同工件各工序間存在固定的加工順序.工序可在多于一臺的機器上加工，其加工時間與所在機器有關.FJSP問題優(yōu)化的目標是為工序分配適當?shù)臋C器，排列各機器上工序間的加工順序并計算其開始/完工時間，最終使系統(tǒng)某個或某些性能達到最優(yōu)[1].

對于這樣的系統(tǒng)，存在一些基本的假設條件：

1)初始零時刻所有工件和機器都是可用的.

2)一臺機器在某一時刻只允許加工一個工件.

3)各工序的加工過程一旦開始不允許被中斷.

4)同工件工序間具有先后加工的約束關系，不同工件工序間則相互獨立.

5)各工件具有相同的加工優(yōu)先級.

6)忽略機器加工工序前所需的調(diào)整時間.

高效快速完成生產(chǎn)任務仍然是大多數(shù)企業(yè)追求的首要目標.因此，本文以最大完工時間Cmax作為優(yōu)化目標，則目標函數(shù)可表示為

其中，Ci表示工件i的完工時間.

2 混合型候鳥遷徙優(yōu)化算法

候鳥遷徙優(yōu)化算法是一種新興的鄰域搜索技術(shù)，它通過模擬候鳥的自然遷徙行為來實現(xiàn)對目標的優(yōu)化[10].整個算法分為算法初始化，領飛鳥進化，跟飛鳥進化和領飛鳥替換四個階段.種群中所有個體構(gòu)成V字形編隊，由領飛鳥開始向隊列兩端通過搜索個體的鄰域解進行進化，最終實現(xiàn)目標的優(yōu)化.種群中的個體除了搜索自身鄰域解進行更新外，還可以搜索其所在隊列中前一個個體的鄰域解(領飛鳥除外，只搜索自身鄰域解).這種搜索機制能夠提高算法找到更優(yōu)解的概率，使算法能夠快速地獲得最優(yōu)解，體現(xiàn)了算法的集中搜索能力[13].MBO算法比較適用于求解離散組合優(yōu)化問題[13]，因此，本文針對FJSP問題的特點采取一系列改進措施，使MBO算法能夠更好地用于FJSP問題的求解.

2.1 編碼/解碼方案

由于求解FJSP問題主要是解決機器分配和工序排序兩個子問題，因此種群中每個個體可分為兩段表示，長度均為車間內(nèi)的工序總數(shù).前半段表示機器分配方案，后半段表示工序間排序方案，如圖1所示.前半段中元素值為工序所在機器的編號，按固定順序存儲，如圖1(a)所示；后半段中相同的元素值表示同一工件的不同工序，元素間的先后順序表示工序間的加工順序，如圖1(b)所示.

解碼時結(jié)合前后兩段編碼進行操作，從左到右依次讀取后半段元素代表的工序，然后在前半段找到其對應的機器，并計算工序的開始和完工時間.

圖1 編碼方案Fig.1 The encoding scheme

2.2 種群初始化方案

與其他群智能優(yōu)化算法(如遺傳算法和粒子群算法等)相同，候鳥遷徙優(yōu)化算法的性能也在一定程度上受到種群初始解的影響.因此，設計一個好的種群初始化方案是必須要解決的問題.根據(jù)個體編碼方式，初始種群可分兩個階段進行初始化，即機器分配階段和工序排序階段.

對于機器分配階段，采用以下3種方法：

1) 隨機生成法：在每道工序可加工機器集內(nèi)隨機選擇一臺機器填入初始解的前半段.

2) 全局搜索法：采用文獻[2]中的全局搜索方法確定初始解前半段機器分配方案，使機器的工作負載平衡，提高機器的使用率，并同時考慮最小化最大完工時間.

3) 局部搜索法：采用文獻[2]中的局部搜索方法確定初始解前半段機器分配方案，其目的和全局搜索方法一樣.

對于工序排序階段，目前很多文獻均采用隨機生成法或根據(jù)調(diào)度規(guī)則生成初始排序方案[14-15].本文采用基于搜索的方法得到初始解的后半段.針對每一個已生成的機器分配方案，均采取以下操作：首先隨機生成若干個工序排序方案，然后評估每個排序方案結(jié)合該機器分配方案后各自對應的目標值，選擇其中最優(yōu)的一組作為初始解.

2.3 鄰域結(jié)構(gòu)

候鳥遷徙優(yōu)化算法中個體通過搜索自身以及排前一個個體的鄰域解對問題的解空間進行搜索，以獲取優(yōu)化目標的最優(yōu)值.因此，鄰域解的構(gòu)造直接影響著算法的求解質(zhì)量和收斂速度.本文采用以下3種鄰域結(jié)構(gòu)，具體構(gòu)造過程如下：

1) 鄰域結(jié)構(gòu)N1：在調(diào)度解的工序排序部分任意選擇兩個位置，并將兩位置間元素逆序排列.

2) 鄰域結(jié)構(gòu)N2：在調(diào)度解的工序排序部分任意選擇兩道不同工件的工序，并互換兩工序所在的位置.

3) 鄰域結(jié)構(gòu)N3：在調(diào)度解的機器分配部分任意選擇一道工序，并將其分配至可選機器集合中(不包括當前機器)加工時間最短的機器上.

2.4 重置機制

在算法中引入一種重置機制，以避免算法陷入局部最優(yōu)解.具體做法為，首先為種群中每個個體均設置一個解齡.對于新產(chǎn)生的個體，其解齡為1，若經(jīng)過一次進化后計算結(jié)果未發(fā)生變化的個體，其解齡加1.若某個個體的解齡超過了預定的上限limit，則對該個體進行重置操作，即采用上述全局搜索法和基于搜索的方法重新生成一個新個體替代原來的個體.

2.5 變鄰域搜索

基于上述3種鄰域結(jié)構(gòu)設計一種變鄰域搜索算法嵌入到候鳥遷徙優(yōu)化算法中，并作用于當前最優(yōu)個體，以加強算法的局部搜索能力.

變鄰域搜索算法的具體步驟如下：

步驟1：算法初始化.將候鳥遷徙優(yōu)化算法得到的當前最優(yōu)解作為變鄰域搜索算法的初始解π，設置qmax←3，it←1及最大循環(huán)次數(shù)itmax.

步驟2：設置q←1.

步驟3：振動環(huán)節(jié).若q=1，則按鄰域結(jié)構(gòu)N1和N3對π進行變換得到新解π′；若q=2，則按鄰域結(jié)構(gòu)N2和N3對π進行變換得到新解π′；若q=3，則按鄰域結(jié)構(gòu)N3對π進行變換得到新解π′.

步驟4：局部搜索.以振動環(huán)節(jié)得到的π′作為局部搜索的初始解，找到局部最優(yōu)解π″.

步驟5：若π″優(yōu)于π，則π←π″，并設置q←1；否則，設置q←q+1.

步驟6：判斷q>qmax是否成立.若是，設置it←it+1，執(zhí)行步驟7；否則，轉(zhuǎn)到步驟3.

步驟7：判斷it>itmax是否成立.若是，執(zhí)行步驟8；否則，轉(zhuǎn)到步驟2.

步驟8：變鄰域搜索結(jié)束.

變鄰域搜索算法中局部搜索的具體步驟如下：

步驟1：獲取初始解π′，并設置lmax←3，λ←1和最大循環(huán)次數(shù)λmax.

步驟2：設置πL.

步驟5：判斷l(xiāng)>lmax是否成立.若是，則設置λ←λ+1，執(zhí)行步驟6；否則，轉(zhuǎn)到步驟3.

步驟6：判斷λ>λmax是否成立.若是，π″←π′，并執(zhí)行步驟7；否則，轉(zhuǎn)到步驟2.

步驟7：局部搜索結(jié)束.

2.6 HMBO算法步驟

HMBO算法具體步驟如下：

步驟1：設置算法參數(shù)及終止條件Kmax，并令K←1，g←1，fg←1.

步驟2：按照2.2節(jié)的方法生成算法初始種群.

步驟3：領飛鳥進化.根據(jù)三種鄰域結(jié)構(gòu)產(chǎn)生領飛鳥k′個鄰域解，若其中的最優(yōu)解優(yōu)于當前領飛鳥，則替換領飛鳥，并將其余本次進化未用到的x個最好的鄰域解同時加入共享鄰域解集SL和SR中.

步驟4：左隊列跟飛鳥進化.對于左隊列中每個個體πL，根據(jù)鄰域結(jié)構(gòu)產(chǎn)生自身k′-x個鄰域解，并構(gòu)成集合NL.若NL∪SL中的最優(yōu)解優(yōu)于當前解πL，則替換πL.置空SL，將NL∪SL中本次進化未用到的x個最好解加入SL.

步驟5：右隊列跟飛鳥進化.對于右隊列中每個個體πR，根據(jù)鄰域結(jié)構(gòu)產(chǎn)生自身k′-x個鄰域解，并構(gòu)成集合NR.若NR∪SR中的最優(yōu)解優(yōu)于當前解πR，則替換πR.置空SR，將NR∪SR中本次進化未用到的x個最好解加入SR.

步驟6：更新當前最優(yōu)解.

步驟7：更新每個個體的解齡.

步驟8：令g←g+1，并判斷是否滿足g>G.若是，則令g←1，并執(zhí)行步驟9；否則，轉(zhuǎn)到步驟3.

步驟9：檢查每個個體的解齡.若超過limit，則對其執(zhí)行重置操作.

步驟10：更新當前最優(yōu)解，并對其執(zhí)行變鄰域搜索，將產(chǎn)生的新解替換當前種群中最差解.

步驟11：替換領飛鳥.若fg=1，左隊列中第一個個體作為新的領飛鳥，將領飛鳥移至左隊列末端，并設置fg=0；否則，右隊列中第一個個體作為新的領飛鳥，將領飛鳥移至右隊列末端，并設置fg=1.

步驟12：令K←K+1，判斷是否滿足K>Kmax.若是，則轉(zhuǎn)到步驟13；否則，執(zhí)行步驟3.

步驟13：算法結(jié)束.

3 仿真實驗

本節(jié)針對文獻[3-5]中柔性作業(yè)車間調(diào)度問題的15個基準算例(Kacem01～Kacem05和MK01～MK10)對HMBO算法的性能進行測試.采用Fortran語言編程，程序在WinXP系統(tǒng)下內(nèi)存4G的Intel Core (TM) i5-2400 CPU 3.10GHz的計算機上運行.算法中4種參數(shù)根據(jù)文獻[10]推薦的數(shù)值進行設置，即種群規(guī)模51，個體搜索鄰域解個數(shù)k′=3，共享鄰域解個數(shù)x=1，巡回次數(shù)G=10.此外，通過大量實驗設置解齡上限limit=10，最大循環(huán)次數(shù)Kmax=500，itmax=30，λmax=10.

為了避免算法陷入局部最優(yōu)解，HMBO算法中引入了一種個體重置機制.因此，這里首先對個體重置機制的有效性進行驗證.將排除個體重置機制后得到的算法HMBO1與HMBO算法進行比較，對比結(jié)果如表1所示.表中n×m表示算例問題的規(guī)模，兩種算法分別針對15個不同算例獨立運行10次并取平均值.由表中數(shù)據(jù)可以看出，HMBO算法的結(jié)果明顯優(yōu)于HMBO1算法的結(jié)果.

為了進一步驗證HMBO算法的有效性，將其與文獻[4-8]中5種算法進行比較，對比情況如表2和表3所示，其中符號‘-’表示文獻中未給出相應的數(shù)據(jù)，黑體表示各算法經(jīng)對比后的最佳結(jié)果.表2中第2～6列給出了由各文獻提供的算法在計算各算例時的最優(yōu)值，第7列為本文算法得到的最優(yōu)結(jié)果.由表1可以看出，本文HMBO算法只在算例Kacem05略差于文獻[6]和文獻[8]中的算法，且只相差一個時間單位.表3中針對Brandimarte算例進行了進一步地比較和分析.首先給出各算法在計算相應算例時得到的最優(yōu)值，然后計算其相對百分比偏差值(Relative percent deviation， RPD).計算公式為

獻[6,8-9]中的算法均能在10個算例中得到6個算例的最佳結(jié)果，但是本文算法得到的平均相對百分比偏差RPD的數(shù)值最小.因此，本文提出的HMBO算法具有一定的有效性.

表1 兩種算法對比結(jié)果

表2 Kacem算例對比結(jié)果

表3 Brandimarte算例對比結(jié)果

4 結(jié)論

本文針對FJSP問題，以最小化最大完工時間為目標，結(jié)合基本候鳥遷徙優(yōu)化算法和變鄰域搜索算法，提出了適用于FJSP問題求解的混合型候鳥遷徙優(yōu)化算法.該算法采用兩階段種群初始化方案，保證了初始種群質(zhì)量和多樣性；設計了個體重置機制，以避免算法陷入局部最優(yōu)解；針對每個個體，設計了3種鄰域結(jié)構(gòu)用于構(gòu)造個體鄰域解；設計變鄰域搜索算法并嵌入到候鳥遷徙優(yōu)化算法中，增強了算法的局部搜索能力.通過對基準算例的計算，驗證了HMBO算法在求解FJSP問題方面的有效性.

目前候鳥遷徙優(yōu)化算法在求解生產(chǎn)調(diào)度問題方面的研究仍處于起步階段，下一步工作需將算法推廣到其他更復雜的車間調(diào)度問題中，并結(jié)合問題的特點，設計出更加高效的算法.

[1] 張超勇， 饒運清， 李培根， 等. 柔性作業(yè)車間調(diào)度問題的兩級遺傳算法[J]. 機械工程學報， 2007， 43(4): 119-124．

[2] 張國輝， 高 亮， 李培根， 等. 改進遺傳算法求解柔性作業(yè)車間調(diào)度問題[J]. 機械工程學報， 2009， 45(7): 145-151．

[3] KACEM I， HAMMADI S， BORNE P. Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic[J]. Mathematics and Computers in Simulation， 2002， 60(3): 245-276.

[4] KACEM I， HAMMADI S， BORNE P. Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C: Applications and Reviews， 2002， 32(1): 1-13.

[5] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research， 1993， 41(3): 157-183．

[6] XING L N， CHEN Y W， WANG P， et al. A knowledge-based ant colony optimization for flexible job shop scheduling problems[J]. Applied Soft Computing， 2010， 10(3): 888-896.

[7] ZIAEE M. A heuristic algorithm for solving flexible job shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology， 2014， 71(1-4): 519-528．

[8] 賀仁杰， 陳宇寧， 姚 鋒， 等. 求解柔性車間作業(yè)調(diào)度的知識型協(xié)同演化方法[J]. 計算機集成制造系統(tǒng)， 2011， 17(2): 310-315．

[9] RAHMATI S H A， ZANDIEH M. A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology， 2012， 58(9-12): 1115-1129．

[10] DUMAN E， UYSAL M， ALKAYA A F. Migrating birds optimization: a new metaheuristic approach and its performance on quadratic assignment problem[J]. Information Sciences， 2012， 217: 65-77．

[11] PAN Q K， DONG Y. An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation[J]. Information Sciences， 2014， 277: 643-655．

[12] TONGUR V， üLKER E. Migrating birds optimization for flow shop sequencing problem[J]. Journal of Computer and Communications， 2014， 2(4): 142-147．

[13] 謝展鵬， 賈 艷， 張超勇， 等. 基于候鳥優(yōu)化算法的阻塞流水車間調(diào)度問題研究[J]. 計算機集成制造系統(tǒng)， 2015， 21(8): 2099-2107．

[14] PEZZELLA F， MORGANTI G， CIASCHETTI， G. A genetic algorithm for the flexible job-shop scheduling problem[J]. Computers &Operations Research， 2008， 35(10): 3202-3212．

[15] GAO K Z， SUGANTHAN P N， PAN Q K， et al. Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives[J]. Journal of Intelligent Manufacturing， 2015， 26(12):1-9．

Hybrid migrating brids optimization algorithm for the flexible job shop scheduling problem

YAO Ni

(School of Computer and Communication Engineering， Zhengzhou University of Light Industry， Zhengzhou 450002)

In this paper， a hybrid migrating birds optimization algorithm (HMBO) is proposed to solve the flexible job shop scheduling problem (FJSP) with the objective of minimizing the makespan by combining the basic migrating birds optimization (MBO) and the variable neighborhood search strategy. Firstly， two-phase encoding and decodingapproaches are given， and a two-stage population initialization method is developed to ensure the quality and diversity of initial solutions. Secondly， an individual reset mechanism is introduced to avoid the algorithm being trapped into the local extremum. In terms of the features of the FJSP， three neighborhood structures are adopted to generate individual neighboring solutions， and based on which a variable neighborhood search algorithm is designed to enhance the local searching capability of the algorithm. Finally， some benchmark instances are used to test the performance of the algorithm. Experimental data show that the proposed algorithm is effective for solving the FJSP．

flexible job shop scheduling； makespan； migrating birds optimization algorithm； variable neighborhood search strategy

2015-07-25.

河南省科技攻關項目(122102210492)．

1000-1190(2016)01-0038-05

TP18

A

*E-mail: zzulijsjyn@163.com．