改進(jìn)的混合粒子群算法求解作業(yè)車(chē)間調(diào)度問(wèn)題

衛(wèi)堯

摘要：為解決作業(yè)車(chē)間調(diào)度問(wèn)題，在標(biāo)準(zhǔn)粒子群算法中加入隨機(jī)慣性權(quán)重策略，使其具有靈活調(diào)節(jié)全局搜索和局部搜索的能力，同時(shí)在進(jìn)化過(guò)程中引入遺傳算法中的交叉、變異操作來(lái)增強(qiáng)種群的多樣性，另外在粒子群算法進(jìn)化停滯時(shí)加入模擬退火算法，利用模擬退火算法可以及時(shí)跳出局部最優(yōu)的能力，保證得到全局最優(yōu)解。最后通過(guò)使用作業(yè)車(chē)間調(diào)度問(wèn)題的經(jīng)典算例進(jìn)行實(shí)驗(yàn)仿真測(cè)試，實(shí)驗(yàn)結(jié)果證明了新算法可以有效地解決作業(yè)車(chē)間調(diào)度問(wèn)題。

關(guān)鍵詞：粒子群算法；隨機(jī)慣性權(quán)重；模擬退火算法；作業(yè)車(chē)間調(diào)度

中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）12-0200-03

1引言

作業(yè)車(chē)間調(diào)度問(wèn)題（Job-shop Scheduling Problem，JSP）是實(shí)際生產(chǎn)車(chē)間調(diào)度過(guò)程中的一種簡(jiǎn)化問(wèn)題，屬于最困難的組合優(yōu)化問(wèn)題之一，生產(chǎn)調(diào)度[1]對(duì)于制造業(yè)企業(yè)來(lái)說(shuō)是非常重要的一步，可以說(shuō)調(diào)度方法的好壞以及結(jié)果的優(yōu)劣直接影響著企業(yè)的生存和發(fā)展，所以對(duì)于尋找車(chē)間調(diào)度問(wèn)題的最優(yōu)解，國(guó)內(nèi)外學(xué)者們一直在不斷地探索。目前解決JSP問(wèn)題比較常用的方法有遺傳算法[2]、禁忌搜索算法[3]、粒子群算法等智能優(yōu)化算法。這些智能優(yōu)化算法[4]不僅可以彌補(bǔ)傳統(tǒng)算法的不足，同時(shí)也為解決JSP問(wèn)題提供了新的思路。黃霞等[5]針對(duì)JSP提出了使用入侵式雜草優(yōu)化算法來(lái)進(jìn)行求解并取得了不錯(cuò)的效果。周鑫等[6]提出一種結(jié)合遺傳算法和模擬退火算法優(yōu)點(diǎn)的混合算法用來(lái)解決JSP問(wèn)題。張梅等[7]將改進(jìn)的教學(xué)算法用于解決JSP問(wèn)題。張文鵬等[8]結(jié)合變領(lǐng)域搜索策略改進(jìn)蝙蝠算法，并通過(guò)JSP問(wèn)題的經(jīng)典算例進(jìn)行試驗(yàn)仿真證明了算法的有效性。

粒子群算法（Particle Swarm Optimization，PSO）是一種通過(guò)模擬鳥(niǎo)類(lèi)聚集飛行，在運(yùn)動(dòng)中不斷改變自身的位置和速度，最終達(dá)到最優(yōu)狀態(tài)的進(jìn)化搜索計(jì)算方法。粒子群算法[9]通用性強(qiáng)、容易實(shí)現(xiàn)還有收斂速度快的優(yōu)點(diǎn)使其成為近年來(lái)求解車(chē)間調(diào)度問(wèn)題的熱點(diǎn)，仲于江等[10]將小生境技術(shù)應(yīng)用于粒子群算法中用來(lái)解決FJSP問(wèn)題；Shi等[11]對(duì)粒子群算法速度更新公式進(jìn)行了改進(jìn)，加入了慣性權(quán)重因子，使其隨著進(jìn)化代數(shù)線(xiàn)性遞減，從而提高了算法的性能；譚躍等[12]提出將遺傳算法中交叉操作和多混沌策略加入PSO中來(lái)提高PSO算法的搜索能力。潘全科等[13]將變鄰域搜索與PSO算法混合成一種調(diào)度算法，顧文斌等[14]將生物體的自我調(diào)節(jié)機(jī)制引入到PSO算法中也取得很好的效果，張飛等[15]將混沌機(jī)制加入粒子群算法中來(lái)解決JSP問(wèn)題。

