改進多鄰域候鳥優(yōu)化算法的柔性作業(yè)車間調(diào)度研究

杜凌浩，向鳳紅

(昆明理工大學 信息工程與自動化學院，昆明 650500)

1 引言

近年來，我國高端制造業(yè)逐步興起，柔性作業(yè)車間調(diào)度問題(Flexible job shop scheduling problem，F(xiàn)JSP)考慮了機器柔性，更加適用于當前實際生產(chǎn)情況而越來越受到關(guān)注[1]。

因為采用精確算法在解決FJSP大規(guī)模算例時較為困難，近年來大多數(shù)學者將解決方案放在了智能優(yōu)化算法上。文獻[2]提出了基于協(xié)同優(yōu)化算法的多群體協(xié)同遺傳算法對FJSP的最大完工時間最小問題進行了研究。文獻[3]將灰狼算法與遺傳算法相結(jié)合研究了FJSP問題。文獻[4-6]分別將蚱蜢優(yōu)化算法、蜻蜓算法、花朵授粉算法進行改進，并將其應(yīng)用在了FJSP問題上。雖然目前學者已經(jīng)使用了很多經(jīng)典的智能優(yōu)化算法來解決FJSP問題，但還需要一些更具競爭力的算法來獲得更好的優(yōu)化結(jié)果。

候鳥優(yōu)化算法(migrating birds optimization，MBO)是2012年由Duman等[7]受到候鳥遷徙過程中領(lǐng)飛鳥和跟飛鳥的行為而提出的一種新型智能算法。由于其求解問題的優(yōu)越性，許多學者將其應(yīng)用在了調(diào)度問題。文獻[8]將候鳥優(yōu)化算法與分布估計算法結(jié)合研究了阻塞批量流水車間調(diào)度問題。文獻[9]對候鳥優(yōu)化算法的鄰域結(jié)構(gòu)進行改進，并提出一種隨機迭代排列解碼方法應(yīng)用在了混合流水車間調(diào)度問題。文獻[10]將基于迭代貪婪算法、貪婪隨機自適應(yīng)搜索、路徑重新鏈接技術(shù)和局部搜索與候鳥優(yōu)化算法相結(jié)合研究了阻塞混合流水車間調(diào)度問題。文獻[11]采用候鳥優(yōu)化算法對置換流水車間調(diào)度問題進行了研究。但目前主要集中在流水車間調(diào)度問題，少有文獻使用MBO算法研究了柔性作業(yè)車間調(diào)度問題。文獻[12]和文獻[13]采用變鄰域搜索策略與候鳥優(yōu)化算法相結(jié)合，研究了FJSP問題。但對算法的改進，只增加了算法的局部搜索能力，解空間的探索范圍和全局性還有待提升。因此，本文提出一種改進的多鄰域候鳥優(yōu)化算法來解決FJSP問題。具體地，采用隨機和最優(yōu)加工時間策略初始化種群，并采用兩段式編碼，以插入和變異的方式構(gòu)造了6種不同的鄰域結(jié)構(gòu)，采用聯(lián)合鄰域搜索策略擴大解空間的搜索范圍。設(shè)計二次種內(nèi)競爭策略來保證優(yōu)秀個體在種群能夠發(fā)揮更好的引導作用；最后設(shè)計了種間協(xié)同策略來解決MBO算法特殊的共享機制而容易導致算法容易陷入局部最優(yōu)的問題。通過實例和基準算例進行測試，與其他算法進行對比驗證了算法的有效性。

2 柔性作業(yè)車間問題

2.1 問題描述

柔性作業(yè)車間調(diào)度問題描述如下：有n個工件(J1,J2, …,Jn)需要在m臺機器(M1,M2, …,Mm)上加工。其中每個工件含有一道或者多道工序，每個工件的工序數(shù)可以不同，且每道工序的加工順序是固定的；每道工序可以選擇在不同的機器上加工，加工時間取決于所選擇的機器。一個工件同一時刻只能被一臺機器加工；一臺機器同一時刻只能加工同一工件的同一工序；工件一旦開始加工就不能中斷；各工件之間具有相同的優(yōu)先級；同一工件存在加工順序，不同工件工序相互獨立；開始前，所有工件機器應(yīng)該準備就緒。本文出現(xiàn)的符號定義如表1所示。

