基于雙模式PSO算法求解置換流水車間調度問題

馬祎航，陶文華，劉 陽

（1.遼寧石油化工大學 信息與控制工程學院，遼寧 撫順 113000；2.中國石油撫順石化公司烯烴廠 遼寧 撫順 113009）

基于雙模式PSO算法求解置換流水車間調度問題

馬祎航1，陶文華1，劉 陽2

（1.遼寧石油化工大學 信息與控制工程學院，遼寧 撫順 113000；2.中國石油撫順石化公司烯烴廠 遼寧 撫順 113009）

針對粒子群算法求解置換流水車間調度這類NP-hard問題存在的早熟問題，本文提出了一種基于隨機鍵編碼的雙模式飛行粒子群算法。首先，基于ROV規則對工件加工順序進行隨機鍵編碼。其次，粒子在搜索過程中采用帶有自適應慣性權重的雙模飛行方式來更新位置和速度，避免粒子群陷入早熟收斂狀態。為了提高解的質量，每次迭代過程中對PSO優化得到的種群最優解進行鄰域局部搜索。最后，通過對標準測試集的數值仿真及與其他PSO算法的比較，證實了所提算法求解該問題的有效性與可行性。

置換流水車間調度；粒子群算法；鄰域搜索；隨機鍵

置換流水車間調度問題（Permutation Flow Shop Scheduling Problem，PFSP）是制造系統中重要的規劃問題[1]，是在流水車間調度問題的基礎上，增加了每臺機器加工各工件順序相同的這一特定的約束條件[2]，已證明3臺即為NP-hard問題[3]。許多實際生產過程都可以簡化成這類問題，而PFSP的優化研究能夠為企業帶來更大的生產效益，因此研究PFSP具有重要的理論和實際意義。

求解PFSP的方法主要分為3大類：精確算法、啟發式方法和智能算法。雖然理論上精確算法能得到最優解，但其運算時間一般無法接受，因此被用在解決小規模問題。啟發式方法根據問題特性，能在較短時間內構造出解，但難以保證解的質量[4]。近年來，隨著計算智能的發展，求解PFSP的方法逐步從精確方法和啟發式方法發展到智能算法[5]，如遺傳算法[6]、量子算法[7]、布谷鳥算法[8]等，盡管這些方法在一些問題上具有良好的收斂性，但在大規模問題上卻無法保證解的質量，很容易陷入早熟。

粒子群優化 （Particle Swarm Optimization，PSO）算法于1995年由Kennedy和E-berhart提出[9]。它作為一種基于群體的改進啟發式算法，盡管已初步成功地用于解決神經網絡訓練、模糊系統控制和組合優化等問題[10]，但在生產調度方面的研究還是很少的。針對置換流水線調度問題，文中采用基于ROV規則的隨機鍵編碼[11]，實現標準PSO操作直接應用在離散優化問題上，而且也保證了解的合法性及解空間的完備性。為了減小陷入局部最優解的可能性，粒子在搜索過程中采用變軌與不變軌雙模式飛行并根據群體信息反饋和自身狀態選擇自己的飛行模式，慣性權重采用自適應線性調節，最后為了提高解的質量，對粒子群算法優化后得到的最優解進行鄰域局部搜索。

1 問題描述

置換流水車間調度問題是n個工件在m臺機器上的流水加工過程，屬于流水車間調度的一類問題，其具有以下特征：

1）每個工件在各機器上加工順序相同；

2）每臺機器上所有工件的加工順序相同；

3）每個工件在每臺機器上只加工一次；

4）每臺機器在任意時刻只能加工一個工件。

已知工件在各機器上的準備時間和加工時間，問題目標是尋找一個工件加工順序，使各工件按該順序加工的總完成時間（makespan）最小。假設n個工件在m臺機器上加工，P為工件i（i=1，2，...，n）在機j（j=1，2，...，m）上的加工時間，C（i，j）為工件i在機器j上的加工完成時間。則C（i，j）的計算公式可描述如下：

2 雙模式粒子群算法

2.1 隨機鍵編碼

本文對粒子的位置矢量采用基于升序排列規則（Ranked—Order—Value，ROV）的隨機鍵編碼實現粒子連續位置到離散值的轉換，無需修改PSO算法的進化操作，而且能夠保證調度方案的可行性。

ROV規則具體描述如下：對于一個微粒的位置矢量，首先將值最小的分量位置賦予ROV值為1，其次將值第二小的分量位置賦予ROV值為2，依此類推，直到將所有的分量位置都賦予一個唯一的ROV值，從而基于ROV值構造出一個工件排序。以3*4 PFSP為例，已知3個工件在各機器上加工時間為：

假設優化得到第k個粒子的位置為：