本文通過(guò)分析PSO算法的優(yōu)化過(guò)程，根據(jù)它存在的一些缺陷和不足，提出了一種改進(jìn)的混合粒子群算法（Improved Hybrid Particle Swarm Optimization，IHPSO）。在粒子群算法基礎(chǔ)上加入隨機(jī)慣性權(quán)重策略，同時(shí)PSO算法進(jìn)化前期引入遺傳算法（Genetic Algorithm，GA）中交叉和變異操作來(lái)增強(qiáng)種群多樣性，并在進(jìn)化后期為避免種群陷入局部最優(yōu)解，加入了擁有強(qiáng)大局部搜索能力的模擬退火算法，來(lái)保證種群可以取得最終的全局最優(yōu)解。

2 作業(yè)車(chē)間調(diào)度問(wèn)題的描述

2.1問(wèn)題描述

作業(yè)車(chē)間調(diào)度問(wèn)題描述如下：有n個(gè)工件在m 臺(tái)機(jī)器上進(jìn)行加工，每個(gè)工件包含 m 道工序，其中工件的各道工序所需要的機(jī)器和加工時(shí)間都是已知的，另外加工過(guò)程中還要滿(mǎn)足以下幾個(gè)約束條件：

（1）不同工件的工序沒(méi)有加工順序要求，但是同一工件的工序必須按照預(yù)先規(guī)定好的加工順序進(jìn)行加工；

（2）一道工序開(kāi)始在機(jī)器上進(jìn)行加工，中途就不能被打斷，直到此道工序加工完成；

（3）一個(gè)工件在同一臺(tái)機(jī)器上只進(jìn)行一次加工；

（4）同一時(shí)間一臺(tái)機(jī)器上只能加工一個(gè)工件；

（5）所有待加工工件沒(méi)有優(yōu)先級(jí)之分，都有可能在初始時(shí)間開(kāi)始加工。

本文性能指標(biāo)即適應(yīng)度函數(shù)定為總工期最短，也就是最小化最大完工時(shí)間。

2.2建立數(shù)學(xué)模型

解決作業(yè)車(chē)間調(diào)度問(wèn)題的實(shí)質(zhì)就是在滿(mǎn)足上述約束條件的情況下，得到一個(gè)可行的加工工序并且使所要求的目標(biāo)函數(shù)達(dá)到最優(yōu)。實(shí)現(xiàn)最大完工時(shí)間最小化是這一類(lèi)車(chē)間調(diào)度問(wèn)題中比較常見(jiàn)的目標(biāo)函數(shù)。這有助于提高生產(chǎn)車(chē)間的工作效率，降低企業(yè)的生產(chǎn)成本，因此將這一指標(biāo)作為目標(biāo)函數(shù)進(jìn)行改進(jìn)具有一定的現(xiàn)實(shí)意義。

本文選取的作業(yè)車(chē)間調(diào)度問(wèn)題的目標(biāo)函數(shù)是最小化最大完工時(shí)間，即

3 算法描述

3.1編碼與解碼

