基于關鍵工序的全局隨機機器選擇和改進GA求解FJSP

徐文星，王琴,2，邊衛斌,2，王萬紅,2，董軼群

?

基于關鍵工序的全局隨機機器選擇和改進GA求解FJSP

徐文星1，王琴1,2，邊衛斌1,2，王萬紅1,2，董軼群1

（1北京石油化工學院信息工程學院，北京 102617；2北京化工大學信息科學與技術學院，北京 100029）

以FJSP的最大完工時間作為優化目標，在考慮同一工件的工序順序約束的同時，為提高初始種群的多樣性，針對FJSP的機器選擇問題采用堆棧方式存儲工序。P-FJSP中只有一臺機器可選的關鍵工序能直接影響機器總負荷和工件加工時間，進而提出了一種基于關鍵工序的全局隨機選擇（GRS）初始化方法。為了避免基本遺傳算法在求解FJSP時陷入局部極優而停滯，在GA算法中加入再激活（re-activation）機制，旨在重新激活種群，增加種群的多樣性。最后，針對FJSP基準測試算例進行數值分析，通過初始機器選擇部分的性能對比實驗、不同初始方式下遺傳算法求解FJSP對比實驗分別驗證了GRS初始化機制的有效性和所提改進算法的可靠性。

柔性作業車間調度；優化；種群多樣性；機器選擇；GRS初始化機制；再激活機制；遺傳算法；數值分析

引 言

關于柔性作業車間調度（flexible job-shop scheduling problem, FJSP）的研究具有很重要理論意義和實際應用價值。國內外學者采用不同的求解算法對FJSP做了深入研究，如禁忌搜索算法[1-3]、文化算法[4-5]、蜂群算法[6-7]、混合和聲搜索算法[8]、粒子群算法[9-10]、細菌覓食優化算法[11]、遺傳算法[12-28]等。智能優化算法各有優劣，而遺傳算法作為一種魯棒性強、通用性好、計算性能穩定的智能優化算法，近年來在FJSP中得到了廣泛應用[28]。國內外關于應用遺傳算法求解FJSP的研究主要在于其編碼方式、遺傳操作算子、解碼方法以及與其他智能算法的結合等，而對種群初始化方法的研究成果不多。由于種群初始化能直接影響算法在整個進化過程的收斂速度和全局搜索能力，因而是智能進化算法中關鍵問題。目前，大多數的進化算法還都是采用隨機方法進行種群初始化，這樣會增加種群大小和迭代次數，從而導致算法的復雜度高、計算負荷大。張國輝等[24-27]提出了一種GLR(global local random)機器選擇方法，其中GS(global selection)和LS(local selection)主要是綜合考慮機器負荷和工序加工時間，盡可能均衡機器的利用率，從而縮短工序的最大完工時間。GLR初始化方法的提出，由于集中了不同機器選擇方式的優點，因此改善了初始種群的質量，縮短了算法的優化時間。趙詩奎等[28]分析出極限調度時間能在很大程度上影響機器選擇鏈初始種群的質量，提出了基于文獻[24-27]中GLR初始化方法的改進機器選擇初始化方法，綜合考慮最大機器負荷和最大工件加工時間以優化FJSP的最大完工時間。張國輝等[24-27]提出的機器選擇GLR初始化方法在選擇工序時，是在既定的工件下，依次選擇該工件的全部工序，這樣會導致機器選擇段的多樣性不足。不同于張國輝等[24-27]的GLR初始化方法，趙詩奎等[28]所提出的初始化方法并未考慮同一工件中的工序順序約束，而著重于增加種群的多樣性，但所增加的初始種群并不能全部得到改善。

在考慮同一工件的工序順序約束的同時，為提高初始種群質量和迭代過程中種群多樣性，本文采用堆棧方式提出了一種基于關鍵工序的全局隨機選擇（global random selection, GRS）初始化方法及再激活機制，并通過對比實驗以證明該方法在提高初始種群中機器選擇段質量的同時，能夠獲得更加可靠的FJSP求解結果。

