杜凌浩，向鳳紅

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

1 引言

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

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

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

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

2.1 問題描述

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

表1 數學符號及符號定義

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)表示各個參數變量是正數。

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

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

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

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

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

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

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

3.2 編碼和解碼

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

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

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

3.3 種群初始化

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

3.4 鄰域結構

MBO算法通過對自身鄰域解的搜索來引導種群進化，為擴大解空間的搜索范圍，結合本文的編碼方式，設計了6種不同的鄰域結構產生鄰域解。

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

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

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

圖2 鄰域結構3示意圖 Fig.2 Schematic diagram of neighborhood structure 3

鄰域結構4：基于機器編碼的前插操作，隨機生成r1，r2，且r1

鄰域結構5：基于工序編碼的前插操作，隨機生成r1，r2，且r1

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

圖3 鄰域結構6示意圖 Fig.3 Schematic diagram of neighborhood structure 6

3.5 聯合鄰域搜索策略

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

3.6 跟飛鳥二次種內競爭策略

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

3.7 種間協同策略

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

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

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

POX交叉與其他交叉操作相比是效果最好的操作之一，它能夠有效的保證任意工序之間的約束關系，其主要思想為把總工件集分為2個不同的子工件集J1和J2，分別在左右隊列中找到J1或J2中所有工件的位置，本文選擇J2工件集對應的基因。將左右隊列包含J2工件位置的基因互換得到新的個體，如圖5所示，表示的是5個工件共15道工序的工件的調度解。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)、內存為8GB、處理器為[Intel]i5-4200H、64位操作系統(tǒng)的計算機上運行。為驗證算法的有效性，選擇Kacem算例和Brandimate算例[16-17]進行仿真，同時為保證算法的有效性，采用3個文章實例進行驗證。文獻[10]和文獻[11]的參數設置，經過大量測試，本文設置參數如下，種群規(guī)模size=51，領飛鳥和跟飛鳥產生鄰域解的數量nk=5，共享鄰域解nx的個數為2，巡回次數G=5，迭代次數為200。

4.1 基準算例仿真實驗

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

表2 Brandimate和Kacem算例對比

4.2 聯合鄰域搜索驗證實驗

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

表3 聯合鄰域搜索驗證

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

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

4.4 實例仿真

實例1：實例1包括3個工件，6臺機器，共15道工序，實驗數據來自文獻[22]，文獻[22]采用PST層次結構的遺傳算法和文獻[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，對應的甘特圖如圖7所示。

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

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

實例2：實例2包括10個工件，8臺機器，共35道工序，實驗數據來自文獻[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道工序，實驗數據來自于文獻[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 結論

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