基于改進(jìn)區(qū)塊進(jìn)化算法求解置換流水車間問題

張 敏，汪 洋，方 侃

(天津大學(xué) 管理與經(jīng)濟(jì)學(xué)部,天津 300072)

0 引言

置換流水車間調(diào)度問題(Permutation Flowshop Scheduling problem, PFSP)是一類經(jīng)典的調(diào)度問題，許多實(shí)際流水線生產(chǎn)調(diào)度問題都可以簡化為PFSP，如生產(chǎn)制造系統(tǒng)、組裝線和信息服務(wù)設(shè)施等[1]。PFSP屬于NP難問題[2]，迄今為止，學(xué)者們已提出不同的算法來解決該問題。傳統(tǒng)的解決方法主要有精確算法(動態(tài)規(guī)劃、分支定界法等)和啟發(fā)式方法(Gupta法[3]、CDS法(Campbell-Dudek-Simth)[4]、NEH法(Nawaz-Enscore-Ham)等)。精確算法理論上能夠得到最優(yōu)解，但隨著問題規(guī)模的增大，計算時間呈指數(shù)式增長，因此僅適用于求解小規(guī)模問題；啟發(fā)式算法雖可以在較短時間內(nèi)得出問題的解，但其解的質(zhì)量無法保證。目前，基于計算智能的元啟發(fā)式算法(遺傳算法[5-6]、粒子群算法[7-8]、模擬退火[9]、禁忌搜索[10]等)成為解決車間調(diào)度問題的研究熱點(diǎn)，并取得了一系列成果。

在這些元啟發(fā)式算法中，分布估計算法(Estimation of Distribution Algorithm, EDA)為一種全新的演化模式，已逐漸興起并應(yīng)用于解決不同的組合優(yōu)化問題[11-12]。EDA主要是通過統(tǒng)計學(xué)習(xí)的手段對生物進(jìn)化從宏觀層面上建立概率統(tǒng)計模型，并以此描述整個群體的進(jìn)化趨勢。與傳統(tǒng)的基因演算法相比，EDA利用概率模型的學(xué)習(xí)與挖掘替換了交叉與變異操作。至今已有很多學(xué)者提出了多種改良的EDA并應(yīng)用于不同層面。Baluja[13]提出使用獨(dú)立變量數(shù)學(xué)模型的基于群體增量學(xué)習(xí) (Population Based Incremental Learning，PBIL) 算法，被視為最早的EDA模型，該算法主要利用二進(jìn)制編碼方法解決最優(yōu)化問題；Chen等[14]提出基于人工染色體的基因算法(extended Artificial Chromosomes with Genetic Algorithm，eACGA) ，改良了之前使用獨(dú)立變量概率模型的做法，增加了二元概率模型來產(chǎn)生人造解 (Artificial Chromosome, AC)，提高了算法的收斂效率；Pelikan等[15]提出貝葉斯優(yōu)化算法(Bayesian Optimization Algorithm，BOA) 來解決多元相依的問題，該算法將選擇的優(yōu)勢群體作為樣本集合，根據(jù)樣本構(gòu)造對應(yīng)的貝葉斯網(wǎng)絡(luò)，最后對貝葉斯模型進(jìn)行采樣，并產(chǎn)生新一代群體。