1 柔性作業車間調度問題的描述

柔性作業車間調度問題可通過如下方式描述：臺機器需要加工個工件，第個工件的工序數為()，而每個工件的任何工序可以在臺機器集的子集中的任意一臺機器上加工，并且對應的加工時間隨著加工機器的不同而不同。柔性作業車間調度問題的目標是在工序約束和設備能力約束的前提下，對所有工序進行機器分配和排序組合，以達到調度系統的優化目標最佳狀態。

1.1 約束條件

（1）所有機器在=0時刻都處于可選用狀態。

（2）任意時刻同一臺機器只能對一個工件加工。

（3）同一時刻下，同一道工序只能在唯一機器上進行加工。

（4）每一工件的每道工序開始加工后中途不能中止。

（5）不同工件的優先級別相同。

（6）同一工件的工序之間有嚴格的先后約束關系，而不同工件之間不存在任何先后約束關系。

1.2 目標函數

本文中柔性作業車間調度問題的目標是優化調度系統最大完工時間。完工時間是指每臺機器結束加工工序的最晚時間，其最大值即為最大完工時間。

數學表達式如下

2 改進遺傳算法求解FJSP

2.1 遺傳算子設計

2.1.1 FJSP的編碼準則 針對FJSP兩大子問題的強耦合性，本文采用集成整數編碼方式，用整數表示染色體個體中的每個基因值，每一個體分為兩部分：機器選擇部分(machine selection，MS)和工序排序部分(operation sequencing，OS)。染色體的總長度為調度系統的工序總數的兩倍，機器選擇部分MS和工序排序部分OS的長度均為調度系統的工序總數。表1顯示的是P-FJSP(partial FJSP)某一案例有關數據，表格中的數值表示工序在對應機器上的加工時間。圖1對應于表1案例的一種染色體編碼方案。

表1 P-FJSP實例

Note: “—” indicates that operation can’t be processed by corresponding machine.

（1）機器選擇部分 機器選擇部分MS是按工序排列的機器編碼，將所有工件的所有工序選擇的機器在其可選機器集里的位置序號，而不是機器號，按照各工件既定的先后約束關系從左到右依次存放在MS的相應位置。

以表1所示的P-FJSP為例說明MS段編碼方式。該案例=2、=5、To=5，染色體MSOS的長度為10，MS和OS長度分別為5。MS段從左到右依次表示工序1112212223所選擇的加工機器在可選機器集中的位置序號。如MS染色體中11對應位置存放的基因值4，表示11在其可選機器集{12345}中選擇的機器4在其可選機器集中的位置序號是4。MS染色體中12對應位置存放的基因值1，表示12在其可選機器集{24}中選擇的機器2在其可選機器集中的位置序號是1。如圖1左半部分所示。

（2）工序排序部分 工序排序部分的每一數字代表一個工件號，而該工件號在OS段出現的次數則代表該工序是對應工件的第道工序。以表1所示的P-FJSP為例說明OS段編碼方式。OS段的長度為工序總數To=5。OS段的數值依次為2、2、1、1、2，表示加工工件的順序是22112，加工工序的順序是2122111223。如圖1右半部分所示。

2.1.2 初始化機制 在考慮同一工件的工序順序約束的同時，為提高初始種群的多樣性，本文采用堆棧的存儲方式將所有工序依次存放在個數組中，每個數組表示一個工件，并從上至下依次存放工序數由小變大的工序。隨機選擇一類工件，選取該數組當前存放的第1道工序，對該工序進行機器選擇，并存放在MS相應的基因位置處，隨后刪除該工序。循環進行，直至所有工序的機器選擇完畢為止。

本文將只有一臺可選機器的工序稱之為關鍵工序。考慮到關鍵工序對機器負荷和工件加工時間有很重要的影響，本文提出了全局隨機選擇GRS初始化機制優先對關鍵工序進行機器選擇。GRS初始化機制的算法步驟如下。

