劉 敏 張超勇 張國(guó)軍 孫 藝

華中科技大學(xué)數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢，430074

0 引言

置換流水車間調(diào)度問題（permutation flow shop scheduling problem，PFSSP）是目前研究最廣泛的一類典型調(diào)度問題，具有很重要的工程應(yīng)用價(jià)值。然而，絕大多數(shù)PFSSP（工件數(shù)n≥3）是NP－h(huán)ard問題，不存在多項(xiàng)式精確求解算法，因此，對(duì)該問題的研究不僅具有重要的實(shí)際意義，而且具有重要的理論意義。

國(guó)內(nèi)外學(xué)者在過去幾十年里做了大量研究，提出了許多解決置換流水車間調(diào)度問題的方法。這些方法大致可分為三類：精確算法、啟發(fā)式算法和元啟發(fā)式算法。由于NP－h(huán)ard問題的復(fù)雜性，精確算法只適用于小規(guī)模問題的求解。啟發(fā)式算法能夠快速構(gòu)造解，但是通常解的質(zhì)量較差。元啟發(fā)式算法能在較短時(shí)間內(nèi)獲得較高質(zhì)量的解，因此在求解置換流水車間調(diào)度問題中獲得廣泛應(yīng)用。

粒子群優(yōu)化（particle swarm optimization，PSO）算法是受鳥群捕食啟發(fā)產(chǎn)生的元啟發(fā)式算法，也是一種基于群體的優(yōu)化算法，最早由Kennedy等[1]于1995年提出。PSO算法是通過種群內(nèi)粒子之間的合作與競(jìng)爭(zhēng)而產(chǎn)生的群體智能優(yōu)化算法。與遺傳算法（genetic algorithm，GA）相比，PSO算法保留了基于種群的全局搜索策略，搜索模型簡(jiǎn)單，收斂速度快，魯棒性高，但是，PSO算法主要用于無約束連續(xù)函數(shù)的優(yōu)化。

目前，PSO算法在解決連續(xù)函數(shù)優(yōu)化方面取得了成功，但在如何應(yīng)用于離散組合優(yōu)化問題方面尚處于探索階段，其解決離散組合優(yōu)化問題主要有以下兩條途徑，一是采用基于隨機(jī)鍵的最小位置值（smallest position value，SPV）規(guī)則將標(biāo)準(zhǔn)PSO算法應(yīng)用于組合優(yōu)化問題中，二是采用向量編碼方式的離散粒子群算法解決離散組合優(yōu)化問題。Tasgetiren等[2]基于SPV規(guī)則提出了一種混合PSO算法，并將其用于求解最小化加權(quán)總拖后時(shí)間的單機(jī)流水車間調(diào)度問題，以及最小化最大完工時(shí)間和總流經(jīng)時(shí)間的PFSSP問題[3－4]。Rameshkumar等[5]采用向量編碼的方式提出了離散PSO算法，定義了粒子群算法的離散操作，并將其用于求解最小化最大完工時(shí)間的PFSSP問題。Lian等[6]直接將GA的交叉和變異操作作為PSO算法中粒子速度和位置的更新操作，提出了一種基于PSO的進(jìn)化算法，并將其應(yīng)用于求解最小化最大完工時(shí)間的PFSSP問題。

本文結(jié)合PSO算法和變鄰域搜索算法各自的優(yōu)點(diǎn)，設(shè)計(jì)了一種混合PSO算法（hybrid particle swarm optimization algorithm，HPSO）。該混合算法采用基于升序排列規(guī)則（ranked－order－value，ROV）的連續(xù)PSO算法對(duì)解空間進(jìn)行全局搜索，應(yīng)用基于關(guān)鍵路徑的變鄰域搜索算法對(duì)全局優(yōu)化的粒子進(jìn)行局部搜索，并使算法在分散搜索和集中搜索之間達(dá)到合理的平衡。通過對(duì)Taillard[7]和 Watson等[8]提出的基準(zhǔn)測(cè)試集進(jìn)行仿真實(shí)驗(yàn)，證實(shí)了算法的有效性。

1 HPSO算法求解置換流水車間調(diào)度問題

1.1 基于PSO算法的置換流水車間調(diào)度研究