近年來，許多學(xué)者在EDA的基礎(chǔ)上結(jié)合片段或區(qū)塊的概念[16]，提出改進(jìn)的EDA算法[1，17]，并取得了一定的成果。Chang等[18]提出基于區(qū)塊的基因算法BBEDA (block-based evolutionary distribution algorithm,)來求解PFSP，該算法利用二元變量概率模型，依據(jù)概率矩陣再通過輪盤法挖掘具有競爭優(yōu)勢的區(qū)塊，將區(qū)塊和非區(qū)塊的基因組合出新的解來增加解的多樣性。BBEDA算法利用優(yōu)勢概率矩陣和相依概率矩陣，其挖掘的對象是連續(xù)基因結(jié)構(gòu)組成的區(qū)塊，而好的基因組合并不一定是連續(xù)的，因此Hsu等[19]提出基于關(guān)聯(lián)規(guī)則的區(qū)塊挖掘算法 (Linkage Mining in Block-Based Evolutionary Algorithm, LMBBEA)，利用關(guān)聯(lián)規(guī)則挖掘出不連續(xù)的基因組合成更多元區(qū)塊，避免了區(qū)塊組合方式過于單調(diào)而造成多樣性不足的問題，提升了算法的效果，但因為該算法使用完全隨機(jī)方法產(chǎn)生初始解，所以無法保證初始解的質(zhì)量，而且LMBBEA在母體重組階段采用相鄰交換法，該方法用局部最優(yōu)結(jié)果產(chǎn)生重組母體，無法保證重組母體的全局最優(yōu)性，且缺乏多樣性。在利用關(guān)聯(lián)規(guī)則進(jìn)行區(qū)塊挖掘的基礎(chǔ)上，本文利用貪婪迭代思想改進(jìn)了NEH算法[20]，并將其應(yīng)用于種群初始化，使初始種群具有較好的質(zhì)量和多樣性。為加快利用關(guān)聯(lián)規(guī)則挖掘優(yōu)勢區(qū)塊的速度與效率，本文又提出新的NEH交換方法，并結(jié)合相鄰交換法應(yīng)用于不同的進(jìn)化階段進(jìn)行母體重組，在增加收斂速度的同時兼顧了有效性。通過應(yīng)用該算法求解PFSP并進(jìn)行實(shí)例仿真，驗證了該算法的魯棒性與有效性。

1 置換流水車間調(diào)度問題描述

PFSP將n個工件在m臺機(jī)器上加工，并滿足如下約束：①各工件在每臺機(jī)器上加工且僅加工一次；②所有工件以完全相同的順序依次經(jīng)過各個機(jī)器；③某一時刻一個工件只能在一臺機(jī)器上加工，一臺機(jī)器也只能加工一個工件；④初始時刻所有工件都可以進(jìn)行加工。若調(diào)度目標(biāo)為最大完工時間，則用三元組表示為Fm/prmu/Cmax，其中：prmu表示所有工件按完全相同的順序經(jīng)過每一臺機(jī)器；Cmax表示這批工件的最大完工時間。

PFSP用數(shù)學(xué)模型描述如下：若用p(i,j)表示工件j在機(jī)器i上的加工時間(假設(shè)工件準(zhǔn)備時間包含在加工時間內(nèi))，并且工件的排序為π{π1,π2,…,πn}，假設(shè)各工件按照機(jī)器1～機(jī)器m的順序加工，則n個工件m臺機(jī)器的PFSP完工時間C(i,πj)分別為：

C(1,π1)=p(1,π1);

(1)

C(1,πj)=C(1,πj-1)+p(1,πj),j=2,…,n;

(2)

C(i,π1)=C(i-1,π1)+p(i,π1),

i=2,…,m;

(3)

C(1,πj)=max{C(i,πj-1),C(i-1,πj)}+

p(i,πj),i=2,…,m，j=2,…,n;

(4)

Cmax=C(m,πn)。

(5)

求解該問題就是要獲得最優(yōu)調(diào)度工件排序π*，使得對于其他任意的工件排序π都有

Cmax(π*)≤Cmax(π)。

2 基于NEH和關(guān)聯(lián)規(guī)則挖掘的區(qū)塊進(jìn)化算法(NEH-LMBBEA)

NEH-LMBBEA主要由6部分組成，其流程圖如圖1所示：①用改進(jìn)NEH算法產(chǎn)生初始種群；②運(yùn)用關(guān)聯(lián)規(guī)則挖掘優(yōu)勢區(qū)塊，并且通過區(qū)塊競爭保留最具優(yōu)勢區(qū)塊；③組合人造解，將區(qū)塊與非區(qū)塊所包含的工件組合成具有競爭優(yōu)勢的人造解，并注入母體幫助進(jìn)化；④為了避免陷入局部最優(yōu)而進(jìn)行的變異操作，加入單點(diǎn)突變機(jī)制；⑤母體自我重組的演化機(jī)制，本研究綜合在不同的進(jìn)化階段應(yīng)用相鄰交換法和NEH交換法，以增加重組母體的多樣性，保證重組母體的質(zhì)量，并增加尋找優(yōu)勢解的機(jī)會；⑥篩選優(yōu)勢解的機(jī)制。