（1）基于堆棧的思想，將所有工序依次存放在類數組中，每類數組含兩個cell數組：J-only和J-muti。J-only中存放該工件只有一臺可選機器的工序，J-muti存放該工件中有多臺可選機器的工序。兩者的存放規則都是從上到下依次存放工序數變大的工序。

（2）隨機產生1～中的某個數字，即為工件號，選該工件號J-only數組中的第1個元素作為當前操作工序，并從該J-only數組中刪除該工序。由于J-only數組中的工序可選機器唯一，則在MS段所選工序的基因位置處直接賦值為1。按照張國輝等[24-27]提出的GS初始化方法計算當前的機器負荷數值，機器負荷數組MT不清零。循環步驟（2）直到對類J-only中的工序進行機器選擇完畢為止。

（3）隨機產生1～中的某個數字，即為工件號，選該工件號J-muti數組中的第1個元素作為當前操作工序，并從該J-muti數組中刪除該工序。按照張國輝等[24-27]提出的GS初始化方法計算當前的機器負荷數值，為當前工序選擇最優機器，并存放在MS相應的基因位置處，機器負荷數組MT不清零。循環步驟（3）直到對類J-muti中的工序進行機器選擇完畢為止。

針對FJSP中機器選擇部分和工序選擇部分的強耦合性，本文采用GRS方法對所有工序進行機器選擇，隨機方法對所有工序進行排序，這樣就完成了染色體MS段和OS段的初始化。

2.1.3 再激活機制 基本遺傳算法具有很強的全局搜索能力，但是在多次循環迭代過程中，很可能陷入局部極優而停滯。為了有效避免這種情況發生，本文在基本遺傳算法中加入再激活（re-activation）機制，即當種群最優陷入停滯時，重新調用初始化，旨在再次激活種群，增加種群的多樣性。

再激活機制將進行一次初始化激活、遺傳操作到局部最優值停滯的這段時間稱為局部更新迭代周期。遺傳算法在m次迭代過程中可有多個局部更新迭代周期，每個局部更新迭代周期的局部最優值需要單獨記錄，該數值與迭代過程中的全局最優值無關，與各個局部更新迭代周期間的局部最優值也無關。

再激活機制的具體運行步驟如下。

（1）記錄局部更新迭代周期內的最優值。

（2）根據局部更新迭代部分最優值的停滯情況設置再激活的標志位，若停滯次數達到10，則該標志位設為1；否則將該標志位設置為0。

（3）當標志位為1時，在算法加入一次GRS初始化，并將上一局部更新迭代周期的數據清零，進入下一個局部更新迭代周期。否則，循環執行步驟（1）和步驟（2）直到達到再激活要求。

2.2 改進遺傳算法求解FJSP

在求解FJSP的改進遺傳算法中，機器選擇部分采用GRS初始化機制生成，工序排序部分采用隨機方法生成。選擇更新采用錦標賽選擇策略；交叉更新中機器段采用均勻交叉[25]方式，工序段采用POX交叉[25]方式；變異更新中機器段采用單點變異[25]方式，工序段采用基于領域搜索變異[25]方式；利用插入解碼[25]方式進行解碼。整體算法步驟如下。

（1）FJSP問題輸入。

（2）種群初始化。機器段采用GRS初始化機制，工序段采用隨機初始方法。

（3）計算并評價適應度值，記錄全局最優值。

（4）判斷是否滿足終止條件。若滿足，則輸出優化結果，否則，進入步驟（5）。

（5）判斷是否陷入局部極優。若是，則進入步驟（6），否則，進入步驟（7）。

（6）啟動再激活機制。

（7）選擇操作。采用錦標賽選擇方法。

（8）交叉操作。機器段采用均勻交叉，工序段采用POX交叉。

（9）變異操作。機器段采用單點變異，工序段采用基于領域搜索變異。

（10）循環步驟（3）～步驟（9），直到滿足終止條件。

3 數值實驗與分析

