基于雙模式PSO算法求解置換流水車(chē)間調(diào)度問(wèn)題

馬祎航，陶文華，劉 陽(yáng)

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

基于雙模式PSO算法求解置換流水車(chē)間調(diào)度問(wèn)題

馬祎航1，陶文華1，劉 陽(yáng)2

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

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

置換流水車(chē)間調(diào)度；粒子群算法；鄰域搜索；隨機(jī)鍵

置換流水車(chē)間調(diào)度問(wèn)題（Permutation Flow Shop Scheduling Problem，PFSP）是制造系統(tǒng)中重要的規(guī)劃問(wèn)題[1]，是在流水車(chē)間調(diào)度問(wèn)題的基礎(chǔ)上，增加了每臺(tái)機(jī)器加工各工件順序相同的這一特定的約束條件[2]，已證明3臺(tái)即為NP-hard問(wèn)題[3]。許多實(shí)際生產(chǎn)過(guò)程都可以簡(jiǎn)化成這類問(wèn)題，而PFSP的優(yōu)化研究能夠?yàn)槠髽I(yè)帶來(lái)更大的生產(chǎn)效益，因此研究PFSP具有重要的理論和實(shí)際意義。

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

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

1 問(wèn)題描述

置換流水車(chē)間調(diào)度問(wèn)題是n個(gè)工件在m臺(tái)機(jī)器上的流水加工過(guò)程，屬于流水車(chē)間調(diào)度的一類問(wèn)題，其具有以下特征：

1）每個(gè)工件在各機(jī)器上加工順序相同；

2）每臺(tái)機(jī)器上所有工件的加工順序相同；

3）每個(gè)工件在每臺(tái)機(jī)器上只加工一次；

4）每臺(tái)機(jī)器在任意時(shí)刻只能加工一個(gè)工件。

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

2 雙模式粒子群算法

2.1 隨機(jī)鍵編碼

本文對(duì)粒子的位置矢量采用基于升序排列規(guī)則（Ranked—Order—Value，ROV）的隨機(jī)鍵編碼實(shí)現(xiàn)粒子連續(xù)位置到離散值的轉(zhuǎn)換，無(wú)需修改PSO算法的進(jìn)化操作，而且能夠保證調(diào)度方案的可行性。

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

假設(shè)優(yōu)化得到第k個(gè)粒子的位置為：

經(jīng)ROV規(guī)則得到一個(gè)序列Lk：

按照該序列對(duì)工件加工重新排序得：

2.2 自適應(yīng)慣性權(quán)重

為了提高算法的收斂穩(wěn)定性及收斂速度，文中采用一種自適應(yīng)慣性權(quán)重的方法。迭代次數(shù)與慣性權(quán)重 成反比是比較廣泛應(yīng)用的PSO算法慣性權(quán)重控制方案：

式中，ω為粒子i在第t次迭代中的取值；Iter為預(yù)先設(shè)定的最大迭代次數(shù)；t為當(dāng)前迭代數(shù)；ωmax為慣性權(quán)重最大值，典型取值為0.9；ωmin為慣性權(quán)重最小值，典型取值為0.4。

通過(guò)全體粒子上一輪迭代結(jié)束后適應(yīng)值的變化來(lái)選擇慣性權(quán)重的取值：

式中，表示粒子i在第i次迭代后的適應(yīng)值；表示粒子i在第i次迭代后的適應(yīng)值變化。然后確定各粒子在當(dāng)前迭代中慣性權(quán)重的最終取值：

當(dāng)t?[1，2]時(shí)，慣性權(quán)重按式（6）取值；當(dāng)t?[3，Iter]時(shí)，慣性權(quán)重按式（7）、式（8）取值。

2.3 粒子飛行模式

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

所有粒子經(jīng)過(guò)的最優(yōu)位置：

分析粒子當(dāng)前位置的優(yōu)劣情況：把群體按適應(yīng)度的大小排序，設(shè)粒子群體規(guī)模是M，記i粒子t時(shí)刻的序號(hào)為s（t），此時(shí)，s（t）=1表示i粒子t時(shí)刻的位置在群體中最優(yōu)。若s（t）=M則表示i粒子t時(shí)刻的位置在群體中最差。粒子依據(jù)當(dāng)前位置優(yōu)劣情況按式（11）（12）確定飛行模式。

