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

姚 妮

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

?

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

姚 妮*

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

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

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

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

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

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

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

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

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

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

2)一臺(tái)機(jī)器在某一時(shí)刻只允許加工一個(gè)工件.

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

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

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

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

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

其中，Ci表示工件i的完工時(shí)間.

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

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

2.1 編碼/解碼方案

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

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

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

2.2 種群初始化方案

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

對(duì)于機(jī)器分配階段，采用以下3種方法：

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

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

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

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

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

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

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

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

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

2.4 重置機(jī)制

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

2.5 變鄰域搜索

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

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

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

步驟2：設(shè)置q←1.

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

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

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

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

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

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

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

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

步驟2：設(shè)置πL.

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

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

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

2.6 HMBO算法步驟

HMBO算法具體步驟如下：

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

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

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

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

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

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

步驟7：更新每個(gè)個(gè)體的解齡.

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

4 結(jié)論

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

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

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

[2] 張國輝， 高 亮， 李培根， 等. 改進(jìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題[J]. 機(jī)械工程學(xué)報(bào)， 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)度的知識(shí)型協(xié)同演化方法[J]. 計(jì)算機(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]. 計(jì)算機(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.

河南省科技攻關(guān)項(xiàng)目(122102210492)．

1000-1190(2016)01-0038-05

TP18

A

*E-mail: zzulijsjyn@163.com．