表1 數(shù)學符號及符號定義

2.2 模型建立

本文以最大完工時間為優(yōu)化目標，其中f為完工時間，表達式如下所示：

f=min(max(Cj)), 1≤j≤n

(1)

Sjh+xxjh×pijh≤Cjh,i=1,2,3,…,m;

j=1,2,3,…,n;h=1,2,3,…,hj

(2)

Cjh≤Sj(h+1),j=1,2,3,…,n;

h=1,2,3,…,hj-1

(3)

Cjhj≤Cmax,j=1,2,3,…,n

(4)

Sjh+pijh≤Skl+L(1-yijhkl),j=0,1,2,3,…,n;

k=1,2,3,…,n;h=1,2,3,…,hj;

l=1,2,3,…,hk;i=1,2,3,…,m

(5)

Cjh≤Sj(h+1)+L(1-yiklj(h+1)),j=1,2,3…,n;

k=0,1,2,3,…,n;h=1,2,3,…,hj-1;

l=1,2,3,…,hk;i=1,2,3,…,m

(6)

(7)

Sjh≥0,Cjh≥0,

j=0,1,2,…,n;h=1,2,3,…,hj

(8)

式(2)和式(3)表示每個工件工序的先后順序約束；式(4)表示單個工件的完工時間小于總完工時間；式(5)和式(6)表示同一臺機器的在某一時刻不能加工多道工序；式(7)表示機器約束，即不能有多臺機器在某一時刻加工同一個工序；式(8)表示各個參數(shù)變量是正數(shù)。

3 改進候鳥優(yōu)化算法解決FJSP問題

3.1 基本候鳥優(yōu)化算法

基本候鳥算法詳細步驟如下：

步驟1算法初始化。算法初始化分為兩部分，第一部分是設(shè)置MBO的參數(shù)，包括產(chǎn)生初始解的個數(shù)，鄰域解的數(shù)量，共享解的數(shù)量以及巡回次數(shù)。第二個部分是生成初始種群，算法的性能受初始種群的影響。在基本MBO中，采用隨機生成可行解的方式生成初始解。在所有可行解s當中，選擇一個解作為領(lǐng)飛鳥，其余可行解作為跟飛鳥，跟飛鳥被平均分為2組，分別放到左隊列和右隊列中。其中各有(s-1)/2個解。

步驟2領(lǐng)飛鳥進化。通過鄰域結(jié)構(gòu)生成k個鄰域解，將鄰域解中的最優(yōu)解與領(lǐng)飛鳥進行對比，若最優(yōu)解優(yōu)于當前領(lǐng)飛鳥的解，則替換領(lǐng)飛鳥；之后將未使用的nx個鄰域解給跟飛鳥使用。

步驟3跟飛鳥進化。根據(jù)鄰域結(jié)構(gòu)，會產(chǎn)生k-nx個鄰域，在新產(chǎn)生的k-nx個鄰域和由前面候鳥產(chǎn)生的未使用的nx個鄰域解中找到最好的解，若最優(yōu)解優(yōu)于當前解，則替換跟飛鳥，同時將本次未使用到的nx個最好解給下一只鳥使用。

步驟4領(lǐng)飛鳥替換。判斷有沒有達到巡回次數(shù)，若未達到巡回次數(shù)，則轉(zhuǎn)到步驟二，若達到巡回次數(shù)，領(lǐng)飛鳥移動到隊伍的末端，在領(lǐng)飛鳥后面的鳥(左邊或右邊)成為新的領(lǐng)飛鳥。

3.2 編碼和解碼

本文采用兩段式編碼：機器編碼，表示將工序分配給對應(yīng)的機器；工序編碼，表示工序被機器加工的順序。

如圖1所表示的是某一染色體的編碼。機器編碼層依次按照工件順序進行加工。機器編碼的數(shù)字表示當前工序在對應(yīng)機器集中選擇的機器，如圖1的第一個數(shù)字2表示該工序選擇在可加工機器集中第二臺機器加工，即O12選擇在機器集中的第二臺機器M3上加工。第二個數(shù)字1表示選擇O32在機器集中的第一臺機器M2上加工。工序編碼層的數(shù)字表示工件號，數(shù)字第幾次出現(xiàn)就表示該工件的第幾道工序，如上圖對應(yīng)所示。解碼時首先通過工序編碼獲得當前工序的相關(guān)信息，然后在機器編碼中找到對應(yīng)的加工機器，從而確定當前工序的加工時間，然后依次對工序編碼進行安排得到完整的調(diào)度解，繪制甘特圖。

