基于關(guān)鍵工序的全局隨機(jī)機(jī)器選擇和改進(jìn)GA求解FJSP

徐文星，王琴,2，邊衛(wèi)斌,2，王萬紅,2，董軼群

?

基于關(guān)鍵工序的全局隨機(jī)機(jī)器選擇和改進(jìn)GA求解FJSP

徐文星1，王琴1,2，邊衛(wèi)斌1,2，王萬紅1,2，董軼群1

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

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

柔性作業(yè)車間調(diào)度；優(yōu)化；種群多樣性；機(jī)器選擇；GRS初始化機(jī)制；再激活機(jī)制；遺傳算法；數(shù)值分析

引 言

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

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

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

柔性作業(yè)車間調(diào)度問題可通過如下方式描述：臺(tái)機(jī)器需要加工個(gè)工件，第個(gè)工件的工序數(shù)為()，而每個(gè)工件的任何工序可以在臺(tái)機(jī)器集的子集中的任意一臺(tái)機(jī)器上加工，并且對(duì)應(yīng)的加工時(shí)間隨著加工機(jī)器的不同而不同。柔性作業(yè)車間調(diào)度問題的目標(biāo)是在工序約束和設(shè)備能力約束的前提下，對(duì)所有工序進(jìn)行機(jī)器分配和排序組合，以達(dá)到調(diào)度系統(tǒng)的優(yōu)化目標(biāo)最佳狀態(tài)。

1.1 約束條件

（1）所有機(jī)器在=0時(shí)刻都處于可選用狀態(tài)。

（2）任意時(shí)刻同一臺(tái)機(jī)器只能對(duì)一個(gè)工件加工。

（3）同一時(shí)刻下，同一道工序只能在唯一機(jī)器上進(jìn)行加工。

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

（5）不同工件的優(yōu)先級(jí)別相同。

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

1.2 目標(biāo)函數(shù)

本文中柔性作業(yè)車間調(diào)度問題的目標(biāo)是優(yōu)化調(diào)度系統(tǒng)最大完工時(shí)間。完工時(shí)間是指每臺(tái)機(jī)器結(jié)束加工工序的最晚時(shí)間，其最大值即為最大完工時(shí)間。

數(shù)學(xué)表達(dá)式如下

2 改進(jìn)遺傳算法求解FJSP

2.1 遺傳算子設(shè)計(jì)

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

表1 P-FJSP實(shí)例

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

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

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

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

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

本文將只有一臺(tái)可選機(jī)器的工序稱之為關(guān)鍵工序?？紤]到關(guān)鍵工序?qū)C(jī)器負(fù)荷和工件加工時(shí)間有很重要的影響，本文提出了全局隨機(jī)選擇GRS初始化機(jī)制優(yōu)先對(duì)關(guān)鍵工序進(jìn)行機(jī)器選擇。GRS初始化機(jī)制的算法步驟如下。

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

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

（3）隨機(jī)產(chǎn)生1～中的某個(gè)數(shù)字，即為工件號(hào)，選該工件號(hào)J-muti數(shù)組中的第1個(gè)元素作為當(dāng)前操作工序，并從該J-muti數(shù)組中刪除該工序。按照張國輝等[24-27]提出的GS初始化方法計(jì)算當(dāng)前的機(jī)器負(fù)荷數(shù)值，為當(dāng)前工序選擇最優(yōu)機(jī)器，并存放在MS相應(yīng)的基因位置處，機(jī)器負(fù)荷數(shù)組MT不清零。循環(huán)步驟（3）直到對(duì)類J-muti中的工序進(jìn)行機(jī)器選擇完畢為止。

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

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

再激活機(jī)制將進(jìn)行一次初始化激活、遺傳操作到局部最優(yōu)值停滯的這段時(shí)間稱為局部更新迭代周期。遺傳算法在m次迭代過程中可有多個(gè)局部更新迭代周期，每個(gè)局部更新迭代周期的局部最優(yōu)值需要單獨(dú)記錄，該數(shù)值與迭代過程中的全局最優(yōu)值無關(guān)，與各個(gè)局部更新迭代周期間的局部最優(yōu)值也無關(guān)。

再激活機(jī)制的具體運(yùn)行步驟如下。

（1）記錄局部更新迭代周期內(nèi)的最優(yōu)值。

（2）根據(jù)局部更新迭代部分最優(yōu)值的停滯情況設(shè)置再激活的標(biāo)志位，若停滯次數(shù)達(dá)到10，則該標(biāo)志位設(shè)為1；否則將該標(biāo)志位設(shè)置為0。

（3）當(dāng)標(biāo)志位為1時(shí)，在算法加入一次GRS初始化，并將上一局部更新迭代周期的數(shù)據(jù)清零，進(jìn)入下一個(gè)局部更新迭代周期。否則，循環(huán)執(zhí)行步驟（1）和步驟（2）直到達(dá)到再激活要求。

2.2 改進(jìn)遺傳算法求解FJSP

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

（1）FJSP問題輸入。

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

（3）計(jì)算并評(píng)價(jià)適應(yīng)度值，記錄全局最優(yōu)值。

（4）判斷是否滿足終止條件。若滿足，則輸出優(yōu)化結(jié)果，否則，進(jìn)入步驟（5）。

（5）判斷是否陷入局部極優(yōu)。若是，則進(jìn)入步驟（6），否則，進(jìn)入步驟（7）。

（6）啟動(dòng)再激活機(jī)制。

（7）選擇操作。采用錦標(biāo)賽選擇方法。

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

（9）變異操作。機(jī)器段采用單點(diǎn)變異，工序段采用基于領(lǐng)域搜索變異。

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

3 數(shù)值實(shí)驗(yàn)與分析

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

