改進粒子群算法求解置換流水車間調(diào)度問題

張源 王加冕

摘 ?要： 針對置換流水車間調(diào)度問題，本文以最小化最大完工時間為優(yōu)化目標建立仿真模型，并設(shè)計一種改進粒子群算法（IPOS）進行求解。為克服標準粒子群算法尋優(yōu)結(jié)果穩(wěn)定性差的缺點，首先，該算法結(jié)合NEH算法生成初始種群;其次，在迭代進化中引入自適應權(quán)重系數(shù)和學習因子;最后，在粒子的個體極值搜索中引入模擬退火算法的Metropolis準則。將改進前后的粒子群算法分別進行仿真優(yōu)化實驗，實驗結(jié)果驗證了該算法的優(yōu)越性和有效性。

關(guān)鍵詞： 置換流水車間;粒子群算法;NEH算法;Metropolis準則;最小化完工時間

中圖分類號： TP391.9 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.06.023

本文著錄格式：張源，王加冕. 改進粒子群算法求解置換流水車間調(diào)度問題[J]. 軟件，2020，41（06）108111+131

【Abstract】： Aiming to the permutation flow shop scheduling problem， a simulation model was established with the goal of minimizing the maximum completion time， and an improved particle swarm optimization （IPOS） algorithm was designed to solve the problem. In order to overcome the poor stability of the optimization results of the standard particle swarm optimization algorithm， firstly， the algorithm combines with NEH algorithm to generate the initial population. Secondly， adaptive weight coefficient and learning factor are introduced into iterative evolution. Finally， the Metropolis criterion of simulated annealing algorithm is introduced into the individual extremum search of particles. The particle swarm optimization （pso） algorithm is simulated and optimized before and after the improvement. The experimental results verify the superiority and effectiveness of the algorithm.

【Key words】： Permutation flow shop; Particle swarm optimization algorithm; NEH algorithm; Metropolis criterion; Makespan

0 ?引言

車間生產(chǎn)調(diào)度問題[1]是指在一定的時間內(nèi)將生產(chǎn)資源與生產(chǎn)任務及設(shè)備進行合理的分配，其目的是對某些特定的性能指標進行優(yōu)化。置換流水車間調(diào)度問題[2]（permutation flow shop scheduling problem，PFSP）是實際生產(chǎn)調(diào)度問題的簡化形式，并且已被證明是一類經(jīng)典的NP難題[3]。所以對置換流水車間調(diào)度問題的研究有利于企業(yè)提高其生產(chǎn)效率和核心競爭力，具有重要的應用價值和意義。

目前針對置換流水車間調(diào)度問題的求解算法主要包括遍歷式算法[4]、構(gòu)造型算法[5]、智能優(yōu)化算 ?法[6]。其中智能優(yōu)化算法由于其原理簡單的特點，在求解置換流水車間調(diào)度問題的研究中得到了普及。粒子群算法（particle swarm optimization，POS）是由Kennedy和Eberhart在1995年共同提出的一種元啟發(fā)式智能優(yōu)化算法[7]。最初主要用于模擬社會行為，作為鳥群或魚群中有機個體運動的表現(xiàn)形式，后經(jīng)改進使得該算法同樣適用于求解生產(chǎn)線調(diào)度問題，但是粒子群算法在流水車間調(diào)度問題的應用中仍存在收斂精度低、穩(wěn)定性差等缺點。

因此，針對上述問題，本文以置換流水車間調(diào)度問題為研究對象建立仿真模型，并提出一種改進粒子群算法（improved particle swarm optimization，IPOS） 對置換流水車間調(diào)度問題進行求解，優(yōu)化目標為最小化最大完工時間[8]（makespan）。最終通過仿真優(yōu)化實驗的結(jié)果對比分析，驗證了IPOS算法的有效性。

1 ?問題描述