圖1 染色體編碼示意圖Fig.1 Chromosome coding diagram

3.3 種群初始化

為了獲得較好的初始解，本文采用隨機生成初始種群，同時針對FJSP在不同機器有不同加工時間的特點，提出最優(yōu)加工時間策略來對種群進行初始化。最優(yōu)加工時間策略即為每道工序分配機器時，選擇機器加工時間最小的機器，進一步減少機器的加工時間，2種方式生成種群的比例為1∶1。

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

MBO算法通過對自身鄰域解的搜索來引導種群進化，為擴大解空間的搜索范圍，結(jié)合本文的編碼方式，設(shè)計了6種不同的鄰域結(jié)構(gòu)產(chǎn)生鄰域解。

鄰域結(jié)構(gòu)1：基于機器編碼的單點變異，在機器編碼中隨機選擇一個基因，同時在該工序的可選機器集里選擇一個與它不同的機器替換原基因。

鄰域結(jié)構(gòu)2：基于工序編碼的互換變異，隨機選擇2個工件的工序，交換2個不同基因在染色體中的位置。

鄰域結(jié)構(gòu)3：將基于機器編碼的單點變異與基于工序編碼的互換變異相結(jié)合的方式(圖2)。

圖2 鄰域結(jié)構(gòu)3示意圖 Fig.2 Schematic diagram of neighborhood structure 3

鄰域結(jié)構(gòu)4：基于機器編碼的前插操作，隨機生成r1，r2，且r1

鄰域結(jié)構(gòu)5：基于工序編碼的前插操作，隨機生成r1，r2，且r1

鄰域結(jié)構(gòu)6：將基于機器編碼的前插操作與基于工序編碼的前插操作行相結(jié)合的方式(圖3)。

圖3 鄰域結(jié)構(gòu)6示意圖 Fig.3 Schematic diagram of neighborhood structure 6

3.5 聯(lián)合鄰域搜索策略

在該策略中，多種不同鄰域共同引導種群進化。左隊列的個體采用前3種基于變異的鄰域結(jié)構(gòu)；右隊列的個體采用后3種基于插入的鄰域結(jié)構(gòu)。對于領(lǐng)飛鳥，在進化巡回過程中可以任意選擇6種不同的鄰域結(jié)構(gòu)來構(gòu)造鄰域解。種群的進化過程中，左右跟飛鳥可以得到多種不同的鄰域組合方式，使多種不同的鄰域結(jié)構(gòu)得到充分利用。

3.6 跟飛鳥二次種內(nèi)競爭策略

跟飛鳥的進化依賴于前一只鳥共享的鄰域解，前鳥的優(yōu)劣影響著算法的進化，在傳統(tǒng)的MBO中，領(lǐng)飛鳥的替換是輪換式的，這就導致優(yōu)秀的個體可能需要很長一段時間才能擁有成為領(lǐng)飛鳥的機會，從而導致鳥群在進化過程中很難把優(yōu)秀的鄰域解傳遞給下一只鳥，如果較差的解排在隊列前面，則后續(xù)跟飛鳥獲得的共享解在進化過程中的作用將會不明顯。為了讓較好的個體能夠更好的發(fā)揮對下一只鳥的引導作用，本文借鑒了文獻[14]提出的一種競爭策略來保證適應(yīng)度較好的鳥處于隊伍前列。但文獻[14]提出的競爭策略只針對于前后跟飛鳥的小范圍競爭，無法對全局的跟飛鳥做出相應(yīng)的調(diào)整，因此本文提出一種新的競爭策略，即在跟飛鳥每次巡回結(jié)束之后分別對左右種群以適應(yīng)度從小到大的方式進行重排列。同時為增強該策略對種群進化的影響，采用跟飛鳥二次種內(nèi)競爭策略，即在達到巡回次數(shù)以后再次采用競爭策略來保證較優(yōu)個體處于隊列前面，增加優(yōu)良跟飛鳥成為領(lǐng)飛鳥的機會。