圖1中:ΔS表示母體重組計數(shù)器，Sthre表示使用母體重組的臨界值，ΔK表示區(qū)塊挖掘的計數(shù)器，Kthre表示使用區(qū)塊挖掘的臨界值。

2.1 改進(jìn)NEH算法初始化種群

2.1.1 NEH算法

NEH算法[20]被認(rèn)為是解決PFSP較好的一種啟發(fā)式方法，其步驟如下：

步驟2從序列S中選擇前兩個元素S[0]和S[1]，計算并選擇由S[0]和S[1]對應(yīng)的工件組成的兩個排序中，總完工時間最小的排序記作S′； 再從S中選擇排在位置3的元素S[2]，插入S′中所有可能的位置，計算并保留3個工件總完工時間最小的序列組成新的S′。

步驟3重復(fù)步驟2依次從S中選擇元素插入S′，直到所有工件都被排序。

本文借助NEH算法思想提出了改進(jìn)NEH方法，并在種群初始化階段加以應(yīng)用。

2.1.2 應(yīng)用改進(jìn)NEH法進(jìn)行種群初始化

NEH算法經(jīng)常被用于各算法的母體初始化。本文在初始化種群時使用改進(jìn)的NEH算法，該算法的思想是：首先由NEH算法得到第一條染色體，然后在第一條染色體的基礎(chǔ)上實(shí)施破壞和重新構(gòu)造操作，從產(chǎn)生的鄰域中選擇最好的解作為新的初始母體，重復(fù)上述破壞和重新構(gòu)造步驟直到得到N條初始母體(N為某給定值)。具體的改進(jìn)NEH算法構(gòu)造如下：

步驟1利用NEH算法得到第一條母體Chr0。

步驟3從π′中依次選擇一個工件，將其插入π″中所有可能的位置并計算對應(yīng)的Cmax，比較并保留Cmax值最小所對應(yīng)的序列，作為下一個工件插入的基礎(chǔ)序列，重復(fù)該步驟直到π′中的所有工件都插入π″中，得到第2條母體Chr1。

步驟4重復(fù)步驟2和步驟3，直到產(chǎn)生含N個母體的初始種群。

2.2 運(yùn)用關(guān)聯(lián)規(guī)則挖掘區(qū)塊

2.2.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則[21]是利用歷史資料信息發(fā)現(xiàn)其中包含的相互關(guān)系與頻繁模式，最初通過逐條分析交易記錄尋找商品間的關(guān)聯(lián)性，為決策者擺放商品和制定促銷策略提供依據(jù)。在調(diào)度問題上，關(guān)聯(lián)規(guī)則通過分析染色體結(jié)構(gòu)尋找基因間的關(guān)聯(lián)性，找出優(yōu)秀的基因組合組成區(qū)塊，并通過將所挖掘區(qū)塊產(chǎn)生的高競爭力人造解注入母體來降低問題的復(fù)雜度，從而有效提升算法的求解效果與收斂效率。

在表示X→Y的關(guān)聯(lián)規(guī)則中，存在兩個重要的參考指標(biāo)和一個評價指標(biāo)(其中X∩Y=?；X→Y表示若X發(fā)生，則Y也發(fā)生)。參考指標(biāo)分別為支持度(Support)與信心水平(Confidence)[22]，支持度指X與Y同時出現(xiàn)在資料記錄里的頻率，信心水平指X與Y的關(guān)聯(lián)強(qiáng)度；評價指標(biāo)增益值[23]則是用來判定關(guān)聯(lián)強(qiáng)度，若增益值大于1則為強(qiáng)關(guān)聯(lián)性，相關(guān)的計算公式如下：

(6)

(7)

(8)