為了驗證本文針對FJSP的機器選擇問題提出的基于關鍵工序的全局隨機選擇GRS初始化機制和改進遺傳算法的有效性，以Brandimarte[1]和Kacem等[29-30]設計的基準實例（可通過網址http://www.idsia.ch/~monaldo/fisp.html進行下載）作為測試問題，設計了兩類實驗：一類是運用全局隨機選擇初始化方式得到FJSP機器選擇部分的初始種群，對比分析初始種群的質量；一類是利用加入了GRS初始化機制和再激活機制的改進遺傳算法求解FJSP實例。旨在通過這兩類實驗來驗證本文提出的GRS初始化機制在FJSP中的有效性，并在結果表格中用黑體字表示所統計的最優結果。

3.1 初始機器選擇部分的性能對比分析

為驗證本文提出的GRS初始化機制的優越性，對文獻[28]中不同初始方式得到的初始種群關于極限調度完工時間limit和調度完工時間max兩項指標做了相應的對比實驗。

3.1.1 極限調度完工時間 本次實驗將采用文獻[28]中的4種機器選擇初始化方式Z-GS、Z-LS、I-GS、I-LS和本文提出的GRS初始化方式，對Brandimarte[1]的mk02（P-FJSP，partial-FJSP）和Kacem等[29-30]的15×10（T-FJSP, total-FJSP）實例初始化1000條機器選擇MS段染色體，通過計算其min(limit)和AV(limit)來對比分析初始種群的質量（limit的計算方法見文獻[28]）。

不同的初始化方式得到的機器選擇段種群關于指標min(limit)和AV(limit)的統計結果如表2所示。圖2對應于表2。由圖2可以看出，本文提出改進后的GRS初始方式對比于文獻[28]中的4種初始化方式，min(limit)和AV(limit)基本上都有了很大程度的降低。其中，mk02的min(limit)和AV(limit)指標值明顯優于其他4種初始方式，由此可說明，本文提出的GRS初始機制對FJSP（尤其是P-FJSP）中機器選擇段limit性能有很大程度的提升。

表2 不同初始方式下FJSP機器選擇段Climit結果統計

3.1.2 調度最大完工時間 為了進一步比較初始種群機器選擇段的質量，本實驗采用相同的遺傳算法對15×10和mk02兩個實例分別以調度最大完工時間最小化為目標函數進行對比實驗。遺傳算法的參數設置如下：種群大小=1000，最大迭代次數m=100，連續運行次數COT=10，采用以上說明的5種不同機器選擇初始方式得到1000條機器選擇種群，工序排序段種群則通過隨機方法得到。為了提高測試的準確性，機器選擇部分MS的交叉和變異概率均設置為0，工序排序部分OS的交叉概率和變異概率分別設置為0.80和0.05。

表3為不同的初始化方式下機器選擇段種群關于指標max的統計結果，其中包括連續運行10次過程中第1代種群的調度最大完工時間的最優值max的平均值和第100代種群的調度最大完工時間的最優值max的平均值。圖3對應于表3。由圖3可見，針對于T-FJSP和P-FJSP，本文提出的GRS初始方式相較于其余4種初始方式在第1代的平均max能達到中間水平，而最后一代的平均max明顯更優。由此說明，本文提出的GRS初始方式對求解FJSP的種群最優解有明顯的改善功能。

表3 不同初始方式下FJSP機器選擇段Cmax結果統計

3.2 求解FJSP基準算例

3.2.1 對比實驗一 為驗證本文所提出的方法具有更強的可靠性，本次實驗將在相同的規模下求解FJSP。種群規模大小為100，最大迭代次數為200，交叉概率為0.8，變異概率為0.01，每個算例連續運行10次。文獻[28]中的初始化方法和張國輝等[24-27]的初始化方法全局選擇、局部選擇、隨機選擇的比例為0.45:0.45:0.1。

由表4可以看出，在種群規模和最大迭代次數相同的情況下，本文的方法與張國輝等[24-27]的方法和文獻[28]中的方法相比，在11個算例中，有10個算例得到了更優解，有9個算例的平均最優值更好，有10個算例得到的最優解的最差值最小，有7個算例的最優值方差更佳。由此可以證明，本文提出的加入GRS初始化機制和再激活機制的改進遺傳算法在求解FJSP時有更強的可靠性。