置換流水車間調(diào)度問題可以描述為[9]：由M臺加工設(shè)備和I個待加工工件組成，并且待加工工件要在所有設(shè)備上進行加工。每臺設(shè)備的工件加工順序和工件在各設(shè)備上的加工順序都相同，置換流水車間存在的約束為[9]：相鄰設(shè)備間存在無限暫存緩沖區(qū);每臺設(shè)備在同一時間只能加工一個工件;各工件同一時刻只能在一臺設(shè)備上加工;工件在加工過程中不能中斷。已知各工件在所有設(shè)備上的加工時間。為方便描述問題，定義參數(shù)如表1所示。

2.6 ?改進粒子群算法步驟及流程圖

本文將NEH算法、自適應權(quán)重系數(shù)及學習因子、Metropolis準則引入到標準粒子群算法的各環(huán)節(jié)中進行改進，圖1為IPOS算法的總流程圖，基本步驟為：

步驟1：設(shè)置算法的初始化參數(shù)、粒子群規(guī)模及初始化速度、最大迭代終止次數(shù)Gmax;

步驟2：結(jié)合NEH算法生成指定規(guī)模數(shù)量的種群作為改進粒子群算法的最終初始種群;

步驟3：分別計算粒子群中個體的適應度值;

步驟4：基于Metropolis準則對粒子的個體極值進行替換，并根據(jù)粒子的適應度值對全局最優(yōu)解進行更新;

步驟5：基于改進自適應權(quán)重系數(shù)和學習因子對粒子的速度位置進行替換;

步驟6：是否滿足最大迭代終止次數(shù)，若滿足輸出最優(yōu)結(jié)果;若不滿足轉(zhuǎn)步驟3。

3 ?仿真實驗

選擇置換流水車間標準測試庫中的Car1作為仿真測試對象[16]，即11個加工工件5臺加工設(shè)備。仿真優(yōu)化模型在Plant Simulation軟件中建立，如圖3所示。

置換流水車間模型由控制參數(shù)、程序仿真和數(shù)據(jù)統(tǒng)計3個模塊組成，其中程序仿真模塊中用Simtalk語言編寫改進粒子群算法和模型調(diào)度分配的程序。數(shù)據(jù)統(tǒng)計模塊將粒子的個體極值和粒子群的全局最優(yōu)解等數(shù)據(jù)進行記錄。控制參數(shù)模塊為仿真運行過程中需要調(diào)用的參數(shù)，如當前粒子群進化代數(shù)、所有工件的完工時間。仿真模型在硬件為AMD A10-5750M APU 2.50 GHZ的計算機上運行。設(shè)置改進粒子群算法和標準粒子群算法滿足終止條件的最大迭代次數(shù)Gmax為300，每代種群的粒子數(shù)N為50，粒子最大速度為工件數(shù)和機器數(shù)乘積的0.1倍，標準粒子群算法[17]的w、c1、c2均取1。

4 ?結(jié)果分析

將改進前后的粒子群算法分別運行10次，10次運算中各算法的尋優(yōu)結(jié)果統(tǒng)計如表2所示。

如表2所示，標準粒子群算法在300次迭代搜索中求解的最優(yōu)值極差較大，穩(wěn)定性較差，且在10次尋優(yōu)中只有3次求解出全局最優(yōu)解7038;而本文提出的改進粒子群算法在10次尋優(yōu)中可以9次求出全局最優(yōu)解7038，且最優(yōu)解的極差僅為10，從而表明了在相同的迭代次數(shù)中，改進粒子群算法具有更優(yōu)的全局搜索能力和穩(wěn)定性。改進前后粒子群算法的迭代曲線如圖3所示。

在圖3所示的迭代進化曲線圖中可得，雖然兩種算法在300次迭代中都可以搜索到最優(yōu)解7038，但IPOS算法由于對種群的初始化、個體極值的替換以及權(quán)重系數(shù)和學習因子進行了改進，提高了算法初始種群的質(zhì)量，更接近全局最優(yōu)解，且收斂速度也更快，在迭代進行到49代就收斂到最小值，避免出現(xiàn)如POS算法在202代才收斂到最小值的情況。