在JSP中如果有n個(gè)工件，每個(gè)工件有m道工序時(shí)，則JSP的一個(gè)可行解就可以表示成一個(gè)長(zhǎng)度為n×m的整數(shù)串。本文采用一種將粒子的實(shí)數(shù)位置通過(guò)計(jì)算轉(zhuǎn)化成一個(gè)工序加工序列的編碼方式，這種編碼方式可以將主要用于求解連續(xù)型問(wèn)題的PSO算法應(yīng)用到離散型的JSP問(wèn)題中，而且實(shí)際操作簡(jiǎn)單、便于理解、容易實(shí)現(xiàn)。下面以3個(gè)工件和3臺(tái)機(jī)器的JSP問(wèn)題為例來(lái)對(duì)粒子的編碼和解碼過(guò)程進(jìn)行說(shuō)明。

首先在取值范圍內(nèi)隨機(jī)生成一組3×3的數(shù)組，例如數(shù)組A=[0.1，0.3，0.6，1.5，0.2，1，0.8，0.5，2.1]，然后對(duì)數(shù)組A中的數(shù)字按照大小進(jìn)行排列，同時(shí)將排列結(jié)果按照原數(shù)組各個(gè)數(shù)字的順序?qū)懭胍粋€(gè)新的數(shù)組B中，得到結(jié)果為B=[1，3，5，8，2，7，6，4，9]，將B數(shù)組中的每一個(gè)數(shù)字都除以工序數(shù)m，并向上取整后可到一組新的數(shù)組C=[1，1，2，3，1，3，2，2，3]。很顯然得到這個(gè)數(shù)組C就是JSP問(wèn)題的一個(gè)可行解，其中第一個(gè)1表示工件1的第一個(gè)工序，第二個(gè)1表示工件1的第二個(gè)工序，依次類(lèi)推，最后一個(gè)位置的3表示工件3的第三個(gè)工序，這樣每一個(gè)隨機(jī)產(chǎn)生的數(shù)組就能轉(zhuǎn)化成工件的一個(gè)加工順序，用于進(jìn)行問(wèn)題的求解。

3.2粒子群算法

在PSO算法中，為了使粒子的全局搜索能力和局部搜索能力保持一定的均衡，加入一種隨機(jī)慣性權(quán)重策略，粒子速度和位置的更新公式如下：

3.3模擬退火算法

模擬退火算法（Simulated annealing，SA）可以利用概率突跳特性讓所求問(wèn)題的可行解在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解。

模擬退火算法的步驟如下：

（1）初始化各項(xiàng)控制參數(shù)。

（2）根據(jù)初始解，找到新解，計(jì)算兩個(gè)解對(duì)應(yīng)適應(yīng)值的變化量[df=fx1-fx2]，若[df<0]，則接受[x2]為新的當(dāng)前解，令[x1=x2]，否則計(jì)算新解[x2]的接受概率[exp-df/T]，其中T為當(dāng)前溫度，若[exp-df/T>rand]（rand（）表示產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)），也接受[x2]作為新的當(dāng)前解，令[x1=x2]，否則保留當(dāng)前解[x1]。

（3）利用降溫速率a對(duì)當(dāng)前溫度T進(jìn)行降溫迭代，降溫公式為[Ti=a×Ti-1]。

（4）判斷當(dāng)前進(jìn)化溫度是否小于設(shè)置結(jié)束溫度，若是，則結(jié)束算法搜索過(guò)程，輸出最優(yōu)解，否則重復(fù)步驟（2）和（3）。

3.4改進(jìn)的混合粒子群算法（IHPSO）

IHPSO算法的具體步驟如下：

步驟1.設(shè)置混合算法中的各項(xiàng)參數(shù)，如粒子種群規(guī)模M、最大進(jìn)化代數(shù)Tmax、當(dāng)前進(jìn)化代數(shù)t以及模擬退火算法中的相關(guān)參數(shù)。

步驟2.初始化粒子種群，使用本文提出的編碼方式進(jìn)行編碼和解碼操作，然后計(jì)算各個(gè)粒子的適應(yīng)度值。