基本粒子群算法采用速度－位置模型進(jìn)行搜索。算法初始化為一群隨機(jī)粒子，在每一次迭代中，粒子通過跟蹤兩個(gè)“極值”來更新自己：第一個(gè)是粒子本身所找到的最好解，叫做個(gè)體極值點(diǎn)（用pbest表示其位置），全局PSO中的另一個(gè)極值點(diǎn)是整個(gè)種群目前找到的最好解，稱為全局極值點(diǎn)（用gbest表示其位置），而局部PSO不用整個(gè)種群而是用其中一部分作為粒子的鄰居，所有鄰居中的最好解就是局部極值點(diǎn)（用lbest表示其位置）。在找到這兩個(gè)最好解后，粒子根據(jù)下式來更新自己的速度和位置：

粒子i的信息可以用n維向量表示，位置表示為Xi＝（xi1，xi2，…，xin），速度表示為vi＝ （vi1，vi2，…，vin），其他向量類似。 其中，ω（t）＝ω（t－1）β是慣性系數(shù)；β為線性遞減因子，其主要作用是產(chǎn)生擾動(dòng)，以防止算法的早熟收斂；c1和c2為學(xué)習(xí)因子，分別調(diào)節(jié)向個(gè)體最好粒子和全局最好粒子方向飛行的最大步長(zhǎng)，通常設(shè)c1＝c2＝2；r1和r2是[0，1]之間均勻產(chǎn)生的隨機(jī)數(shù)。

1.1.1 解的表示和ROV規(guī)則

對(duì)于PFSSP問題，最常用的編碼方式就是直接采用基于工件的排序。由于連續(xù)PSO算法中微粒的位置為連續(xù)值矢量，為了得到微粒位置矢量到工件排序的映射關(guān)系，基于隨機(jī)鍵編碼，王凌[9]提出了ROV規(guī)則，將粒子的連續(xù)位置矢量Xi＝（xi1，xi2，…，xin）轉(zhuǎn)換為離散的加工排序π，即機(jī)器上各工件的加工 順序，π ＝ ｛σ1，σ2，…，σn｝。

ROV規(guī)則具體描述如下：對(duì)于一個(gè)微粒的位置矢量，首先將值最小的分量位置賦予ROV值為1，其次將值第二小的分量位置賦予ROV值為2，依此類推，直到將所有的分量位置都賦予一個(gè)唯一的ROV值，從而基于ROV值構(gòu)造出一個(gè)工件排序。

1.1.2 種群初始化

初始種群一方面應(yīng)該具有一定的分布性，能夠以較大的概率覆蓋整個(gè)解空間，另一方面為了提高種群的搜索效率，避免盲目搜索，初始種群中也應(yīng)該包括部分質(zhì)量較高的解。因此，本文的初始解采用以下兩種方式產(chǎn)生，一是用構(gòu)造性啟發(fā)式方法產(chǎn)生，二是在一連續(xù)區(qū)間內(nèi)隨機(jī)產(chǎn)生。在構(gòu)造性啟發(fā)式方法中，本文采用NEH啟發(fā)式算法，它是由Nawaz、Enscore和 Ham共同提出，是當(dāng)前解決PFSSP性能最好的啟發(fā)式算法。該算法步驟如下：①按工件在機(jī)器上的總加工時(shí)間遞減的順序排列n個(gè)工件；②取前兩個(gè)工件調(diào)度，使部分總完工時(shí)間達(dá)到最小；③把第k（k＝3，4，…，n）個(gè)工件插入到k個(gè)可能的位置，求得最小的部分總完工時(shí)間。

NEH啟發(fā)式算法產(chǎn)生的解是工件序列，在此，按如下方式將其轉(zhuǎn)換為一定區(qū)間內(nèi)的位置矢量：

式中，xNEH，j為粒子在第j維的位置值；sNEH，j為通過NEH算法得到的解的第j維工件序號(hào)；xmax，j、xmin，j分別為連續(xù)空間上粒子位置矢量的上界值和下界值；r3為[0，1]間均勻產(chǎn)生的隨機(jī)數(shù)。

xij、vij隨機(jī)產(chǎn)生的方式為

其中，xij在連續(xù)區(qū)間[xmin，xmax]變化，vij在連續(xù)區(qū)間[vmin，vmax]變化。

1.2 基于變鄰域搜索的置換流水車間調(diào)度研究

