衛(wèi)堯

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

關鍵詞：粒子群算法；隨機慣性權重；模擬退火算法；作業(yè)車間調(diào)度

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2018）12-0200-03

1引言

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

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

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

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

2.1問題描述

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

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

（2）一道工序開始在機器上進行加工，中途就不能被打斷，直到此道工序加工完成；

（3）一個工件在同一臺機器上只進行一次加工；

（4）同一時間一臺機器上只能加工一個工件；

（5）所有待加工工件沒有優(yōu)先級之分，都有可能在初始時間開始加工。

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

2.2建立數(shù)學模型

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

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

3 算法描述

3.1編碼與解碼

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

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

3.2粒子群算法

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

3.3模擬退火算法

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

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

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

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

（3）利用降溫速率a對當前溫度T進行降溫迭代，降溫公式為[Ti=a×Ti-1]。

（4）判斷當前進化溫度是否小于設置結束溫度，若是，則結束算法搜索過程，輸出最優(yōu)解，否則重復步驟（2）和（3）。

3.4改進的混合粒子群算法（IHPSO）

IHPSO算法的具體步驟如下：

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

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

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

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

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

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

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

4 仿真實驗與分析

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

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

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

改進的混合粒子群算法、標準粒子群算法以及遺傳算法求解FT06算例、FT10算例的收斂速度對比圖如下圖2、3所示。

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

5 結論

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

參考文獻：

[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] 王凌.車間調(diào)度及其遺傳算法[M]. 北京：清華大學出版社， 2003.

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

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

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

[8] 張文鵬，王興.改進型蝙蝠算法在作業(yè)車間調(diào)度問題中的應用[J].計算機工程與應用，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è)車間調(diào)度優(yōu)化方法[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] 譚躍，譚冠政，鄧曙光.基于遺傳交叉和多混沌策略改進的粒子群優(yōu)化算法[J].計算機應用研究，2016（12）：3643-3647.

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

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

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