5 ?結(jié)論

針對置換流水車間調(diào)度問題，本文提出一種改進粒子群算法進行求解。該算法將自適應權(quán)重系數(shù)和學習因子引入粒子速度位置的迭代更新中;將Metropolis準則引入粒子個體的極值替換中;將NEH啟發(fā)式算法引入種群的初始化中。并以最小化最大完工時間為目標對置換流水車間調(diào)度問題進行仿真實驗，通過實驗結(jié)果的對比分析，驗證了改進粒子群算法的有效性和優(yōu)越性。

參考文獻

[1] Julia L， Frank W. A Permutation-Based Heuristic Method for the Blocking Job Shop Scheduling Problem[J]. PapersOnLine， 2019， 52（13）： 1403-1408.

[2] 黃佳琳， 張丫丫， 顧幸生. 基于改進生物地理學優(yōu)化算法的分布式裝配置換流水車間調(diào)度問題[J/OL]. 華東理工大學學報（自然科學版）： 1-12[2020-01-15].

[3] Frank B， Roland B， Karl F. Doerner， Richard F. Hartl. A machine learning approach for flow shop scheduling prob-lems with alternative resources， sequence-dependent setup times， and blocking[J]. OR Spectrum， 2019， 41（4）： 871-893.

[4] 張春燕. 基于改進遺傳進化算法的復雜作業(yè)流程調(diào)度[J]. 軟件， 2017， 38（12）： 98-103.

[5] 楊蕾， 梁永全. 協(xié)同進化策略的粒子群優(yōu)化算法[J]. 軟件， 2019， 40（08）： 152-155.

[6] Beezao A C， Cordeau J F， Laporte G， et al. Scheduling identical parallel machines with tooling constraints. Euro-pean Journal of Operational Research， 2017， 257（3）： 834- 844.

[7] Mohd S S， Azuwir M N， Mohamad E B， et al. Optimization of surface roughness in FDM 3D printer using response surface methodology， particle swarm optimization， and symbiotic organism search algorithms[J]. The International Journal of Advanced Manufacturing Technology， 2019， 105（1）： 5121-5137.

[8] 鐘祾充， 錢斌， 胡蓉， 王凌. 混合布谷鳥算法求解綠色流水車間調(diào)度問題[J]. 中國機械工程， 2018， 29（22）： 2674- 2681.

[9] 劉長平， 葉春明. 置換流水車間調(diào)度問題的螢火蟲算法求解[J]. 工業(yè)工程與管理， 2012， 17（03）： 56-59+65.

[10] 王柏琳， 王海鳳， 李鐵克. 工件可拒絕的有限等待置換流水車間調(diào)度算法[J]. 控制與決策， 2019， 34（03）： 459-469.

[11] Eltamaly A M， Al-Saud Mamdooh S， Abokhalil Ahmed G， Farh Hassan MH. Photovoltaic maximum power point tracking under dynamic partial shading changes by novel adaptive particle swarm optimization strategy[J]. Transa-ctions of the Institute of Measurement and Control， 2020，42（1）： 104-115.

[12] 施文章， 韓偉， 戴睿聞. 模擬退火下布谷鳥算法求解車間作業(yè)調(diào)度問題[J]. 計算機工程與應用， 2017， 53（17）： 249-253+259.

[13] SHI Y， EBERHART R. A modified particle swarm opti?mi-zer[J]. Advances in Natural Computation， 1998， 12： 429-439.

[14] 趙遠東， 方正華. 帶有權(quán)重函數(shù)學習因子的粒子群算法[J]. 計算機應用， 2013， 33（08）： 2265-2268.

[15] 尚正陽， 顧寄南， 王建平. 求解帶能力約束車輛路徑優(yōu)化問題的改進模擬退火算法[J/OL]. 計算機集成制造系統(tǒng)： 1-16[2020-01-16].

[16] Carlier J. Ordonnancements à contraintes disjonctives[J]. RAIRO-Operations Research， 1978， 12（4）： 333-350.