步驟3.找出粒子的pbest以及整個(gè)粒子種群的gbest。

步驟4.利用公式（4）、（5）更新粒子的速度和位置，同時(shí)在粒子種群中按照一定概率隨機(jī)選出兩個(gè)粒子進(jìn)行兩點(diǎn)交叉和兩點(diǎn)互換變異操作。

步驟5.在進(jìn)化過(guò)程中判斷種群是否陷入局部最優(yōu)，若種群進(jìn)化陷入停滯階段，判斷種群的進(jìn)化停滯代數(shù)是否大于初始設(shè)定值N，若是轉(zhuǎn)步驟6，否則轉(zhuǎn)入步驟7。

步驟6.使用SA算法對(duì)當(dāng)前種群進(jìn)行優(yōu)化搜索，如果可以得到更優(yōu)結(jié)果則更新粒子的pbest和gbest。

步驟7.判斷是否達(dá)到種群最大進(jìn)化代數(shù)或者得到全局最優(yōu)解，若是則輸出粒子最優(yōu)解對(duì)應(yīng)的加工工序，加工結(jié)束，否則轉(zhuǎn)步驟3。

4 仿真實(shí)驗(yàn)與分析

為了檢驗(yàn)IHPSO算法對(duì)求解JSP問(wèn)題是否有效，本文采用JSP中的經(jīng)典算例FT06、FT10作為仿真實(shí)例進(jìn)行實(shí)驗(yàn)測(cè)試。同時(shí)用IHPSO算法、PSO算法以及GA這三種算法對(duì)實(shí)驗(yàn)算例進(jìn)行求解，并將結(jié)果進(jìn)行對(duì)比分析。

在對(duì)算例進(jìn)行仿真實(shí)驗(yàn)測(cè)試的過(guò)程中，針對(duì)不同的算例設(shè)置不同的參數(shù)，例如在測(cè)試FT06算例時(shí)，種群規(guī)模設(shè)置為100，最大進(jìn)化代數(shù)設(shè)置為200，學(xué)習(xí)因子c1和c2都設(shè)為2，因?yàn)樵搶?shí)驗(yàn)算例規(guī)模較小，計(jì)算復(fù)雜度低，所以停滯代數(shù)N設(shè)置為3，但是如果在計(jì)算FT10算例時(shí)，由于該實(shí)驗(yàn)算例規(guī)模較大，計(jì)算復(fù)雜度較高，所以停滯代數(shù)N相應(yīng)增大設(shè)置為5，各個(gè)算法分別進(jìn)行10次獨(dú)立仿真運(yùn)算，最后統(tǒng)計(jì)各算法的實(shí)驗(yàn)結(jié)果。

使用IHPSO算法求解FT06算例取得最優(yōu)解55的甘特圖如圖1所示。

改進(jìn)的混合粒子群算法、標(biāo)準(zhǔn)粒子群算法以及遺傳算法求解FT06算例、FT10算例的收斂速度對(duì)比圖如下圖2、3所示。

觀察圖2和圖3可以發(fā)現(xiàn)IHPSO算法很快地求出FT06算例的最優(yōu)解55以及FT10算例的最優(yōu)解930，而其他兩個(gè)算法，只有GA算法找到了FT06問(wèn)題的最優(yōu)解55，剩下的則沒(méi)有找到最優(yōu)解。而且通過(guò)對(duì)比圖2和圖3中的收斂速度，可以很明顯地看出IHPSO算法的收斂速度遠(yuǎn)遠(yuǎn)快于PSO算法和GA的收斂速度，并且IHPSO算法可以很快就得到最優(yōu)解，而其他兩個(gè)算法有時(shí)會(huì)得不到最優(yōu)解，這是因?yàn)镻SO在進(jìn)化初期易陷入局部最優(yōu)值導(dǎo)致取不到最優(yōu)解，而IHPSO算法因?yàn)樵赑SO算法后期引入了SA，所以在粒子種群進(jìn)化后期陷入局部最優(yōu)時(shí)可以很快地跳出，并順利找到全局最優(yōu)解。另外比較兩張收斂速度對(duì)比圖還可以發(fā)現(xiàn)，相對(duì)于GA和PSO算法，IHPSO算法可以更快找到最優(yōu)解的這個(gè)優(yōu)勢(shì)在求解大規(guī)模的JSP問(wèn)題時(shí)會(huì)更加明顯。