式中：N表示染色體總數(shù)；τ(X∪Y)表示基因集X和基因集Y同時出現(xiàn)各染色體的總次數(shù)；δ(X)表示基因集X出現(xiàn)于各染色體的概率；s(X→Y)表示兩基因集之間關(guān)聯(lián)的支持強(qiáng)度；c(X→Y)表示兩基因集之間關(guān)聯(lián)的信心水平；Lift表示增益值，用來判斷基因集之間是否存在強(qiáng)烈的關(guān)聯(lián)。另外，為了使關(guān)聯(lián)規(guī)則成立，需存在一些必要條件，即最小支持度(minimum support)與最小信心水平(minimum confidence)，只有挖掘的關(guān)聯(lián)規(guī)則超過所設(shè)立的臨界值，才能作為有意義的信息。

2.2.2 構(gòu)建與挖掘區(qū)塊

本文根據(jù)關(guān)聯(lián)規(guī)則構(gòu)建優(yōu)勢區(qū)塊。優(yōu)勢區(qū)塊是一個擁有高度競爭優(yōu)勢的基因結(jié)構(gòu)，是降低進(jìn)化算法復(fù)雜度的一種方法[19]。本研究挖掘區(qū)塊的第一步是在各代群體中依據(jù)適應(yīng)值大小排序，選擇適應(yīng)值排在前K的染色體，根據(jù)所挑選的各染色體的工件順序?qū)⑵滢D(zhuǎn)化為工件加工記錄資料集。圖2所示為從包含5個工件的所有排序中挑選適應(yīng)值 (Cmax)較好的4條染色體，將其工件排序轉(zhuǎn)化為工件加工記錄資料的過程，其中設(shè)置區(qū)塊長度為1，執(zhí)行代數(shù)為3。

得到工件的加工資料集后，根據(jù)設(shè)立的最小支持度臨界值(Smin)和區(qū)塊的最大長度產(chǎn)生區(qū)塊的具體流程如下：

步驟1從工件加工資料庫中找出大于所設(shè)立臨界值的基因放入頻繁項目集H。

步驟2將頻繁項目集H中的基因聯(lián)結(jié)為基因區(qū)塊組合的候選項目集L。

步驟3從候選項目集L中找出大于臨界值的基因區(qū)塊為新的頻繁項目集H′，直到無法找到大于臨界值的基因區(qū)塊組合為止，將所得的基因組合存入當(dāng)代的暫存資料庫。

步驟4重復(fù)上述步驟，直到所有好的基因組合(區(qū)塊)均被存入暫存資料庫。

構(gòu)建區(qū)塊的過程如圖3所示。

2.2.3 區(qū)塊篩選

通過關(guān)聯(lián)規(guī)則挖掘得到的區(qū)塊資料庫中可能存在不同區(qū)塊包含相同工件，或不同區(qū)塊的工件出現(xiàn)在相同位置上的情況，區(qū)塊篩選就是挑選與比較區(qū)塊資料庫中的區(qū)塊，將出現(xiàn)上述情況的區(qū)塊通過區(qū)塊間的競爭進(jìn)行比較和選擇，保留具有更高競爭優(yōu)勢的區(qū)塊。具體做法是將資料庫中的區(qū)塊進(jìn)行工件與位置對比，若區(qū)塊間出現(xiàn)重復(fù)的工件或出現(xiàn)位置重復(fù)，發(fā)生重復(fù)的區(qū)塊將比較區(qū)塊的增益值[23]，增益值大于1且數(shù)值較大者將擁有更強(qiáng)的關(guān)聯(lián)度而被保留，其他不滿足的區(qū)塊將被刪除。區(qū)塊篩選如圖4所示。經(jīng)過區(qū)塊競爭后，留存在區(qū)塊資料庫中的優(yōu)勢區(qū)塊將用于組合人造解。

2.3 組合人造解

組合具有高度競爭優(yōu)勢的人造解，將其注入母體可以提高算法求解的品質(zhì)和收斂效率[24]。本文利用挖掘和篩選后具有高度競爭優(yōu)勢的區(qū)塊進(jìn)行組合人造解操作，具體步驟如下：

步驟1將挖掘和篩選后的所有區(qū)塊放入所建造的空的人造解中，將區(qū)塊中對應(yīng)的工件與機(jī)器位置直接放入人造解對應(yīng)的位置。