經ROV規則得到一個序列Lk：

按照該序列對工件加工重新排序得：

2.2 自適應慣性權重

為了提高算法的收斂穩定性及收斂速度，文中采用一種自適應慣性權重的方法。迭代次數與慣性權重 成反比是比較廣泛應用的PSO算法慣性權重控制方案：

式中，ω為粒子i在第t次迭代中的取值；Iter為預先設定的最大迭代次數；t為當前迭代數；ωmax為慣性權重最大值，典型取值為0.9；ωmin為慣性權重最小值，典型取值為0.4。

通過全體粒子上一輪迭代結束后適應值的變化來選擇慣性權重的取值：

式中，表示粒子i在第i次迭代后的適應值；表示粒子i在第i次迭代后的適應值變化。然后確定各粒子在當前迭代中慣性權重的最終取值：

當t?[1，2]時，慣性權重按式（6）取值；當t?[3，Iter]時，慣性權重按式（7）、式（8）取值。

2.3 粒子飛行模式

為了提高算法的全局搜索能力，避免過早的陷入早熟，本文采用雙模式飛行粒子群算法[12]假設粒子個數為N，第i粒子經過的歷史最優位置（i=1，2，…，N）：

所有粒子經過的最優位置：

分析粒子當前位置的優劣情況：把群體按適應度的大小排序，設粒子群體規模是M，記i粒子t時刻的序號為s（t），此時，s（t）=1表示i粒子t時刻的位置在群體中最優。若s（t）=M則表示i粒子t時刻的位置在群體中最差。粒子依據當前位置優劣情況按式（11）（12）確定飛行模式。

粒子不變軌飛行模式：

粒子變軌飛行模式：

決策因子：

其中，λ服從（0，1）的均勻隨機分布，k為[1，2，...，D]的一個隨機整數，即i粒子的第d維變軌繞到Gbest（t）的第k維，則稱i粒子按變軌飛行模式飛行。DFi（t）為[0，1]的決策因子，它反映i粒子的當前狀態，是i粒子確定其下一步飛行模式的依據。適應度最優的決策因子是0，而適應度最差的決策因子是1。換言之，處于較優位置的粒子傾向于選擇式（11）的不變軌飛行模式，而處于較差位置的粒子傾向于選擇式（12）的變軌飛行。

2.4 鄰域局部搜索

在PSO每次迭代優化得到加工順序之后，通過局部搜索進一步尋找工件加工最佳順序。文中采用鄰域局部搜索方法來確定機器加工序列[13]。步驟如下：1）DMPSO優化后得到所有工件的一個排序β；2）令k=1，取出β中的前2個工件，對兩個工件先后加工次序進行評價，選擇調度解小的序列作為當前序列；3）令k=k+1，依次將第k個工件插入到當前序列的k個可能的位置，從中選擇調度解小的序列作為當前序列；4）重復步驟3），直到β中所有工件均得到新的排序操作。

3 雙模式粒子群算法流程圖

求解PFSP的雙模式粒子群算法（DMPSO）流程如圖1所示。

圖1 雙模式粒子群算法流程圖

4 仿真測試與比較

為了驗證本文算法求解PFSP的性能，選擇Car類[14]和Rec類[15]問題中進行仿真測試。仿真環境：Windows7操作系統，MATLAB2010，處理器2.9 GHz，內存2 GB。參數設置為粒子群算法進化次數M=100，種群規模N=100，加速因子 c1= 1.5，c2=2.5，λ=0.732，粒子位置變化范圍為[1，10]。慣性權重ωmax=0.9，ωmin=0.4，c*為問題最優值或目前已知下界值，RE表示算法求出的最優值C與C*相對誤差 （RE=（c-c*）/c*× 100%），對各類問題獨立運行20次得到的平均值，ARE表示平均相對誤差。表1為在忽略鄰域搜索算法的作用情況下，本文算法與恒定慣性權重DMPSO算法的平均相對誤差ARE比較，表2為常規粒子群算法、量子粒子群算法[7]平均相對誤差進行對比，圖2給出的是DMPSO與PSO兩種算法求解Car8的收斂曲線。

圖2 求解Car8問題的DMPSO與PSO收斂曲線

1）從表1可知，自適應慣性權重使得算法尋優能力得到很大程度的改善，相對誤差減小，

驗證了自適應慣性權重對于提高優化算法的穩定性是有效的。

表1 自適應慣性權重對平均相對誤差的影響