3.2.2 對比實驗二 基于遺傳算法求解Brandimarte[1]和Kacem等[29-30]設計的基準實例，由對比文獻[28]中直接得到相應的max和AV(max)指標的統計結果，與本文提出基于GRS初始化機制和改進遺傳算法綜合求解的結果進行對比。文獻[28]中，種群規模大小為500，最大迭代次數為100，交叉概率為0.8，變異概率為0.05，當全局最優值連續30次不變時，結束循環，這樣連續運行10次得到調度最大完工時間max的指標統計結果見表5。

表4 相同規模不同初始方式求解FJSP所得Cmax指標統計結果對比

表5 不同規模不同初始方式FJSP機器選擇段Cmax指標統計結果對比

本文采用加入GRS的初始化機制和再激活機制的改進GA求解FJSP，遺傳種群規模大小為100，最大迭代次數為200，交叉概率為0.8，變異概率為0.01，連續運行10次得到調度最大完工時間max的指標統計結果見表5。由表5的統計結果可以看出，雖然由本文提出改進算法的種群規模大小和最大迭代次數的乘積明顯小于文獻[28]中的參數，但是本文GRS初始方式下11組算例的AV(max)有9組算例明顯優于文獻[28]的結果，有8組算例得到了更好的最優解，進一步驗證了本文提出算法的有效性和可靠性。

4 結 論

針對FJSP的機器選擇問題，為提高初始種群質量，并增加迭代過程中種群多樣性，本文提出了基于關鍵工序的全局隨機選擇初始化機制和再激活機制，并通過實驗分析得到以下結論。

（1）不同初始方式下對FJSP機器選擇部分的極限調度完工時間limit和調度最大完工時間max的實驗結果表明本文提出的GRS初始化機制能提高FJSP機器選擇部分的初始種群質量。

（2）不同初始方式下，不同規模和相同規模下，FJSP機器選擇段max指標統計結果可證明加入GRS初始化機制和再激活機制的改進遺傳算法在求解FJSP時有較強的可靠性。

（3）本文提出的改進算法并未對所有算例的最優解產生更好的改善，對此還需要作更深入的優化研究。

符 號 說 明

AV(Cmax)——最大完工時間的平均值 Climit——極限調度完工時間 Cmax——調度系統的最大完工時間 COT——連續運行次數 Gm——最大迭代次數 h(j)——第j個工件的工序總數 Jj——第j個工件 j——工件序號，j=1,2,3, …,n k——機器序號，k=1,2,3,…,m LB——最優值的下界 l——工序序號，l=1,2,3, …,h(j) Mk——第k臺機器 Max(Cmax)——最大完工時間的最差值 MT(k)——每k臺機器的最大完工時間 m——機器總數 n——工件總數 Ojl——第j個工件的第l道工序 P——種群大小 To——工序總數， Var(Cmax)——最大完工時間的方差

References

[1] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Ann. Oper. Res., 1993, 41(3): 157-183.

[2] MASTROLOLLI M, GAMBBARDELLA L M. Effective neighborhood functions for the flexible job shop problem[J]. Journal of Scheduling, 2002, 3(1): 3-20.

[3] LI J Q, PAN Q K, SUGANTHAN P N,A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem[J]. International Journal of Advanced Manufacturing Technology, 2011, 52(52): 683-697.

[4] HO N B, TAY J C. GENACE: an efficient cultural algorithm for solving the flexible job-shop problem[C]// Proceedings of the 2004 Congress on Evolutionary Computation. Washington, D.C,USA: IEEE, 2004: 1759-1766.

[5] 李鐵克, 王偉玲, 張文學. 基于文化遺傳算法求解柔性作業車間調度問題[J]. 計算機集成制造系統, 2010, 16(4): 861-866. LI T K, WANG W L，ZHANG W X. Solving flexible Job Shop scheduling problem based on cultural genetic algorithm[J]. Computer Integrated Manufacturing Systems, 2010, 16(4): 861-866.