3.7 種間協(xié)同策略

MBO算法中基于鄰域的搜索方式使算法具備極強的局部搜索能力，但由于其特殊的共享機制，容易導致種群陷入局部最優(yōu)。結(jié)合文獻[15]的研究發(fā)現(xiàn)，種群內(nèi)多次執(zhí)行交換操作能夠增加種群的多樣性，有效避免算法陷入局部最優(yōu)。考慮到候鳥優(yōu)化算法特殊的V字型結(jié)構(gòu)，本文提出種間協(xié)同策略避免算法陷入局部最優(yōu)，引導算法探索更優(yōu)秀的解空間。采用遺傳算法中的交叉操作來實現(xiàn)該理論，即采用基于機器編碼的單點交叉和基于工序編碼的POX交叉。不同于傳統(tǒng)遺傳算法，在本文算法中，父代母代分別來自左右跟飛鳥種群。

基于機器編碼的單點交叉如圖4所示，隨機選擇機器編碼的任意位置，然后交換該位置右側(cè)部分的基因。若某基因出現(xiàn)不可行解，則保持當前基因的原有機器編碼不變。P1代表來自左隊列的候鳥，P2代表來自右隊列的候鳥，C1和C2表示采用基于機器編碼的單點變異之后，而產(chǎn)生的新工序編碼。

圖4 基于機器編碼的單點交叉示意圖 Fig.4 Single point crossing based on machine coding

POX交叉與其他交叉操作相比是效果最好的操作之一，它能夠有效的保證任意工序之間的約束關(guān)系，其主要思想為把總工件集分為2個不同的子工件集J1和J2，分別在左右隊列中找到J1或J2中所有工件的位置，本文選擇J2工件集對應(yīng)的基因。將左右隊列包含J2工件位置的基因互換得到新的個體，如圖5所示，表示的是5個工件共15道工序的工件的調(diào)度解。P1代表左隊列的候鳥，P2代表右隊列的解，J2表示當前的工件集，C1和C2表示通過POX交叉以后新的工序編碼(圖5)。

圖5 基于工序編碼的pox交叉示意圖 Fig.5 POX cross based on process coding

3.8 IMBO算法流程

IMBO算法流程如圖6所示。

圖6 IMMBO流程框圖 Fig.6 IMMBO flow diagram

4 仿真測試與分析

本文采用Matlab 2019a編程，并在Windows 10系統(tǒng)、內(nèi)存為8GB、處理器為[Intel]i5-4200H、64位操作系統(tǒng)的計算機上運行。為驗證算法的有效性，選擇Kacem算例和Brandimate算例[16-17]進行仿真，同時為保證算法的有效性，采用3個文章實例進行驗證。文獻[10]和文獻[11]的參數(shù)設(shè)置，經(jīng)過大量測試，本文設(shè)置參數(shù)如下，種群規(guī)模size=51，領(lǐng)飛鳥和跟飛鳥產(chǎn)生鄰域解的數(shù)量nk=5，共享鄰域解nx的個數(shù)為2，巡回次數(shù)G=5，迭代次數(shù)為200。

4.1 基準算例仿真實驗

從表2可以看出，本文算法能夠獲得最多的最優(yōu)解，并且RPD的平均值也是最低的，因此本文提出的IMMBO算法具有一定的優(yōu)越性。

表2 Brandimate和Kacem算例對比

4.2 聯(lián)合鄰域搜索驗證實驗

然后對聯(lián)合鄰域搜索的有效性進行驗證，這里采用單一鄰域結(jié)構(gòu)與采用多種鄰域結(jié)構(gòu)聯(lián)合搜索的方式進行驗證。本文選擇鄰域結(jié)構(gòu)1和4來進行驗證。為保證驗證實驗的合理性，領(lǐng)飛鳥采用單一鄰域結(jié)構(gòu)，選擇鄰域結(jié)構(gòu)1，跟飛鳥采用多種不同鄰域結(jié)構(gòu)。其中MBO1代表左右跟飛鳥都采用鄰域結(jié)構(gòu)1，MBO4代表左右跟飛鳥都采用鄰域結(jié)構(gòu)4，MBO14代表左右跟飛鳥分別采用鄰域結(jié)構(gòu)1和4。每個算法分別針對Brandimate的10個算例獨立運行10次，取平均值進行驗證。從表3的數(shù)據(jù)中可以看出采用聯(lián)合鄰域搜索MBO14的算法明顯優(yōu)于只采用單一鄰域結(jié)構(gòu)的MBO1的MBO2算法。

