張?jiān)? 王加冕

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

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

中圖分類號(hào)： TP391.9 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.06.023

本文著錄格式：張?jiān)?，王加? 改進(jìn)粒子群算法求解置換流水車間調(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]是指在一定的時(shí)間內(nèi)將生產(chǎn)資源與生產(chǎn)任務(wù)及設(shè)備進(jìn)行合理的分配，其目的是對(duì)某些特定的性能指標(biāo)進(jìn)行優(yōu)化。置換流水車間調(diào)度問題[2]（permutation flow shop scheduling problem，PFSP）是實(shí)際生產(chǎn)調(diào)度問題的簡化形式，并且已被證明是一類經(jīng)典的NP難題[3]。所以對(duì)置換流水車間調(diào)度問題的研究有利于企業(yè)提高其生產(chǎn)效率和核心競爭力，具有重要的應(yīng)用價(jià)值和意義。

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

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

1 ?問題描述

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

2.6 ?改進(jìn)粒子群算法步驟及流程圖

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

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

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

步驟3：分別計(jì)算粒子群中個(gè)體的適應(yīng)度值;

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

步驟5：基于改進(jìn)自適應(yīng)權(quán)重系數(shù)和學(xué)習(xí)因子對(duì)粒子的速度位置進(jìn)行替換;

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

3 ?仿真實(shí)驗(yàn)

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

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

4 ?結(jié)果分析

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

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

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

5 ?結(jié)論

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

參考文獻(xiàn)

[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ìn)生物地理學(xué)優(yōu)化算法的分布式裝配置換流水車間調(diào)度問題[J/OL]. 華東理工大學(xué)學(xué)報(bào)（自然科學(xué)版）： 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ìn)遺傳進(jìn)化算法的復(fù)雜作業(yè)流程調(diào)度[J]. 軟件， 2017， 38（12）： 98-103.

[5] 楊蕾， 梁永全. 協(xié)同進(jìn)化策略的粒子群優(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]. 中國機(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]. 計(jì)算機(jī)工程與應(yīng)用， 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] 趙遠(yuǎn)東， 方正華. 帶有權(quán)重函數(shù)學(xué)習(xí)因子的粒子群算法[J]. 計(jì)算機(jī)應(yīng)用， 2013， 33（08）： 2265-2268.

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

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