粒子不變軌飛行模式：

粒子變軌飛行模式：

決策因子：

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

2.4 鄰域局部搜索

在PSO每次迭代優(yōu)化得到加工順序之后，通過(guò)局部搜索進(jìn)一步尋找工件加工最佳順序。文中采用鄰域局部搜索方法來(lái)確定機(jī)器加工序列[13]。步驟如下：1）DMPSO優(yōu)化后得到所有工件的一個(gè)排序β；2）令k=1，取出β中的前2個(gè)工件，對(duì)兩個(gè)工件先后加工次序進(jìn)行評(píng)價(jià)，選擇調(diào)度解小的序列作為當(dāng)前序列；3）令k=k+1，依次將第k個(gè)工件插入到當(dāng)前序列的k個(gè)可能的位置，從中選擇調(diào)度解小的序列作為當(dāng)前序列；4）重復(fù)步驟3），直到β中所有工件均得到新的排序操作。

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

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

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

4 仿真測(cè)試與比較

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

圖2 求解Car8問(wèn)題的DMPSO與PSO收斂曲線

1）從表1可知，自適應(yīng)慣性權(quán)重使得算法尋優(yōu)能力得到很大程度的改善，相對(duì)誤差減小，

驗(yàn)證了自適應(yīng)慣性權(quán)重對(duì)于提高優(yōu)化算法的穩(wěn)定性是有效的。

表1 自適應(yīng)慣性權(quán)重對(duì)平均相對(duì)誤差的影響

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

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

5 結(jié)論

文中提出的求解置換流水線調(diào)度問(wèn)題的一種改進(jìn)粒子群算法，通過(guò)實(shí)驗(yàn)證明了本文提出的改進(jìn)算法的有效性。經(jīng)Car和Rec基準(zhǔn)問(wèn)題測(cè)試表明本文提出的改進(jìn)粒子群算法的相對(duì)誤差遠(yuǎn)遠(yuǎn)低于其他粒子群算法，驗(yàn)證了本文算法在求解質(zhì)量、求解穩(wěn)定度上的優(yōu)越性。基于該改進(jìn)算法的良好性能，下一步研究中，可經(jīng)過(guò)適當(dāng)改進(jìn)，將算法運(yùn)用于解決混合流水線調(diào)度問(wèn)題。

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

[2]王凌，劉波.微粒群優(yōu)化與調(diào)度算法[M].北京:清華大學(xué)出版社，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]鄭曉龍，王凌，王圣堯.求解置換流水線調(diào)度問(wèn)題的混合離散果蠅算法[J].控制理論與應(yīng)用，2014，31（2）:159-164.

[5]于承敏，鄭麗萍.PSO算法求解PFSP問(wèn)題研究進(jìn)展[J].哈爾濱理工大學(xué)學(xué)報(bào)，2012，17（6）:14-20.

[6]李小繽，白焰，耿林霄.求解置換流水車(chē)間調(diào)度問(wèn)題的改進(jìn)遺傳算法[J].計(jì)算機(jī)應(yīng)用，2013，33（12）:3576-3579.

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

[8]劉長(zhǎng)平，葉春明.求解置換流水車(chē)間調(diào)度的布谷鳥(niǎo)算法[J].上海理工大學(xué)學(xué)報(bào)，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問(wèn)題研究進(jìn)展[J].哈爾濱理工大學(xué)學(xué)報(bào)，2012，17（6）:17-20.

[11]王凌.車(chē)間調(diào)度及其遺傳算法[M].北京:清華大學(xué)出版社，2003.

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

[13]潘全科，高亮，李新宇.流水車(chē)間調(diào)度及其優(yōu)化算法[M].華中科技大學(xué)出版社，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，F(xiàn)ushun 113000，China；2.Olefins plant of China Petroleum Fushun Petrochemical Company，F(xiàn)ushun 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 仿真測(cè)試結(jié)果及比較

TN081

A

1674－6236（2016）15-0001-04

2016-01-08 稿件編號(hào)：201601048

國(guó)家自然科學(xué)基金面上基金項(xiàng)目（61473140）；國(guó)家自然科學(xué)基金青年基金項(xiàng)目（61203021）

馬祎航（1987—），男，遼寧沈陽(yáng)人，碩士研究生。研究方向：生產(chǎn)調(diào)度與智能優(yōu)化。