步驟2找出尚未挑選的工件集合A，依次隨機(jī)地從A中選擇工件放入人造解未安排工件的位置中，直到人造解組合完成。

AC組合人造解的操作方式如圖5所示。

2.4 突變機(jī)制

為了避免算法陷入局部最優(yōu)，本文采用單點(diǎn)突變機(jī)制。單點(diǎn)突變指母體本身發(fā)生基因突變的過程，雖然進(jìn)行母體突變會破壞算法過程中的穩(wěn)定性，但是卻可以發(fā)掘母體中潛在的基因特性，擴(kuò)大問題的搜索空間。文中的突變機(jī)制是隨機(jī)產(chǎn)生一個突變位置，將該位置上的原有基因與其補(bǔ)集基因(補(bǔ)集基因指與該基因相加等于工件總數(shù)的基因)互換，如圖6所示。

2.5 母體重組

母體重組是該進(jìn)化算法中一個重要的進(jìn)化程序，可以提高本研究算法尋找最佳解的機(jī)會。本文將NEH交換法 (NEH Swapping, NEHS)和相鄰交換法 (Neighborhood Swapping, NS)[25]兩種不同的方法分別在進(jìn)化的不同階段進(jìn)行母體重組。NEHS是從整體上尋找大規(guī)模破壞母體交換后的最優(yōu)重組解，能夠提高算法的全局搜索能力，適用于進(jìn)化前期(進(jìn)化代數(shù)前60%)，用于增加重組后母體的多樣性并保證其有效性；NS對母體進(jìn)行局部破壞后尋優(yōu)，適用于進(jìn)化后期 (進(jìn)化代數(shù)后40%)，因為后期的母體整體質(zhì)量較高，對高質(zhì)量母體進(jìn)行較小地破壞能保證算法的有效性。

2.5.1 NEH交換法

NEHS用于進(jìn)化前期的母體重組階段，主要為增加重組后解的多樣性并保留解的競爭優(yōu)勢，從而增加算法尋找最優(yōu)解的機(jī)會，加速算法收斂。NEH交換法的步驟如下：