3.1 初始機(jī)器選擇部分的性能對(duì)比分析

為驗(yàn)證本文提出的GRS初始化機(jī)制的優(yōu)越性，對(duì)文獻(xiàn)[28]中不同初始方式得到的初始種群關(guān)于極限調(diào)度完工時(shí)間limit和調(diào)度完工時(shí)間max兩項(xiàng)指標(biāo)做了相應(yīng)的對(duì)比實(shí)驗(yàn)。

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

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

表2 不同初始方式下FJSP機(jī)器選擇段Climit結(jié)果統(tǒng)計(jì)

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

表3為不同的初始化方式下機(jī)器選擇段種群關(guān)于指標(biāo)max的統(tǒng)計(jì)結(jié)果，其中包括連續(xù)運(yùn)行10次過程中第1代種群的調(diào)度最大完工時(shí)間的最優(yōu)值max的平均值和第100代種群的調(diào)度最大完工時(shí)間的最優(yōu)值max的平均值。圖3對(duì)應(yīng)于表3。由圖3可見，針對(duì)于T-FJSP和P-FJSP，本文提出的GRS初始方式相較于其余4種初始方式在第1代的平均max能達(dá)到中間水平，而最后一代的平均max明顯更優(yōu)。由此說明，本文提出的GRS初始方式對(duì)求解FJSP的種群最優(yōu)解有明顯的改善功能。

表3 不同初始方式下FJSP機(jī)器選擇段Cmax結(jié)果統(tǒng)計(jì)

3.2 求解FJSP基準(zhǔn)算例

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

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

3.2.2 對(duì)比實(shí)驗(yàn)二 基于遺傳算法求解Brandimarte[1]和Kacem等[29-30]設(shè)計(jì)的基準(zhǔn)實(shí)例，由對(duì)比文獻(xiàn)[28]中直接得到相應(yīng)的max和AV(max)指標(biāo)的統(tǒng)計(jì)結(jié)果，與本文提出基于GRS初始化機(jī)制和改進(jìn)遺傳算法綜合求解的結(jié)果進(jìn)行對(duì)比。文獻(xiàn)[28]中，種群規(guī)模大小為500，最大迭代次數(shù)為100，交叉概率為0.8，變異概率為0.05，當(dāng)全局最優(yōu)值連續(xù)30次不變時(shí)，結(jié)束循環(huán)，這樣連續(xù)運(yùn)行10次得到調(diào)度最大完工時(shí)間max的指標(biāo)統(tǒng)計(jì)結(jié)果見表5。

表4 相同規(guī)模不同初始方式求解FJSP所得Cmax指標(biāo)統(tǒng)計(jì)結(jié)果對(duì)比

表5 不同規(guī)模不同初始方式FJSP機(jī)器選擇段Cmax指標(biāo)統(tǒng)計(jì)結(jié)果對(duì)比

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

4 結(jié) 論

針對(duì)FJSP的機(jī)器選擇問題，為提高初始種群質(zhì)量，并增加迭代過程中種群多樣性，本文提出了基于關(guān)鍵工序的全局隨機(jī)選擇初始化機(jī)制和再激活機(jī)制，并通過實(shí)驗(yàn)分析得到以下結(jié)論。

（1）不同初始方式下對(duì)FJSP機(jī)器選擇部分的極限調(diào)度完工時(shí)間limit和調(diào)度最大完工時(shí)間max的實(shí)驗(yàn)結(jié)果表明本文提出的GRS初始化機(jī)制能提高FJSP機(jī)器選擇部分的初始種群質(zhì)量。

（2）不同初始方式下，不同規(guī)模和相同規(guī)模下，F(xiàn)JSP機(jī)器選擇段max指標(biāo)統(tǒng)計(jì)結(jié)果可證明加入GRS初始化機(jī)制和再激活機(jī)制的改進(jìn)遺傳算法在求解FJSP時(shí)有較強(qiáng)的可靠性。

（3）本文提出的改進(jìn)算法并未對(duì)所有算例的最優(yōu)解產(chǎn)生更好的改善，對(duì)此還需要作更深入的優(yōu)化研究。

符 號(hào) 說 明

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

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] 李鐵克, 王偉玲, 張文學(xué). 基于文化遺傳算法求解柔性作業(yè)車間調(diào)度問題[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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] 李修琳, 魯建廈, 柴國鐘, 等. 混合蜂群算法求解柔性作業(yè)車間調(diào)度問題[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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] 宋存利. 求解柔性作業(yè)調(diào)度問題的協(xié)同進(jìn)化粒子群算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 吳秀麗, 張志強(qiáng), 杜彥華, 等. 改進(jìn)細(xì)菌覓食算法求解柔性作業(yè)車間調(diào)度問題[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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] 董蓉, 何衛(wèi)平. 求解FJSP的混合遺傳-蟻群算法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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] 趙詩奎. 求解柔性作業(yè)車間調(diào)度問題的兩極領(lǐng)域搜索混合算法[J]. 機(jī)械工程學(xué)報(bào), 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ìn)遺傳算法求解柔性作業(yè)車間調(diào)度問題[J]. 機(jī)械工程學(xué)報(bào), 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] 張國輝. 柔性作業(yè)車間調(diào)度方法研究[D]. 武漢: 華中科技大學(xué), 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] 趙詩奎, 方水泉, 顧新建. 基于極限調(diào)度完工時(shí)間最小化的機(jī)器選擇及FJSP求解[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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

國家自然科學(xué)基金項(xiàng)目（61304217）；北京市教育委員會(huì)科技計(jì)劃項(xiàng)目（KM201510017003）。

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

聯(lián)系人：董軼群。第一作者：徐文星（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).