[6] 李修琳, 魯建廈, 柴國鐘, 等. 混合蜂群算法求解柔性作業車間調度問題[J]. 計算機集成制造系統, 2011, 17(7): 1495-1500. LI X L, LU J S, CHAI G Z,. Hybrid bee colony algorithm for flexible job shop scheduling problem[J]. Computer Integrated Manufacturing System, 2011, 17(7): 1495-1500.

[7] GAO K Z, SUGANTHAN P N, CHUA T J,. A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion[J]. Expert Systems with Applications, 2015, 42(21): 7652-7663.

[8] YUAN Y, XU H, YANG J D. A hybrid harmony search algorithm for the flexible job shop scheduling problem[J]. Applied Soft Computing, 2013, 13(7): 3259-3272.

[9] 宋存利. 求解柔性作業調度問題的協同進化粒子群算法[J]. 計算機工程與應用, 2013, 49(21): 15-18.SONG C L. Co-evolution particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. Computer Engineering and Applications, 2013, 49(21): 15-18.

[10] SINGH M R, MAHAPATRA S S. A quantum behaved particle swarm optimization for flexible job shop scheduling[J]. Computers & Industrial Engineering, 2016, 93: 36-44.

[11] 吳秀麗, 張志強, 杜彥華, 等. 改進細菌覓食算法求解柔性作業車間調度問題[J]. 計算機集成制造系統, 2015, 21(5): 1262-1270. WU X L, ZHANG Z Q, DU Y H,. Improved bacteria foraging optimization algorithm for flexible job shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2015, 21(5): 1262-1270.

[12] 董蓉, 何衛平. 求解FJSP的混合遺傳-蟻群算法[J]. 計算機集成制造系統, 2012, 18(11): 2492-2501.DONG R, HE W P. Hybrid genetic algorithm-ant colony optimization for FJSP solution[J]. Computer Integrated Manufacturing Systems, 2012, 18(11): 2492-2501.

[13] ISHHIKAWA S, KUBBOA R, HORIO K. Effective hierarchical optimization by a hierarchical multi-space competitive genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications, 2015, 42(24): 9434-9440.

[14] 趙詩奎. 求解柔性作業車間調度問題的兩極領域搜索混合算法[J]. 機械工程學報, 2015, 14: 175-184.ZHAO S K. Bilevel neighborhood search hybrid algorithm for the flexible job shop scheduling problem[J]. Journal of Mechanial Engineering, 2015, 14: 175-184.

[15] CHANG H, CHEN Y, LIU T,. Solving the flexible job scheduling problem with makespan optimization by using a hybrid taguchi-genetic algorithm[J]. Access IEEE, 2015, 3: 1740-1754.

[16] LI X, GAO L. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem[J]. International Journal of Production Economics, 2016, 174: 93-110.

[17] ZHOU W, YAN-PING B U, ZHOU Y Q. An improved genetic algorithm for solving flexible job shop scheduling problem[C]// Control and Decision Conference. 2013: 4553-4558.

[18] CHANG H C, TAI H T, LIU T K. Application of genetic algorithm to optimize unrelated parallel machines of flexible job-shop scheduling problem[C]// IEEE International Conference on Control & Automation. IEEE, 2014: 596-599.

[19] MOGHADAM A M, WONG K Y, PIROOZFARD H. An efficient genetic algorithm for flexible job-shop scheduling problem[C]// IEEE International Conference on Industrial Engineering and Engineering Management. IEEE, 2015: 1031-1044.

[20] XU L, SUN W, MING H. Flexible job shop scheduling based on multi-population genetic-variable neighborhood search algorithm[C]// International Conference on Computer Science and Network Technology. IEEE, 2015: 244-248.

[21] ZHANG M, WU K. An improved genetic algorithm for the re-entrant and flexible job-shop scheduling problem[C]// Chinese Control and Decision Conference. IEEE, 2016: 3399-3404.

