改進粒子群算法求解置換流水車間調度問題

張源 王加冕

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

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

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

本文著錄格式：張源，王加冕. 改進粒子群算法求解置換流水車間調度問題[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 ?引言

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

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

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

1 ?問題描述

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

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

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

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

步驟2：結合NEH算法生成指定規模數量的種群作為改進粒子群算法的最終初始種群;

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

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

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

步驟6：是否滿足最大迭代終止次數，若滿足輸出最優結果;若不滿足轉步驟3。

3 ?仿真實驗

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

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

4 ?結果分析

將改進前后的粒子群算法分別運行10次，10次運算中各算法的尋優結果統計如表2所示。

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

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

5 ?結論

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

參考文獻

[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] 黃佳琳， 張丫丫， 顧幸生. 基于改進生物地理學優化算法的分布式裝配置換流水車間調度問題[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] 張春燕. 基于改進遺傳進化算法的復雜作業流程調度[J]. 軟件， 2017， 38（12）： 98-103.

[5] 楊蕾， 梁永全. 協同進化策略的粒子群優化算法[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] 鐘祾充， 錢斌， 胡蓉， 王凌. 混合布谷鳥算法求解綠色流水車間調度問題[J]. 中國機械工程， 2018， 29（22）： 2674- 2681.

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

[10] 王柏琳， 王海鳳， 李鐵克. 工件可拒絕的有限等待置換流水車間調度算法[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] 施文章， 韓偉， 戴睿聞. 模擬退火下布谷鳥算法求解車間作業調度問題[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] 趙遠東， 方正華. 帶有權重函數學習因子的粒子群算法[J]. 計算機應用， 2013， 33（08）： 2265-2268.

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

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