張 敏，汪 洋，方 侃

(天津大學 管理與經濟學部,天津 300072)

0 引言

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

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

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

1 置換流水車間調度問題描述

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

PFSP用數學模型描述如下：若用p(i,j)表示工件j在機器i上的加工時間(假設工件準備時間包含在加工時間內)，并且工件的排序為π{π1,π2,…,πn}，假設各工件按照機器1～機器m的順序加工，則n個工件m臺機器的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)調度工件排序π*，使得對于其他任意的工件排序π都有

Cmax(π*)≤Cmax(π)。

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

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

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

2.1 改進NEH算法初始化種群

2.1.1 NEH算法

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

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

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

本文借助NEH算法思想提出了改進NEH方法，并在種群初始化階段加以應用。

2.1.2 應用改進NEH法進行種群初始化

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

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

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

步驟4重復步驟2和步驟3，直到產生含N個母體的初始種群。

2.2 運用關聯規(guī)則挖掘區(qū)塊

2.2.1 關聯規(guī)則

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

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

(6)

(7)

(8)

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

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

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

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

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

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

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

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

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

2.2.3 區(qū)塊篩選

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

2.3 組合人造解

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

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

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

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

2.4 突變機制

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

2.5 母體重組

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

2.5.1 NEH交換法

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

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

NEH交換法的運行機制如圖7所示。

2.5.2 相鄰交換法

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

步驟1隨機的選擇N個切點，將染色體切割成數個片段。

步驟2選擇片段中最長的片段進行相鄰交換。

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

步驟4重復步驟3，直到出現與原片段相同的排序為止。

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

NS的運行機制如圖8所示。

2.6 保留優(yōu)勢解

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

3 實驗結果與分析

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

(9)

(10)

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

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

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

續(xù)表1

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

由表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，且具有很強的魯棒性。

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

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

續(xù)表3

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

4 結束語

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

參考文獻:

[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).[劉 昶,李 冬,彭 慧,等.求解混合流水車間調度問題的變量相關EDA算法[J].計算機集成制造系統,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).[涂雪平,施燦濤,李鐵克.求解置換流水車間調度問題的改進遺傳算法[J].計算機工程與應用,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的置換流水車間調度算法[J].電子學報,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].控制與決策,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).[吳楚格,王 凌,鄭曉龍.求解不相關并行機調度的一種自適應分布估計算法[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).[張先超,周 泓.變參數量子進化算法及其在求解置換流水車間調度問題中的應用[J].計算機集成制造系統,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.