Mladenovic等[10]在1997年提出了一種變鄰域搜索算法，在很多問題的求解中得到了很好的應(yīng)用。不過，變鄰域搜索的效率取決于鄰域結(jié)構(gòu)的選擇。Zobolas等[11]將遺傳算法與變鄰域搜索算法結(jié)合來求解置換流水車間調(diào)度問題，Bassem等[12]將分布評(píng)估算法與變鄰域搜索算法結(jié)合來求解轉(zhuǎn)換流水車間調(diào)度問題。然而，他們對(duì)所有工件均采取插入移動(dòng)和交換移動(dòng)兩種鄰域操作方式，沒有考慮問題的具體鄰域知識(shí)。本文采用基于關(guān)鍵路徑的兩種鄰域結(jié)構(gòu)，基于變鄰域搜索求解置換流水車間調(diào)度問題，有效地提高了算法集中搜索能力。

1.2.1 關(guān)鍵路徑

針對(duì)問題知識(shí)設(shè)計(jì)的局部搜索是鄰域搜索元啟發(fā)式算法的關(guān)鍵組成部分。對(duì)于車間調(diào)度問題，例如流水車間調(diào)度問題（flow shop scheduling problem，F(xiàn)SSP），可行調(diào)度的關(guān)鍵塊中工序的局部移動(dòng)是該類問題最有效的更新算子之一。

路徑和關(guān)鍵路徑可以由一個(gè)有向柵格圖來分析，G（π）＝（N，E）是表示排列π的一個(gè)柵格圖，其中N 是所有節(jié)點(diǎn)的集合，Ni，j∈ N，i∈ ｛1，2，…，m｝，j∈ ｛1，2，…，n｝，Nij在N中具有權(quán)重pi，π（j），而 E 則是所有箭頭指向的有向邊的集合，它不具有權(quán)重。圖1所示為G（π）的有向柵格圖，π＝｛2，7，5，3，6，1，4｝為工件數(shù)n＝7、機(jī)器數(shù)m＝5的置換流水車間調(diào)度問題的一個(gè)排列，粗箭頭所示的為該排列的關(guān)鍵路徑。

圖1 有向柵格圖G（π）

由圖1所示的有向柵格圖可以得到排列的關(guān)鍵路徑，同時(shí)找到關(guān)鍵路徑上的關(guān)鍵塊Bk，在這里共有3個(gè)關(guān)鍵塊，分別為：B1＝｛2，7，5｝、B2＝｛5，3，6｝和B3＝｛6，1，4｝。關(guān)鍵塊所對(duì)應(yīng)的機(jī)器分別為m1＝2、m2＝3、m3＝5。

1.2.2 基于關(guān)鍵路徑的變鄰域搜索

Nowicki等[13]、Grabowski等[14]分別在1996年和2004年利用關(guān)鍵路徑和塊的概念，針對(duì)置換流水車間調(diào)度問題提出了一種有效的鄰域結(jié)構(gòu)，并將其成功地運(yùn)用在了禁忌搜索（tabu search，TS）算法中，取得了較好的結(jié)果。本文將這兩種鄰域結(jié)構(gòu)運(yùn)用在了變鄰域搜索算法中。

在Grabowski等[14]提出的鄰域結(jié)構(gòu)（簡(jiǎn)稱為鄰域結(jié)構(gòu)Gw）中，執(zhí)行插入移動(dòng)時(shí)，將被移動(dòng)的工件插入到相鄰關(guān)鍵塊邊界之后，其具體的移動(dòng)操作如圖2所示（在圖2中標(biāo)記為黑色的工件為關(guān)鍵塊邊界，橢圓包含的區(qū)域是需要考慮插入的位置，下同）。

圖2 鄰域結(jié)構(gòu)Gw的移動(dòng)操作

在Nowicki等[13]提出的鄰域結(jié)構(gòu)（簡(jiǎn)稱為鄰域結(jié)構(gòu)Ns）中，執(zhí)行插入移動(dòng)時(shí)，當(dāng)要被移動(dòng)的工件在關(guān)鍵塊內(nèi)時(shí)，他們僅考慮了相鄰關(guān)鍵塊中的插入位置，如圖3a所示，如果要被移動(dòng)的工件在關(guān)鍵塊邊界上，除了考慮相鄰關(guān)鍵塊內(nèi)的位置外，其臨近的位置也要考慮在內(nèi)，如圖3b所示。

