基于混合粒子群優化算法的置換流水車間調度問題研究

劉 敏 張超勇 張國軍 孫 藝

華中科技大學數字制造裝備與技術國家重點實驗室，武漢，430074

0 引言

置換流水車間調度問題（permutation flow shop scheduling problem，PFSSP）是目前研究最廣泛的一類典型調度問題，具有很重要的工程應用價值。然而，絕大多數PFSSP（工件數n≥3）是NP－hard問題，不存在多項式精確求解算法，因此，對該問題的研究不僅具有重要的實際意義，而且具有重要的理論意義。

國內外學者在過去幾十年里做了大量研究，提出了許多解決置換流水車間調度問題的方法。這些方法大致可分為三類：精確算法、啟發式算法和元啟發式算法。由于NP－hard問題的復雜性，精確算法只適用于小規模問題的求解。啟發式算法能夠快速構造解，但是通常解的質量較差。元啟發式算法能在較短時間內獲得較高質量的解，因此在求解置換流水車間調度問題中獲得廣泛應用。

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

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

本文結合PSO算法和變鄰域搜索算法各自的優點，設計了一種混合PSO算法（hybrid particle swarm optimization algorithm，HPSO）。該混合算法采用基于升序排列規則（ranked－order－value，ROV）的連續PSO算法對解空間進行全局搜索，應用基于關鍵路徑的變鄰域搜索算法對全局優化的粒子進行局部搜索，并使算法在分散搜索和集中搜索之間達到合理的平衡。通過對Taillard[7]和 Watson等[8]提出的基準測試集進行仿真實驗，證實了算法的有效性。

1 HPSO算法求解置換流水車間調度問題

1.1 基于PSO算法的置換流水車間調度研究

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

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

1.1.1 解的表示和ROV規則

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

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

1.1.2 種群初始化

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

NEH啟發式算法產生的解是工件序列，在此，按如下方式將其轉換為一定區間內的位置矢量：

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

xij、vij隨機產生的方式為

其中，xij在連續區間[xmin，xmax]變化，vij在連續區間[vmin，vmax]變化。

1.2 基于變鄰域搜索的置換流水車間調度研究

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

1.2.1 關鍵路徑

針對問題知識設計的局部搜索是鄰域搜索元啟發式算法的關鍵組成部分。對于車間調度問題，例如流水車間調度問題（flow shop scheduling problem，FSSP），可行調度的關鍵塊中工序的局部移動是該類問題最有效的更新算子之一。

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

圖1 有向柵格圖G（π）

由圖1所示的有向柵格圖可以得到排列的關鍵路徑，同時找到關鍵路徑上的關鍵塊Bk，在這里共有3個關鍵塊，分別為：B1＝｛2，7，5｝、B2＝｛5，3，6｝和B3＝｛6，1，4｝。關鍵塊所對應的機器分別為m1＝2、m2＝3、m3＝5。

1.2.2 基于關鍵路徑的變鄰域搜索

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

在Grabowski等[14]提出的鄰域結構（簡稱為鄰域結構Gw）中，執行插入移動時，將被移動的工件插入到相鄰關鍵塊邊界之后，其具體的移動操作如圖2所示（在圖2中標記為黑色的工件為關鍵塊邊界，橢圓包含的區域是需要考慮插入的位置，下同）。

圖2 鄰域結構Gw的移動操作

在Nowicki等[13]提出的鄰域結構（簡稱為鄰域結構Ns）中，執行插入移動時，當要被移動的工件在關鍵塊內時，他們僅考慮了相鄰關鍵塊中的插入位置，如圖3a所示，如果要被移動的工件在關鍵塊邊界上，除了考慮相鄰關鍵塊內的位置外，其臨近的位置也要考慮在內，如圖3b所示。

圖3 鄰域結構Ns的移動操作

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

（1）初始化。選擇鄰域結構集Nk，初始化內外循環步長inloop，并給出鄰域搜索初始解s0，外循環次數i＝0。

（2）隨機產生s0的第一種鄰域結構s，s∈N1（s0），內循環次數l＝0，并循環步驟（3）～ 步驟（8），直到達到外循環步長outloop。

（3）循環步驟（4）～ 步驟（7），直到達到內循環步長。

（4）設置k＝1。

（5）循環步驟（6）～ 步驟（7），直到k＝kmax。

（6）產生s的第k種鄰域結構s1，s1∈Nk（s）。

圖4 基于關鍵路徑的變鄰域搜索流程

（7）若序列s1優于s，則用s1替代s并設置k＝1，否則，將k值加1。

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

1.3 混合粒子群優化算法流程

本文結合了問題本身的鄰域知識結構，把PSO算法和變鄰域搜索算法有機結合，設計了一種混合粒子群優化算法，使分散搜索和集中搜索達到有機平衡，混合粒子群優化算法的流程如圖5所示。具體的算法流程如下。

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

（1）初始化算法參數——慣性系數w、認知系數c1和社會系數c2等。

（2）初始化粒子種群。①利用NEH算法生成種群的10%個工件加工序列，評價其調度目標，并根據式（3）將加工序列轉換為一個粒子的位置矢量；②隨機產生余下種群的90%個粒子的位置矢量，根據ROV規則得出各粒子對應的工件加工序列，并根據加工序列評價各粒子的調度目標；③隨機初始化種群中所有粒子的速度矢量；④令各粒子的局部最優為當前位置，并根據比較的各粒子的調度目標確定其中最好的粒子的位置，并將其作為全局最優。

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

（4）對所有粒子執行下列操作：①更新所有粒子的速度和位置；②根據ROV規則，確定各粒子位置矢量所對應的工件加工序列，并評價各粒子調度目標；③更新各粒子的個體極值。

（5）更新全體極值。

（6）對全體極值執行變鄰域搜索算法：①找出全局極值的關鍵路徑，設計鄰域結構；②執行基于關鍵路徑的變鄰域搜索算法；③更新全局極值。

（7）輸出全體極值。

2 實例仿真與結果分析

為了驗證提出的混合粒子群優化算法，本文測試數據采用Taillard[7]在1993年提出的120個基準測試問題，以及Watson等[8]在2002年提出的隨機型基準測試問題，應用提出的算法求解這些基準實例，并與其他文獻算法進行比較，以驗證算法的有效性。

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

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

表1 不同調度算法Taillard基準問題測試結果

表2 算法求解Watson基準問題測試結果

3 結束語

本文針對置換流水車間調度問題提出了一種結合粒子群優化算法和變鄰域搜索算法的混合優化算法。在混合算法中，采用NEH算法和隨機方式產生初始解，采用基于ROV規則連續PSO算法進行有效的全局搜索；應用基于關鍵路徑的變鄰域搜索算法進行局部搜索，使分散搜索和集中搜索達到有效的平衡，提高了算法的搜索能力。運用混合算法求解了Taillard基準問題和 Watson基準問題，并將測試結果與其他算法比較，證實了該算法的有效性。

在今后的工作中，可從以下兩個方面進行改進研究：一方面，用局部搜索能力更強的禁忌搜索算法代替變鄰域搜索算法；另一方面，對鄰域結構采用評估策略，從而進一步提高算法的搜索效率。

[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]王凌.微粒群優化與調度算法[M].北京：清華大學出版社，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.