5 結(jié)論

本文在求解JSP問(wèn)題時(shí)針對(duì)PSO算法存在的后期收斂速度慢、容易陷入局部最優(yōu)解的問(wèn)題，首先在PSO算法中加入隨機(jī)慣性權(quán)重，同時(shí)引入GA中的交叉和變異操作，最后在種群進(jìn)化后期結(jié)合SA算法，來(lái)提高混合算法的全局尋優(yōu)能力，最后通過(guò)對(duì)JSP問(wèn)題的經(jīng)典算例進(jìn)行仿真實(shí)驗(yàn)，并將仿真實(shí)驗(yàn)結(jié)果和GA、PSO算法的仿真實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析，證明了改進(jìn)的混合粒子群算法的有效性和可行性。

參考文獻(xiàn)：

[1] Rodammer F A and White KP.A recent survey of production scheduling[J]. IEEE Trans. SMC， 1988， 18（6）： 841-851

[2] CORCE F D，TADEI R，VOLTA G.A genetic algorithm for the Job Shop problem[J].Computers and Operations Research，1995，22（1）：15-24.

[3] NOWICKI E，SMUTNICKI C.A fast taboo search algorithm for the Job Shop scheduling[J].Management Science，1996，42（6）：797-813.

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

[5] 黃霞，葉春明，包曉曉.作業(yè)車(chē)間調(diào)度問(wèn)題的雜草優(yōu)化算法求解[J].計(jì)算機(jī)應(yīng)用與軟件，2016（06）：231-234.

[6] 周鑫，馬躍，胡毅.求解車(chē)間作業(yè)調(diào)度問(wèn)題的混合遺傳模擬退火算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2015（02）：370-374.

[7] 張梅，吳凱華，胡躍明.基于改進(jìn)教學(xué)算法的車(chē)間作業(yè)調(diào)度問(wèn)題[J].控制與決策，2017（02）：349-09.

[8] 張文鵬，王興.改進(jìn)型蝙蝠算法在作業(yè)車(chē)間調(diào)度問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2017（53）：137-140.

[9] Ratnaweera A， HalgamugeS K， Watson H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration [J]. IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 240-255.

[10] 仲于江，楊海成，莫蓉，等.基于小生境粒子群算法的柔性作業(yè)車(chē)間調(diào)度優(yōu)化方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2015（12）：3231-3238.

[11] Shi Y， Eberhart R C. A modified particle swarm optimizer[A]. Proc. of the IEEE International Conference on Evolutionary Computation. [C]. Anchorage， AK， 1998： 69-73.

[12] 譚躍，譚冠政，鄧曙光.基于遺傳交叉和多混沌策略改進(jìn)的粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用研究，2016（12）：3643-3647.

[13] 潘全科，王文宏，朱劍英，等.基于粒子群優(yōu)化和變鄰域搜索的混合調(diào)度算法[J].計(jì)算機(jī)集成制造系統(tǒng).2007（02）：323-326.

[14] 顧文斌，張薇薇，苑明海.基于改進(jìn)型粒子群的作業(yè)車(chē)間調(diào)度問(wèn)題研究[J].機(jī)械設(shè)計(jì)與制造工程.2017（01）：11-15.

[15] 張飛，耿紅琴.基于混沌粒子群算法的車(chē)間作業(yè)調(diào)度優(yōu)化[J].山東大學(xué)學(xué)報(bào)（工學(xué)版），2013（03）：19-22+37