圖3 鄰域結(jié)構(gòu)Ns的移動(dòng)操作

由此，筆者設(shè)計(jì)了包含兩種基于關(guān)鍵路徑的不同鄰域結(jié)構(gòu)的變鄰域搜索算法，將鄰域結(jié)構(gòu)Gw作為第一鄰域結(jié)構(gòu)，鄰域結(jié)構(gòu)Ns作為第二鄰域結(jié)構(gòu)。算法流程如圖4所示，其中Nk（s）表示解s的第k種鄰域，具體的算法流程如下：

（1）初始化。選擇鄰域結(jié)構(gòu)集Nk，初始化內(nèi)外循環(huán)步長(zhǎng)inloop，并給出鄰域搜索初始解s0，外循環(huán)次數(shù)i＝0。

（2）隨機(jī)產(chǎn)生s0的第一種鄰域結(jié)構(gòu)s，s∈N1（s0），內(nèi)循環(huán)次數(shù)l＝0，并循環(huán)步驟（3）～ 步驟（8），直到達(dá)到外循環(huán)步長(zhǎng)outloop。

（3）循環(huán)步驟（4）～ 步驟（7），直到達(dá)到內(nèi)循環(huán)步長(zhǎng)。

（4）設(shè)置k＝1。

（5）循環(huán)步驟（6）～ 步驟（7），直到k＝kmax。

（6）產(chǎn)生s的第k種鄰域結(jié)構(gòu)s1，s1∈Nk（s）。

圖4 基于關(guān)鍵路徑的變鄰域搜索流程

（7）若序列s1優(yōu)于s，則用s1替代s并設(shè)置k＝1，否則，將k值加1。

（8）若序列s優(yōu)于s0，則用s替代s0。（9）輸出局部搜索最優(yōu)序列s0。

1.3 混合粒子群優(yōu)化算法流程

本文結(jié)合了問題本身的鄰域知識(shí)結(jié)構(gòu)，把PSO算法和變鄰域搜索算法有機(jī)結(jié)合，設(shè)計(jì)了一種混合粒子群優(yōu)化算法，使分散搜索和集中搜索達(dá)到有機(jī)平衡，混合粒子群優(yōu)化算法的流程如圖5所示。具體的算法流程如下。

圖5 混合粒子群算法具體流程

（1）初始化算法參數(shù)——慣性系數(shù)w、認(rèn)知系數(shù)c1和社會(huì)系數(shù)c2等。

（2）初始化粒子種群。①利用NEH算法生成種群的10%個(gè)工件加工序列，評(píng)價(jià)其調(diào)度目標(biāo)，并根據(jù)式（3）將加工序列轉(zhuǎn)換為一個(gè)粒子的位置矢量；②隨機(jī)產(chǎn)生余下種群的90%個(gè)粒子的位置矢量，根據(jù)ROV規(guī)則得出各粒子對(duì)應(yīng)的工件加工序列，并根據(jù)加工序列評(píng)價(jià)各粒子的調(diào)度目標(biāo)；③隨機(jī)初始化種群中所有粒子的速度矢量；④令各粒子的局部最優(yōu)為當(dāng)前位置，并根據(jù)比較的各粒子的調(diào)度目標(biāo)確定其中最好的粒子的位置，并將其作為全局最優(yōu)。

（3）循環(huán)步驟（4）～步驟（6）直到滿足停止條件，這里定義的停止條件是種群代數(shù)達(dá)到給定的最大迭代次數(shù)。

（4）對(duì)所有粒子執(zhí)行下列操作：①更新所有粒子的速度和位置；②根據(jù)ROV規(guī)則，確定各粒子位置矢量所對(duì)應(yīng)的工件加工序列，并評(píng)價(jià)各粒子調(diào)度目標(biāo)；③更新各粒子的個(gè)體極值。

（5）更新全體極值。

（6）對(duì)全體極值執(zhí)行變鄰域搜索算法：①找出全局極值的關(guān)鍵路徑，設(shè)計(jì)鄰域結(jié)構(gòu)；②執(zhí)行基于關(guān)鍵路徑的變鄰域搜索算法；③更新全局極值。

（7）輸出全體極值。

2 實(shí)例仿真與結(jié)果分析