2）從表2可知，本文算法較其他算法的最優解更能接近已知下界值，反映出PSO粒子飛行模式的改進是有效的。從ARE指標來看，在Car及Rec問題上DMPSO求得的調度解均優于于其他算法，顯示出DMPSO在離散空間具有良好的進化機制。在同等規模問題上，ARE相差不大，表明DMPSO算法具有較強的魯棒性，在求解大規模問題上具有良好的穩定性，能夠適用于復雜的生產過程中。從運算速度上來看，DMPSO小于CQPSO，但大于PSO，由于DMPSO是在PSO基礎上改進了粒子飛行機制及加入了鄰域搜索算法，因此操作復雜度要大于PSO，但相比PSO得到的解，DMPSO能夠得到更好的解。

3）由圖2可見，DMPSO算法在第41次迭代就得到了最優解，而PSO算法在迭代結束也未能找到最優解，因此DMPSO算法不僅具有較快的收斂性，而且在搜索過程中具有良好的全局搜索能力，保證了求解精度。

5 結論

文中提出的求解置換流水線調度問題的一種改進粒子群算法，通過實驗證明了本文提出的改進算法的有效性。經Car和Rec基準問題測試表明本文提出的改進粒子群算法的相對誤差遠遠低于其他粒子群算法，驗證了本文算法在求解質量、求解穩定度上的優越性?；谠摳倪M算法的良好性能，下一步研究中，可經過適當改進，將算法運用于解決混合流水線調度問題。

[1]周馳，高亮，高海兵.基于PSO的置換流水車間調度算法[J].電子學報，2006，36(11):2008-2011.

[2]王凌，劉波.微粒群優化與調度算法[M].北京:清華大學出版社，2011.

[3]Garey M R，Johnson D S，Sethy R.The complexity of flowshop and job-shop scheduling[J].Mathematics of Operations Research，1976，1（2）:117-129.

[4]鄭曉龍，王凌，王圣堯.求解置換流水線調度問題的混合離散果蠅算法[J].控制理論與應用，2014，31（2）:159-164.

[5]于承敏，鄭麗萍.PSO算法求解PFSP問題研究進展[J].哈爾濱理工大學學報，2012，17（6）:14-20.

[6]李小繽，白焰，耿林霄.求解置換流水車間調度問題的改進遺傳算法[J].計算機應用，2013，33（12）:3576-3579.

[7]楊子江，顧幸生.基于混沌量子粒子群算法的置換流水車間調度[J].華東理工大學學報：自然科學版，2013，39（3）: 325-331.

[8]劉長平，葉春明.求解置換流水車間調度的布谷鳥算法[J].上海理工大學學報，2013，35（1）:17-20.

[9]Kennedy J，Eberhart R C.Particle swarm optimization[C].// Proceedings of International Con-ference on Neural Networks.Piscataway，N.J.USA:IEEE Press，1995:1942-1948.

[10]于承敏，鄭麗萍.PSO算法求解PFSP問題研究進展[J].哈爾濱理工大學學報，2012，17（6）:17-20.

[11]王凌.車間調度及其遺傳算法[M].北京:清華大學出版社，2003.

[12]李景洋，王勇，李春雷.采用雙模飛行的粒子群優化算法[J].模式識別與人工智能，2014，27（6）:533-539.

[13]潘全科，高亮，李新宇.流水車間調度及其優化算法[M].華中科技大學出版社，2013.

[14]Carlieb J.Ordonnancements à contraintes disjonetives[J].RAIRO-Operations Research-Recherche Opérationnelle.1978，12（4）:333-350.

[15]Reeves C R.A genetic algorithm for flow-shop sequencing[J].Computers and Operations Research 1995，22（1）:5-13.

Dual mode PSO for solving permutation flow shop scheduling problem

MA Yi-hang1，TAO Wen-hua1，LIU Yang2
（1.School of Information and Control Engineering，Liaoning Shihua University，Fushun 113000，China；2.Olefins plant of China Petroleum Fushun Petrochemical Company，Fushun 113009，China）

Our objective in this report is to study the permutation flow shop scheduling problem，this paper proposes a dualmode particle swarm optimization algorithm based on random key code.Based on the ROV rules for random code for the processing sequence；Secondly，particles in the search process use dual flight mode with the adaptive inertia weight to update the position and velocity，avoid particle swarm into premature convergence；In order to improve the quality of the solution，in each iteration the neighborhood local search algorithm is used on PSO optimized solution.Finally a comparison through numerical simulation and comparison of different PSO algorithm on the standard test set，to verify the feasibility and effectiveness of the proposed algorithm to solve the problem.

permutation flow-shop scheduling；particle swarm optimization；neighborhood search；random key

表2 仿真測試結果及比較

TN081

A

1674－6236（2016）15-0001-04

2016-01-08 稿件編號：201601048

國家自然科學基金面上基金項目（61473140）；國家自然科學基金青年基金項目（61203021）

馬祎航（1987—），男，遼寧沈陽人，碩士研究生。研究方向：生產調度與智能優化。