[22] REN H, XU H, SUN S. Immune genetic algorithm for multi-objective flexible job-shop scheduling problem[C]// Chinese Control and Decision Conference. IEEE, 2016.

[23] WU X L, LI S J. Mass variety and small batch scheduling in the flexible job shop[C]// International Conference on Biomedical Engineering and Informatics, Bmei 2009. Tianjin, China, 2009: 1-7.

[24] 張國輝, 高亮, 李培根, 等. 改進遺傳算法求解柔性作業車間調度問題[J]. 機械工程學報, 2009, 45(7): 145-151. ZHANG G H, GAO L, LI P G,. Improved genetic algorithm for the flexible job-shop scheduling problem[J]. Journal of Mechanial Engineering, 2009, 45(7): 145-151.

[25] 張國輝. 柔性作業車間調度方法研究[D]. 武漢: 華中科技大學, 2009. ZHANG G H. Research on methods for flexible job shop scheduling problems[D]. Wuhan: Huazhong University of Science and Technology, 2009.

[26] ZHANG G H, GAO L, SHI Y. An effective genetic algorithm for the flexible job-shop scheduling problem[J]. Expert Systems with Applications, 2011, 38(4): 3563-3573.

[27] SHI Y, ZHANG G H, GAO L,. A novel initialization method for solving flexible job-shop scheduling problem[C]//Proceedings of International Conference on Computers & Industrial Engineering. Washington, D, C, USA: IEEE, 2009.

[28] 趙詩奎, 方水泉, 顧新建. 基于極限調度完工時間最小化的機器選擇及FJSP求解[J]. 計算機集成制造系統, 2014, 20(4): 854-865. ZHAO S K, FANG S Q, GU X J. Machine selection and FJSP solution based on limit scheduling completion time minimization[J]. Computer Integrated Manufacturing Systems, 2014, 20(4): 854-865.

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

[30] KACEM I. Genetic algorithm for the flexible job-shop scheduling problem[J]. IEEE International Conference on Systems Man and Cybernetics, 2003, 4: 3464-3469.

Improved GA and global random machine selection based on key operation to solve FJSP

XU Wenxing1, WANG Qin1, 2, BIAN Weibin1, 2, WANG Wanhong1, 2, DONG Yiqun1

(1College of Information Engineering, Beijing Institute of Petrochemical Technology, Beijing 102617, China;2College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China)

In order to improve the diversity of initial population and consider the operation sequence constraints of the same artifact at the same time, the stack was used to storage all operations in the view of the FJSP machine selection problem, in which the makespan was the optimization objective. Global random initialization method based on the key operation was proposed to solve the machine selection problem of FJSP, in which the key operation containing the only optional machine can directly affect the total load machine and processing time. To avoid the basic genetic algorithm trapped in local optimum when solving FJSP, re-activation mechanism was added to the GA algorithm, by which the diversity of population can be increased. Finally, in the view of the FJSP benchmark examples, the effectiveness of the GRS initialization mechanism and the reliability of the proposed improved algorithm were verified respectively by analyzing the performance comparison of the initial machine selection parts and the experimental results of solving FJSP by the genetic algorithm with different initializations.

flexible job-shop scheduling; optimization; species diversity; machine selection; GRS initialization mechanism; re-activation mechanism; genetic algorithm; numerical analysis

10.11949/j.issn.0438-1157.20161625

TP 301.6；TP 278

A

0438—1157（2017）03—1073—08

國家自然科學基金項目（61304217）；北京市教育委員會科技計劃項目（KM201510017003）。

2016-11-16收到初稿，2016-11-26收到修改稿。

聯系人：董軼群。第一作者：徐文星（1982—），女，博士，副教授。

2016-11-16.

DONG Yiqun, dongyq@bipt.edu.cn

supported by the National Natural Science Foundation of China (61304217)and the Scientific Research Common Program of Beijing Municipal Commission of Education (KM201510017003).