為了驗(yàn)證提出的混合粒子群優(yōu)化算法，本文測(cè)試數(shù)據(jù)采用Taillard[7]在1993年提出的120個(gè)基準(zhǔn)測(cè)試問題，以及Watson等[8]在2002年提出的隨機(jī)型基準(zhǔn)測(cè)試問題，應(yīng)用提出的算法求解這些基準(zhǔn)實(shí)例，并與其他文獻(xiàn)算法進(jìn)行比較，以驗(yàn)證算法的有效性。

本文算法編程采用Visual C＋＋6.0，計(jì)算機(jī)CPU為Intel Celeron M520，主頻為1.6GHz，物理內(nèi)存為512MB，操作系統(tǒng)為Windows XP。實(shí)驗(yàn)參數(shù)設(shè)置如下：c1＝c2＝2.0，慣性系數(shù)w初始值設(shè)為0.9，β＝0.975，β最小不能小于0.4，粒子的最小位置值xmin＝0，粒子的最大位置值xmax＝4.0，粒子的最小速度值vmin＝14.0，粒子的最大速度值vmax＝4.0，最大迭代次數(shù)設(shè)為400，種群規(guī)模設(shè)為40，每個(gè)實(shí)例獨(dú)立連續(xù)運(yùn)行10次。Taillard基準(zhǔn)測(cè)試集包含120個(gè)流水線調(diào)度問題實(shí)例，通過網(wǎng)站 http：／／mistic.heig－vd.ch／taillard／中的FSP實(shí)例可以獲得這些實(shí)例的數(shù)據(jù)和當(dāng)前最好解。本文選取每種規(guī)模系列問題中的第一個(gè)和第五個(gè)問題進(jìn)行計(jì)算，并運(yùn)用提出的混合粒子群優(yōu)化算法（HPSO）與 Nearchou[15]提出的多算子遺傳算法、Lian等[16]提出的一種新的粒子群算法（NPSO）和Zhang等[17]提出的混合輪換兩階段粒子群算法（ATPPSO）進(jìn)行比較，結(jié)果如表1所示。表1中也列出了本文算法獲得的最優(yōu)解（best solution，BS）、最差解（worst solution，WS）、多次運(yùn)行獲得的解的平均值（average solution，AS）和最優(yōu)相對(duì)偏差（best relative error，BRE）。由表1可知，本文算法求解Taillard系列問題能夠取得很好的效果，相比其他幾種算法本文算法能夠更好地收斂于最優(yōu)解。

2002年，Watson等[8]針對(duì)置換流水車間調(diào)度問題給出了一類新的基準(zhǔn)問題測(cè)試集，該測(cè)試集共有14 000個(gè)問題，分為隨機(jī)型問題和構(gòu)造型問題，其中隨機(jī)型問題有800個(gè)，分別為20×20rand問題，50×20rand問題，100×20rand問題，200×20rand問題，20×20rand－narrow問題，50×20rand－narrow問題，100×20randnarrow問題和200×20rand－narrow問題8種，每種有100個(gè)同等規(guī)模的問題，其中的rand問題的數(shù)值從1～99間隨機(jī)產(chǎn)生，rand－narrow問題的數(shù)值從45～55間隨機(jī)產(chǎn)生，這些測(cè)試集的數(shù)據(jù)和Watson等給出的最優(yōu)解都能在網(wǎng)站http：／／www.cs.colostate.edu／sched／generator／中 查到。通過本算法對(duì)其中的800個(gè)隨機(jī)型問題進(jìn)行了測(cè)試，將其中的部分問題結(jié)果列于表2中。從表2可以看到，90%的被測(cè)試問題都能達(dá)到先前給出的問題的最好解，并改進(jìn)了其中8個(gè)問題的最好解結(jié)果，這一結(jié)果充分表現(xiàn)了本文算法具有良好的收斂性。

表1 不同調(diào)度算法Taillard基準(zhǔn)問題測(cè)試結(jié)果

表2 算法求解Watson基準(zhǔn)問題測(cè)試結(jié)果

3 結(jié)束語

本文針對(duì)置換流水車間調(diào)度問題提出了一種結(jié)合粒子群優(yōu)化算法和變鄰域搜索算法的混合優(yōu)化算法。在混合算法中，采用NEH算法和隨機(jī)方式產(chǎn)生初始解，采用基于ROV規(guī)則連續(xù)PSO算法進(jìn)行有效的全局搜索；應(yīng)用基于關(guān)鍵路徑的變鄰域搜索算法進(jìn)行局部搜索，使分散搜索和集中搜索達(dá)到有效的平衡，提高了算法的搜索能力。運(yùn)用混合算法求解了Taillard基準(zhǔn)問題和 Watson基準(zhǔn)問題，并將測(cè)試結(jié)果與其他算法比較，證實(shí)了該算法的有效性。