表3 聯(lián)合鄰域搜索驗證

4.3 不同候鳥優(yōu)化算法對比實驗

最后為進一步驗證本文改進候鳥優(yōu)化算法與使用其他不同方法改進候鳥優(yōu)化算法的優(yōu)越性，選擇文獻[12]的HMBO1算法和文獻[13]的MBOA和VNS_MBOA算法，采用Brandimarte算例在相同條件下運行10次取平均值進行比較。結(jié)果如表4所示，可以看出除少部分算例本文算法未獲得較優(yōu)的值外，其余算例都獲得優(yōu)于其他方法的解，可以看出IMMBO優(yōu)于其余算法。

4.4 實例仿真

實例1：實例1包括3個工件，6臺機器，共15道工序，實驗數(shù)據(jù)來自文獻[22]，文獻[22]采用PST層次結(jié)構(gòu)的遺傳算法和文獻[23]采用鯨魚群優(yōu)化算法得到的最優(yōu)解為134。文獻[24]采用改進的離散粒子群算法得到的最優(yōu)解是129。利用IMMBO算法對實例進行優(yōu)化求解，得到的最優(yōu)解是116，相比于文獻[22]和文獻[23]，最優(yōu)加工時間縮短了18，相比于文獻[24],最優(yōu)加工時間縮短了13，對應(yīng)的甘特圖如圖7所示。

表4 4種候鳥優(yōu)化算法對比結(jié)果

圖7 實例1甘特圖 Fig.7 Example 1 Gantt diagram

實例2：實例2包括10個工件，8臺機器，共35道工序，實驗數(shù)據(jù)來自文獻[25]，文獻[26]和文獻[27]對蝙蝠算法進行改進分別獲得了82和79的最小完工時間，采用IMMBO算法得到的最優(yōu)解為69，相比于文獻[26]和文獻[27]，最優(yōu)加工時間分別縮短了13和10，其甘特圖如圖8。

圖8 實例2甘特圖 Fig.8 Example 2 Gantt diagram

實例3：實例3包括6個工件，8臺機器，共26道工序，實驗數(shù)據(jù)來自于文獻[28]，其中文獻[29]采用的量子粒子群算法得到的最優(yōu)解為67，文獻[28]采用雙層粒子群優(yōu)化算法得到的最優(yōu)解為60，文獻[27]采用改進的蝙蝠算法得到最優(yōu)解為為56，文獻[30]的混合遺傳蝙蝠算法得到的最優(yōu)解為55，采用IMMBO算法得到的最優(yōu)解為53，相比于文獻[27]和文獻[28]，最優(yōu)加工時間分別縮短了3和7，與文獻[30]和文獻[24]相比，最優(yōu)加工時間分別縮短了14和2，其甘特圖如圖9。

圖9 實例3甘特圖 Fig.9 Example 3 Gantt diagram

從上面3個實例可以看出IMBO都獲得了比其他算法更加優(yōu)良的解，說明所提算法優(yōu)于其他算法，表明了算法的有效性。

5 結(jié)論

針對FJSP問題，提出了一種基于改進的多鄰域候鳥優(yōu)化算法。首先采用兩段式編碼解決FJSP的工序排序和機器選擇問題；為增大解空間的搜索范圍設(shè)計了6種不同的鄰域結(jié)構(gòu)；為擴大候鳥進化過程中前鳥對后鳥的影響作用，設(shè)計了二次種內(nèi)斗爭策略增強較好的個體在算法迭代過程中的效果。最后，為解決候鳥優(yōu)化算法基于鄰域搜索方式，容易陷入局部最優(yōu)的問題，提出了種間協(xié)同策略。通過實例和標準算例測試，IMBO算法在求解FJSP問題時的有效性，下一步將對算法繼續(xù)改進應(yīng)用到求解多目標FJSP問題。