步驟1從染色體中隨機(jī)挑選L(L

NEH交換法的運(yùn)行機(jī)制如圖7所示。

2.5.2 相鄰交換法

NS由Chang[25]首次提出并應(yīng)用，本文將其用于進(jìn)化后期，充分利用了該方法的局部搜索能力，能保證重組母體具有高度的競爭優(yōu)勢。NS的步驟如下：

步驟1隨機(jī)的選擇N個切點(diǎn)，將染色體切割成數(shù)個片段。

步驟2選擇片段中最長的片段進(jìn)行相鄰交換。

步驟3從選中片段的第一個工件開始，以兩兩交換的方式進(jìn)行變動，每次變動均計算相應(yīng)的適應(yīng)值。

步驟4重復(fù)步驟3，直到出現(xiàn)與原片段相同的排序為止。

步驟5比較變動過程中所有序列的適應(yīng)值，選擇適應(yīng)值最小的序列作為最終變動的結(jié)果，插入原片段的位置，完成母體重組。

NS的運(yùn)行機(jī)制如圖8所示。

2.6 保留優(yōu)勢解

進(jìn)行母體重組后產(chǎn)生的子代會與此代的原始母體進(jìn)行比較篩選，本文使用二元競賽法(binary tournament selection)[26]選擇新的母體進(jìn)行下一代進(jìn)化。二元競賽法的運(yùn)行機(jī)理是：首先將新產(chǎn)生的子代與原始母體放入同一個選擇池中，然后從選擇池中隨機(jī)選擇兩條解，比較其對應(yīng)的適應(yīng)值，將適應(yīng)值小的解選到新的母體中，適應(yīng)值較大的解放回選擇池繼續(xù)篩選，反復(fù)執(zhí)行上述步驟，直到所選擇的解滿足設(shè)定的母體大小，新產(chǎn)生的母體將進(jìn)入算法的下一次迭代。

3 實(shí)驗結(jié)果與分析

為了驗證本文提出的NEH-LMBBEA求解PFSP的性能，以O(shè)R-Library中Taillard[27]與Reeves[28]例題作為測試案例，將測試結(jié)果與LMBBEA及其他進(jìn)化算法進(jìn)行比較。NEH-LMBBEA程序用Microsoft Visual Studio 2015中的Visual C++編寫，運(yùn)行環(huán)境為Windows10 (64位)操作系統(tǒng)系統(tǒng)，Intel(R) Core(TM)i7-3610M CPU@ 2.30 GHz，內(nèi)存8 G。首先在各參數(shù)設(shè)置完全相同的情況下，將NEH-LMBBEA，BBEDA[25]和LMBBEA[19]進(jìn)行比較，驗證并展示本文算法的魯棒性和有效性，以及相應(yīng)性能提升的效果；隨后將NEH-LMBBEA，VP-QEA[29]和LMBBEA[19]在執(zhí)行代數(shù)較少的情況下進(jìn)行較，驗證本文算法的快速收斂性。這里使用目前普遍使用的誤差率作為本文算法與其他算法比較的基準(zhǔn)，誤差率分為平均誤差率AER和最小誤差率MER，其計算公式為：

(9)

(10)

式中：mean表示算法所求的平均值,least表示算法所求的最小值，opt表示最優(yōu)解。

為了突出本文改進(jìn)算法的效果，NEH-LMBBEA設(shè)定的各個參數(shù)均與LMBBEA[19]和BBEDA[25]相同，其中：實(shí)驗次數(shù)為30，種群規(guī)模為100， Reeves例題的迭代次數(shù)為n×m×50(n為工件數(shù)，m為機(jī)器數(shù))， Taillard例題的迭代次數(shù)參照文獻(xiàn)[30]的參數(shù)設(shè)定，其他參數(shù)設(shè)定均參照算法LMBBEA[19]。Reeves例題執(zhí)行結(jié)果比較如表1所示，執(zhí)行例題Taillard的結(jié)果如表2所示。

表1 執(zhí)行Reeves例題時各算法的結(jié)果比較

續(xù)表1

表2 執(zhí)行Taillard例題時各算法的結(jié)果比較

由表1可知， NEH-LMBBEA求解Reeves例題的AER平均值為0.34，MER平均值為0.53，均優(yōu)于BBEDA和LMBEA，其中AER較LMBEA提升了19.7%，提升效果明顯，而且利用本文算法測試Reeves的21個例題時(如表1第1列)，所得到的MER和AER均優(yōu)于其他兩個算法。由表2可知，用3種算法測試Taillard的 (ta005，ta010，ta020，ta030，ta050，ta060，ta070，ta080)8個規(guī)模的不同例題，本文算法的MER均值為0.38，較BBEDA提升了38.7%，較LMBBEA提升了24%，而且NEH-LMBBEA測試各個例題所得的MER均優(yōu)于其他算法，表明NEH-LMBBEA算法尋找最佳解的能力高于BBEDA和LMBBEA。綜合表1和表2可知，本文所提NEH-LMBBEA能有效解決PFSP，且具有很強(qiáng)的魯棒性。

為了驗證本文算法較LMBBEA能高效快速收斂，減少進(jìn)化代數(shù)，將迭代數(shù)設(shè)置為n×m，重新驗證21個Reeves例題，并記錄運(yùn)行時間。運(yùn)行結(jié)果并與變參數(shù)量子進(jìn)化算法 (Variable Parameters Quantum-inspired Evolutionary Algorithm, VP-QEA)[29]進(jìn)行比較，結(jié)果如表3所示。圖9和圖10所示分別為NEH-LMBBEA，LMBBEA，VP-QEA在迭代設(shè)置較少情況下的MER和AER比較。通過表3、圖9和圖10可以明顯看出，相對于最優(yōu)調(diào)度目標(biāo)的MER和AER，NEH-LMBBEA均優(yōu)于LMBBEA和VP-QEA，且效果明顯；NEH-LMBBEA的執(zhí)行時間和LMBBEA相近，遠(yuǎn)低于VP-QEA。實(shí)驗表明，NEH-LMBBEA能在較短的時間內(nèi)找到最優(yōu)解，具有快速收斂能力和較強(qiáng)的魯棒性。

表3 算法收斂能力與收斂速度比較

續(xù)表3

數(shù)值實(shí)驗分析表明，NEH-LMBBEA求解PFSP的效果明顯優(yōu)于BBEDA，LMBBEA和VP-QEA。

4 結(jié)束語

本文對LMBBEA進(jìn)行改進(jìn)，提出NEH-LMBBEA來求解PFSP。主要改進(jìn)有：①提出改進(jìn)NEH算法初始化種群，得到同時兼具多樣性和競爭優(yōu)勢的初始母體，加速了算法的收斂速度；②為了避免陷入局優(yōu)，提出一個新穎的單點(diǎn)突變機(jī)制，增加了算法的全局尋優(yōu)能力；③為了提高算法尋找最佳解的機(jī)會，提出將NEHS結(jié)合NS應(yīng)用于不同的進(jìn)化階段，充分發(fā)揮了兩種方法的優(yōu)勢，保證了重組母體的競爭優(yōu)勢。通過對PFSP的Benchmark問題進(jìn)行數(shù)值實(shí)驗表明，相比于較LMBBEA和BBEDA，NEH-LMBBEA在求解PFSP的魯棒性和有效性上有了很大程度的提高，而且通過設(shè)置較少的進(jìn)化代數(shù)，驗證了該算法的收斂速度和收斂效率較LMBBEA和VP-QEA更高。今后將嘗試把本文算法應(yīng)用于其他組合優(yōu)化問題。

參考文獻(xiàn):

[1] LIU Chang, LI Dong, PENG Hui, et al. EDA algorithm with correlated variables for solving hybrid flow-shop scheduling problem[J].Computer Integrated Manufacturing Systems,2015,21(4):1032-1039(in Chinese).[劉 昶,李 冬,彭 慧,等.求解混合流水車間調(diào)度問題的變量相關(guān)EDA算法[J].計算機(jī)集成制造系統(tǒng),2015,21(4):1032-1039.]

[2] GAREY M R, JOHNSON D S, SETHI R. The complexity of flowshop and job shop scheduling[J]. Mathematics of Operations Research,1976,1(2):117-129.

[3] CHENG T C E, GUPTA M C. Survey of scheduling research involving due date determination decisions[J]. European Journal of Operational Research,1989,38(2):156-166.

[4] CHEUNG C H, PO L M. A novel cross-diamond search algorithm for fast block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology,2002,12(12):1168-1177.

[5] REEVES C R. A genetic algorithm for flowshop sequencing[J]. Computers & Operations Research,1995,22(1):5-13.

[6] TU Xueping, SHI Cantao, LI Tieke. Improved genetic algorithm for permut ation flow-shop problem[J]. Computer Engineering and Applications,2009,45(36):50-53(in Chinese).[涂雪平,施燦濤,李鐵克.求解置換流水車間調(diào)度問題的改進(jìn)遺傳算法[J].計算機(jī)工程與應(yīng)用,2009,45(36):50-53.]

[7] ZHOU Chi, GAO Liang, GAO Haibing. Particle swarm optimization based algorithm for permutation flow shop scheduling[J]. Acta Elctronica Sinica,2006,34(11):2008-2011(in Chinese).[周 馳,高 亮,高海兵.基于PSO的置換流水車間調(diào)度算法[J].電子學(xué)報,2006,34(11):2008-2011.]

[8] LIAO C J, TSENG C T, LUARN P. A discrete version of particle swarm optimization for flowshop scheduling problems[J]. Computers & Operations Research,2007,34(10):3099-3111.

[9] OSMAN I H, POTTS C N. Simulated annealing for permutation flow-shop scheduling[J]. Omega,1989,17(6):551-557.

[10] NOWICKI E, SMUTNICKI C. A fast tabu search algorithm for the permutation flow-shop problem[J]. European Journal of Operational Research,1996,91(1):160-175.

[11] WANG Shengyao, WANG Ling, FANG Chen, et al. Advances in estimation of distribution algorithms[J].Control and Decision,2012,27(7):961-966(in Chinese).[王圣堯,王 凌,方 晨,等.分布估計算法研究進(jìn)展[J].控制與決策,2012,27(7):961-966.]

[12] CEBERIO J, IRUOZKI E, MENDIBURU A, et al. A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems[J]. Progress in Artificial Intelligence,2012,1(1):103-117.

[13] BALUJA S. Population-based incremental learning. a method for integrating genetic search based function optimization and competitive learning[R]. Pittsburgh,Pa.,USA:Carnegie-Mellon University,1994.

[14] CHEN Y M, CHEN M C, CHANG P C, et al. Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems[J]. Computers & Industrial Engineering,2012,62(2):536-545.

[15] PELIKAN M, GOLSBERG D E, CANTU-PAE-PAZ E. BOA:the Bayesian optimization algorithm[C]∥Proceedings of the 1st Annual Conference on Genetic and Evolutionary Computation-Volume 1. San Francisco, Cal., USA：Morgan Kaufmann Publishers Inc.,1999:525-532.

[16] CHANG P C, HUANG W H, Uu J L, et al. A block mining and re-combination enhanced genetic algorithm for the permutation flowshop scheduling problem[J]. International Journal of Production Economics,2013,141(1):45-55.

[17] WU Chuge, WANG Ling, ZHENG Xiaolong. An adaptive estimation of distribution algorithm for solving the unrelated parallel machine scheduling[J].Control and Decision,2016,31(12):2177-2182(in Chinese).[吳楚格,王 凌,鄭曉龍.求解不相關(guān)并行機(jī)調(diào)度的一種自適應(yīng)分布估計算法[J].控制與決策,2016,31(12):2177-2182.]

[18] CHANG P C, CHEN M H. A block based estimation of distribution algorithm using bivariate model for scheduling problems[J]. Soft Computing,2014,18(6):1177-1188.

[19] HSU C Y, CHANG P C, CHEN M H. A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem[J]. Computers & Industrial Engineering,2015,83(3):159-171.

[20] NAWAZ M, ENSCORE E E, HAM I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. Omega,1983,11(1):91-95.

[21] STEPHENS C R, SUKUMAR R. An introduction to data mining[J]. IEEE Transactions on Knowledge & Data Engineering, 2006, 22(6):753-754.

[22] SARATH K, RAVI V. Association rule mining using binary particle swarm optimization[J]. Engineering Applications of Artificial Intelligence,2013,26(8):1832-1840.

[23] MCNICHOLAS P D, MURPHY T B, O’REGAN M. Standardising the lift of an association rule[J]. Computational Statistics & Data Analysis,2008,52(10):4712-4721.

[24] CHANG P C, CHEN S S, FAN C Y. Mining gene structures to inject artificial chromosomes for genetic algorithm in single machine scheduling problems[J]. Applied Soft Computing,2008,8(1):767-777.

[25] CHANG P C, CHEN M H, TIWARI M K, et al. A block-based evolutionary algorithm for flow-shop scheduling problem[J]. Applied Soft Computing,2013,13(12):4536-4547.

[26] MILLER B L, GOLDBERG D E. Genetic algorithms, tournament selection, and the effects of noise[J]. Complex Systems,1995,9(3):193-212.

[27] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research,1993,64(2):278-285.

[28] REEVES C R. A genetic algorithm for flowshop sequencing[J]. Computers & Operations Research,1995,22(1):5-13.

[29] ZHANG Xianchao, ZHOU Hong. Variable parameters quantum-inspired evolutionary algorithm and its application in permutation flow-shop scheduling problem[J]. Computer Integrated Manufacturing Systems,2016,22(3):774-781(in Chinese).[張先超,周 泓.變參數(shù)量子進(jìn)化算法及其在求解置換流水車間調(diào)度問題中的應(yīng)用[J].計算機(jī)集成制造系統(tǒng),2016,22(3):774-781.]

[30] LIAN Z, GU X, JIAO B. A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan[J]. Applied Mathematics and Computation,2008,175(1):773-785.