在今后的工作中，可從以下兩個(gè)方面進(jìn)行改進(jìn)研究：一方面，用局部搜索能力更強(qiáng)的禁忌搜索算法代替變鄰域搜索算法；另一方面，對(duì)鄰域結(jié)構(gòu)采用評(píng)估策略，從而進(jìn)一步提高算法的搜索效率。

[1]Kennedy J，Eberhart R C.Particle Swarm Optimization[C]／／Proceedings of International Conference on Neural Net－works.Piscataway：IEEE Press，1995：1942-1948.

[2]Tasgetiren M F，Sevkli M，Liang Y C，et al.Particle Swarm Optimization Algorithm Forpermutation Flowshop Sequencing Problem[J].Lecture Notes in Computer Science，2004，3172：382-389.

[3]Tasgetiren M F，Liang Y C，Sevkli M，et al.Particle Swarm Optimization and Differential Evolution for the Singlemachine Total Weighted Tardiness Problem[J].Int.J.Prod.Res.，2006，44：4737-4754.

[4]Tasgetiren M F，Liang Y C，Sevkli M，et al.A Particle Swarm Optimization Algorithm for Makespanand Total Flowtime Minimization in the Permutation Flowshop Sequencing Problem[J].European Journal of Operational Research，2007，177：1930-1947.

[5]Rameshkumar K，Suresh R K，Mohanasundaram K M.Discrete Particle Swarm Optimization（DPSO）Algorithm for Permutation Flowshop Scheduling to Minimize Makespan[J].Advances in Natural Computation，2005，3612：572-581.

[6]Lian Z G，Gu X S，Jiao B.A Similar Particle Swarm Optimization Algorithm Forpermutation Flowshop Scheduling to Minimize Makespan[J].Appl.Math.Comput.，2006，175：773-785.

[7]Taillard E.Benchmarks for Basic Scheduling Problems[J].European Journal of Operational Research，1993，64：278-285.

[8]Watson J P，Barbulescu L，Whitley L D，et al.Contrasting Structured and Random Permutation Flowshop Scheduling Problems：Search Space Topology and Algorithm Performance[J].ORSA Journal of Computing，2002，14（2）：98-123.

[9]王凌.微粒群優(yōu)化與調(diào)度算法[M].北京：清華大學(xué)出版社，2008.

[10]Mladenovic N，Hansen P.Variable Neighborhood Search[J].Computers and Operations Research，1997，24：1097-1100.

[11]Zobolas G I，Tarantilis C D，Ioannou G.Minimizing Makespan in Permutation Flow Shop Schedulingproblems Using a Hybrid Metaheuristicalgorithm[J].Computers ＆ Operations Research，2009，36：1249-1267.

[12]Bassem J，Mansour E，Patrick S.An Estimation of Distribution Algorithm Forminimizing the Total Flowtime in Permutation Flowshop Scheduling Problems[J].Computers ＆ Operations Research，2009，36：2638-2646.

[13]Nowicki E，Smutnicki C.A Fast Tabu Search Algorithm for Thepermutation Flowshop Problem[J].European Journal of Operational Research，1996，91：160-175.

[14]Grabowski J，Wodecki M.A Very Fast Tabu Search Algorithm for the Permutation Flow Shop Problem with Makespan Criterion[J].Computers and Operations Research，2004，31（11）：1891-1909.

[15]Nearchou.The Effect of Various Operators on the Genetic Search Forlarge Scheduling Problems[J].International Journal of Production Economy，2004，88：191-203.

[16]Lian Z G，Gu X S，Jiao B，et al.A Novel Particle Swarm Optimization Algorithm Forpermutation Flow－shop Scheduling to Minimize Makespan[J].Chaos Solitons and Fractals，2008，35（5）：851-861.

[17]Zhang C S，Ning J X，Ouyang D T，et al.A Hybrid Alternate Two Phases Particle Swarm Optimization Algorithmfor Flow Shop Scheduling Problem[J].Computers ＆Industrial Engineering，2010，58：1-11.