吳再新，高尚策，2，齊 潔

（1.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海　201620；2.富山大學(xué) 工程學(xué)院，日本 富山　9308555）

求解動態(tài)車間調(diào)度問題的改進(jìn)微粒群算法

吳再新1，高尚策1，2，齊 潔1

（1.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海201620；2.富山大學(xué) 工程學(xué)院，日本 富山9308555）

為了對生產(chǎn)車間調(diào)度過程中發(fā)生的動態(tài)事件進(jìn)行快速、有效的處理，提出了一種將微粒群算法與遺傳算法（GA）、模擬退火算法（SA）相結(jié)合的混合微粒群算法（GSPSO）。通過用標(biāo)準(zhǔn)車間調(diào)度問題對該算法的性能進(jìn)行檢驗(yàn)；然后把該算法用于解決基于事件驅(qū)動調(diào)度策略的動態(tài)車間調(diào)度問題；仿真結(jié)果表明GSPSO算法具有快速的收斂性和可行性，能對生產(chǎn)過程中發(fā)生的動態(tài)事件進(jìn)行合理調(diào)度。

動態(tài)車間調(diào)度；粒子群算法；遺傳算法；事件驅(qū)動

對生產(chǎn)作業(yè)車間進(jìn)行有效的調(diào)度是制造執(zhí)行系統(tǒng)的一項(xiàng)核心技術(shù)，也是研究的一個熱點(diǎn)問題。作業(yè)車間調(diào)度問題（JSP）實(shí)際上就是組合優(yōu)化問題，也是一類典型的NP難題，它可以分為兩種：靜態(tài)調(diào)度和動態(tài)調(diào)度。在過去的幾十年里，大部分學(xué)者對于車間調(diào)度問題的研究都是靜態(tài)的。在實(shí)際的生產(chǎn)過程當(dāng)中，各種突發(fā)事件（如新增緊急訂單、訂單取消、機(jī)器故障等）時常發(fā)生，因此動態(tài)作業(yè)車間調(diào)度更加符合實(shí)際的情況。

在求解JSP問題的方法上，遺傳算法憑借其強(qiáng)大的全局搜索能力，被許多學(xué)者用于解決JSP問題[1]，但是該算法有收斂速度慢、容易早熟的缺點(diǎn)；蟻群算法主要針對調(diào)度問題產(chǎn)生，其在解決JSP問題上也得到了大量的應(yīng)用[2]，該算法對大規(guī)模調(diào)度問題很難得到最優(yōu)解，且求解時間過長。粒子群優(yōu)化算法是Dr.Eberhart與J.Kennedy于1995年正式提出[3]，之后得到了迅速的發(fā)展和廣泛的應(yīng)用，文獻(xiàn)[4]采用微粒群算法與遺傳算法相結(jié)合，提出了改進(jìn)的微粒群算法用于解決模糊車間調(diào)度問題，但是對算法跳出局部最優(yōu)的策略仍待改進(jìn)。在前人研究的基礎(chǔ)上，把遺傳算法交叉變異特性和模擬退火算法的metropolis接受準(zhǔn)則引入到PSO算法中，提出了混合微粒群算法（GSPSO）用于解決作業(yè)車間調(diào)度問題。

1　動態(tài)車間調(diào)度（DJSP）

JSP問題可以簡單的描述為:有n個工件在m臺機(jī)器上進(jìn)行加工，每個工件有一道或者多道工序等待加工，每道工序只能在指定的機(jī)器上進(jìn)行加工，且滿足以下的約束條件[5]：

1）每個工件的加工工序不能改變。

2）每個工件的加工時間和機(jī)器事先已經(jīng)確定。

3）同一工件同一時刻只能在一臺機(jī)器上進(jìn)行加工。

4）一臺機(jī)器同一時刻只能加工一個工件。

調(diào)度的目的就是找到一個合適的加工序列，在滿足上述約束條件的情況下，使得最大加工完成時間最小。所謂最大加工完成時間就是所有工件中最后一道工序加工完成的時間，可用式（1）表示：

其中，表示最佳的調(diào)度方案，表示工件最后一道工序的完工時間。

在實(shí)際的生產(chǎn)過程中，一些隨機(jī)的動態(tài)事件比如新增緊急訂單，訂單取消，機(jī)器故障維修等在所難免，在任務(wù)執(zhí)行過程中必須實(shí)時監(jiān)測這些隨機(jī)事件的發(fā)生，然后對加工任務(wù)執(zhí)行重新調(diào)度，使得調(diào)度系統(tǒng)始終處于最優(yōu)狀態(tài)。這樣，原本是靜態(tài)的作業(yè)車間調(diào)度就變成了動態(tài)調(diào)度。解決動態(tài)事件的策略有兩種[6]，一是基于事件驅(qū)動的調(diào)度策略，即在系統(tǒng)動態(tài)事件發(fā)生時就立即進(jìn)行重調(diào)度。二是周期性的調(diào)度策略，即不管有無動態(tài)事件發(fā)生，系統(tǒng)總是每隔一段時間進(jìn)行一次重調(diào)度。在實(shí)際的生產(chǎn)應(yīng)用當(dāng)中，應(yīng)視情況而選取不同的調(diào)度策略，當(dāng)已知系統(tǒng)會周期性的出現(xiàn)動態(tài)事件（如定期機(jī)器維修）時，應(yīng)采用周期性調(diào)度策略；當(dāng)系統(tǒng)對動態(tài)事件處理的實(shí)時性要求比較高時應(yīng)選取事件驅(qū)動的調(diào)度策略。為了使最大完工時間最小，又要使系統(tǒng)對動態(tài)事件做出及時的響應(yīng)，減少重調(diào)度帶來的時間損耗，本文選用基于事件驅(qū)動的調(diào)度策略。

2　GSPSO算法描述

2.1標(biāo)準(zhǔn)微粒群優(yōu)化算法

微粒群優(yōu)化算法是基于群體尋優(yōu)的進(jìn)化算法，它將每個個體看作是D維搜索空間中的一個沒有體積的微粒，每個微粒都代表極值優(yōu)化問題的一個潛在最優(yōu)解，用位置、速度和適應(yīng)度值三項(xiàng)指標(biāo)表示該微粒的特性適應(yīng)度值由適應(yīng)度函數(shù)計(jì)算而來，其值的好壞表示粒子的優(yōu)劣。微粒在解空間中運(yùn)動，通過跟蹤個體極值Pbest和群體極值Gbest更新個體位置。個體極值Pbest是指個體所經(jīng)歷位置中計(jì)算得到的適應(yīng)度值最優(yōu)位置，群體極值Gbest是指種群中所有粒子搜索到的適應(yīng)度最優(yōu)位置。其優(yōu)化過程可用下式表示[7]：

其中，為慣性權(quán)重，為粒子速度，、為非負(fù)常數(shù)，稱為加速度因子，和是分布在[0，1]區(qū)間的隨機(jī)數(shù)。標(biāo)準(zhǔn)微粒群尋優(yōu)算法的基本流程圖如圖1所示。

圖1　標(biāo)準(zhǔn)微粒群算法流程Fig.1　The standard PSO algorithm flow chart

2.2GSPSO算法概述

微粒群優(yōu)化算法是針對連續(xù)優(yōu)化問題提出，而要用于解決離散問題必須對算法進(jìn)行改進(jìn)。由式（2）和式（3）可知，微粒具有自身的認(rèn)知能力和社會信息共享能力，這也是種群進(jìn)化的依據(jù)。為了能使用PSO算法對離散的JSP問題進(jìn)行處理，文中提出了式（4）用于粒子更新：

式中表示粒子的第t+1次迭代，、分別表示粒子的個體極值和種群的群體極值，茚代表遺傳算法的交叉操作，、分別代表粒子與、交叉時交叉片段的長度，他們的取值范圍是0到微粒的最大長度。由此可知，為粒子的自身的認(rèn)知能力，為種群的社會信息共享能力，而則表示當(dāng)前粒子的權(quán)重。

標(biāo)準(zhǔn)的PSO算法具有快速的收斂能力，但是容易陷入局部最優(yōu)解。將SA算法的metropolis接受準(zhǔn)則融入到PSO算法中，使算法具有突跳能力，能有效的避免搜索過程陷入局部最優(yōu)解。把GA算法的變異操作作用于PSO算法的全局最優(yōu)解，增加種群的多樣性，能使算法得到全局最優(yōu)解。GSPSO算法同時繼承了3個算法的優(yōu)點(diǎn)，使得它能夠快速的在全局范圍內(nèi)尋找最優(yōu)解，又能避免算法在搜索過程中陷入局部最優(yōu)解。GSPSO算法的解決動態(tài)車間調(diào)度問題的基本步驟如下：

Step1：種群初始化，初始種群尋優(yōu)

采用基于工序的編碼方式隨機(jī)生成初始微粒種群，通過適應(yīng)度值函數(shù)對微粒進(jìn)行評價(jià)，找出所有微粒的最佳個體，記為種群的最優(yōu)個體，所有粒子的個體最優(yōu)記為各自的初始位置。

Step2：SA算法Metropolis接受準(zhǔn)則

將SA算法的Metropolis接受準(zhǔn)則作用于個體最優(yōu)微粒，避免算法陷入局部最優(yōu)解。

Step3：遺傳算法的交叉與變異

把遺傳算法的交叉操作引入到PSO算法中粒子的進(jìn)化過程當(dāng)中，用交叉產(chǎn)生的新個體代替粒子的速度和位置的更新。同時把遺傳算法的變異策略作用到全局最優(yōu)微粒，以避免算法陷入局部最優(yōu)，增加種群的多樣性。

Step4：最優(yōu)選擇

當(dāng)算法達(dá)到算法的終止條件后，采用第二步選出來的全局最優(yōu)粒子作為種群的最優(yōu)值Gbest，選出最優(yōu)值之后調(diào)度任務(wù)就可以順利進(jìn)行了。當(dāng)動態(tài)事件出現(xiàn)，調(diào)度任務(wù)被打斷時，進(jìn)入第五步。

Step5：動態(tài)事件處理

通過動態(tài)事件發(fā)生的時刻可以確定待加工的工件和機(jī)器的狀態(tài)，重新進(jìn)入第一步進(jìn)行重調(diào)度。

2.3GSPSO算法的具體實(shí)現(xiàn)

GSPSO算法處理作業(yè)車間動態(tài)調(diào)度問題的算法流程圖如圖2所示。

2.3.1適應(yīng)度值函數(shù)

PSO算法是通過適應(yīng)度值函數(shù)來對個體的自身性能及種群的整體性能進(jìn)行評價(jià)的，根據(jù)適應(yīng)度的大小對個體進(jìn)行優(yōu)勝劣汰的選擇，進(jìn)而決定個體的下一步操作。由于本文以調(diào)度任務(wù)的最大完工時間最少為優(yōu)化目標(biāo)，因此可以用式（1）的倒數(shù)作為算法的適應(yīng)度值評價(jià)函數(shù)，即：

圖2　GSPSO算法流程圖Fig.2　The GSPSO algorithm flow chart

2.3.2Metropolis抽樣準(zhǔn)則

在PSO算法中引入Metropolis準(zhǔn)則，它能以一定的概率接受惡化解，這樣就能使算法跳離局部最優(yōu)的陷進(jìn)。接受概率是這樣確定的，假如調(diào)度任務(wù)最小的最大完工時間為f（t），則當(dāng)前解最小的最大完工時間為，新解最小的最大完工時間為，兩者的差值為，則Metropolis準(zhǔn)則接受概率為：

如果df<0，則以概率1接受新解；否則以概率exp（）接受新解。

2.3.3粒子的編碼規(guī)則

由于調(diào)度問題具有嚴(yán)格的工藝約束，必須以一定的編碼方式來體現(xiàn)其工藝約束，以便用微粒群算法對其進(jìn)行處理。文中采用基于工序的編碼方式對調(diào)度任務(wù)進(jìn)行編碼，該編碼方式進(jìn)行編碼時，用同一數(shù)字表示工件的工件號，用該數(shù)字在微粒中第幾次出現(xiàn)來表示該工件的工序號。例如以一個3*3的作業(yè)車間調(diào)度問題為例，有一個粒子的編碼為232133211，該編碼的第一個數(shù)2表示2號工件的第一道工序，第二個數(shù)3表示3號工件的第一道工序，第三個數(shù)2表示2號工件的第二道工序，以此類推。

2.3.4遺傳算法的變異與交叉操作

為了使算法能夠在全局范圍內(nèi)搜索最優(yōu)解，避免進(jìn)入局部最優(yōu)解，增加種群的多樣性，對PSO算法中的以一定的概率進(jìn)行變異操作。傳統(tǒng)遺傳算法的變異概率是固定不變的，從而使得算法難以跳出局部最優(yōu)，文中提出一種新的計(jì)算變異概率的式（7），

式中為第i次迭代的變異概率，為初始變異概率，為第i次迭代中的適應(yīng)度值函數(shù)，、分別為的最大適應(yīng)度值函數(shù)和平均適應(yīng)度值函數(shù)。這種方法能提高適應(yīng)度值劣于平均適應(yīng)度值微粒的變異概率，抑制適應(yīng)度值優(yōu)于平均適應(yīng)度值微粒的變異概率。變異的方法是隨機(jī)的交換微粒中若干對工序的位置。

在PSO算法中，采用遺傳算法的交叉操作替代PSO算法的種群更新，可以有效的把其應(yīng)用于解決離散的JSP問題。在交叉的過程中，先讓微粒與Pbest交叉，交叉的方法是根據(jù)式（4），在Pbest中選取一段，插入到當(dāng)前微粒的對應(yīng)位置，然后再把此微粒與Gbest進(jìn)行交叉，交叉的方法與前面相同。這樣在交叉后就得到了新的微粒，新的微粒既保存的上一代微粒的信息，又具有信息共享的能力。以一個3*3的車間調(diào)度問題為例，假設(shè)式（4）中常數(shù)、都為2，則一個微粒的交叉過程可用如圖3來描述，交叉后會出現(xiàn)某些工件的工序多余，某些工件的工序缺失的現(xiàn)象，把工件工序多余的操作變?yōu)楣ぜば蛉笔У牟僮?，使得交叉后的微粒符合編碼規(guī)則。

圖3　微粒交叉Fig.3　The cross of particle

2.4動態(tài)作業(yè)車間調(diào)度的實(shí)現(xiàn)過程

在調(diào)度系統(tǒng)的執(zhí)行過程當(dāng)中，由于調(diào)度環(huán)境的動態(tài)變化，需要對加工任務(wù)進(jìn)行重新調(diào)度。重調(diào)度與初始時刻調(diào)度的主要差別是機(jī)器狀態(tài)和加工的工件任務(wù)不同，機(jī)器的可利用時候和工件上一道工序的完成時刻不同。在重調(diào)度時刻，有的機(jī)器可能正在加工工件，由于加工過程的連續(xù)性，只有待機(jī)器加工完該工序，才能進(jìn)入重調(diào)度的調(diào)度安排；而有的機(jī)器可能在重調(diào)度時刻處于空閑狀態(tài)，重調(diào)度之后立即可以投入生產(chǎn)；有的工件可能完成了一部分工序，也有可能完成了全部工序。處理動態(tài)事件的步驟如下：

Step1：系統(tǒng)按照調(diào)度方案進(jìn)行加工，動態(tài)事件發(fā)生時進(jìn)入第二步，如果加工任務(wù)完成沒有動態(tài)事件發(fā)生，結(jié)束調(diào)度任務(wù)。

Step2：確定重調(diào)度加工工件的工序矩陣和對應(yīng)的機(jī)器矩陣，通過動態(tài)事件發(fā)生的時候和初始調(diào)度情況計(jì)算機(jī)器的可利用時刻矩陣。

Step3：產(chǎn)生重調(diào)度方案，轉(zhuǎn)入第一步，調(diào)度任務(wù)繼續(xù)執(zhí)行。

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

實(shí)驗(yàn)仿真在自用PC機(jī)上進(jìn)行，用benchmark車間調(diào)度問題對算法進(jìn)行測試，算法的基本參數(shù)設(shè)置如下：

種群迭代次數(shù)，種群規(guī)模，粒子交叉片段常數(shù)、問題的規(guī)模大小不一適當(dāng)變化，變異初始概率，模擬退火初始溫度，降溫系數(shù)。

表 1是用本文提出的算法和 PSOGA、GA算法解決benchmark車間調(diào)度問題10次，然后取平均值的比較。從表中可以看出，本文提出的PAGSO算法與另外兩種算法相比具有更好的平均值，從而表明該算法在求解JSP問題上具有很好的求解效果。

圖4是3種算法在求解FT06問題時的收斂性比較，圖中橫坐標(biāo)表示算法的迭代次數(shù)，縱坐標(biāo)表示最大完工時間10次的平均值。從圖中可知，PSGSO算法具有更快的收斂速度。

表1　三種算法的比較Tab.1　Comparison of the three algorithms

圖4　三個算法的收斂性比較Fig.4　The convergence comparison of the three algorithms

圖5是用本文提出的PSGSO算法解決DJSP問題時的輸出甘特圖，圖中橫坐標(biāo)表示加工時間，縱坐標(biāo)表示機(jī)器號。限于篇幅只考慮以下3種動態(tài)事件發(fā)生的情況：

圖5　動態(tài)調(diào)度甘特圖Fig.5　The gantt chart of the dynamic job-scheduling

1）新增緊急訂單。在t=20時刻，新增緊急訂單7號工件，該工件工序的時間約束矩陣為T7=[6 3 8 5 4 9]，對應(yīng)的機(jī)器約束矩陣為M7=[6 1 5 2 4 3]，由圖可以看出緊急訂單加入后被優(yōu)先處理，最終的調(diào)度結(jié)果為64。

2）在t=30時刻，取消4號和5號工件，由圖可知在30時刻后工件4和工件5的已經(jīng)從調(diào)度任務(wù)中取消，最終的調(diào)度結(jié)果為52。

3）在t=26時刻，機(jī)器4出現(xiàn)故障，預(yù)計(jì)修復(fù)時間為9，最終調(diào)度結(jié)果為57。

文獻(xiàn)[8]中用混合蟻群算法解決同樣的問題，與本文采用的方法比較如表2所示，結(jié)果表明GSPSO算法具有明顯的優(yōu)勢，說明該算法具有可行性。

表2　混合蟻群算法與GSPSO算法處理DJSP問題時的比較Tab.2　The comparison of ant colony algorithm and GSPSO algorithm to deal with DJSP

4　結(jié)束語

文中把遺傳算法的交叉、變異操作和模擬退火算法的Metropolis接受準(zhǔn)則融入到粒子群[9-11]優(yōu)化算法當(dāng)中，形成了混合粒子群算法GSPSO，該算法能自適應(yīng)的調(diào)整變異概率，在全局范圍內(nèi)高效地搜索最優(yōu)解。通過實(shí)驗(yàn)結(jié)果表明該算法對小規(guī)模的JSP問題具有很好的搜索質(zhì)量和較快的收斂速度，能對車間調(diào)度生產(chǎn)過程中發(fā)生的動態(tài)事件進(jìn)行及時有效的處理；但是對大規(guī)模的JSP問題是否能取得好的效果還有待驗(yàn)證，這也是今后研究的重點(diǎn)內(nèi)容。

[1]ZHAO Zi-xiang，ZHANG Guo-shan，BING Zhi-gang.Jobshopscheduling optimization design based on an improved GA[C]//2012 10th World Congress on Intelligent Control and Automation（WCICA）.Beijing:IEEE，2012:654，659.

[2]雷蕾.基于混合蟻群算法的動態(tài)JSP研究與仿真[D].西安：西安工業(yè)大學(xué)，2012.

[3]Eberhart R，Kennedy J.A new optimizer using particle swarm theory[C]//Proceeding of the Sixth International Symposium on Micro Machine andHuman Science.Nagoya:IEEE，1995: 39-43.

[4]Niu Q，Jiao B，Gu X S.Particle swarm optimization combined with genetic operators for job-shop scheduling problem with fuzzy processingtime[J].Applied Mathematics and Computation，2008，205（1）:148-158.

[5]CHIANG Tsung-Che，F(xiàn)U Li-Chen.Multiobjective Job Shop Scheduling using Genetic Algorithm with Cyclic Fitness Assignment[C]//IEEE Congress on Evolutionary Computation. Vancouver BC:IEEE，2006:326-3273.

[6]SureshV，ChandhuriD.Dynamic Scheduling-A survey of research[J].Int Jof Prod Peon，1993，32（1）:53-63.

[7]YAN Ping，JIAO Ming-hai.Animproved PSO search method for the job shop scheduling problem[C]//Control and Decision Conference.Mianyang:IEEE，2011:23-25.

[8]陸韡，張潔.基于事件及變周期驅(qū)動的作業(yè)車間動態(tài)調(diào)度[J].控制工程，2007（S1）:209-213.

[9]孫會明，陳薇.基于粒子群優(yōu)化的光伏MPPT算法[J].電子科技，2014（8）:187-189.

[10]康鯤鵬.快速混合粒子群優(yōu)化算法應(yīng)用研究[J].電子設(shè)計(jì)工程，2014（10）:10-13.

[11]王娟娟.哈夫曼編碼的協(xié)同粒子群優(yōu)化算法[J].計(jì)算機(jī)與現(xiàn)代化，2015（6）:82-85.

An improved particle swarm optimization algorithm for dynamic job-shop scheduling problem

WU Zai-xin1，GAO Shang-ce1，2，QI Jie1
（1.College of Information Science and Technology，Dong Hua University，Shanghai 201620，China；2.Faculty of Engineering，University of Toyama，Toyama 9308555，Japan）

In order to deal with the dynamic events rapidly and effectively in the process of job-shop scheduling，an improved hybrid Particle Swarm Optimization algorithm（GSPSO）combining with Genetic Algorithm（GA）and Simulated Annealing algorithm（SA）has been proposed.The introduced algorithm is tested by the benchmark job-shop problem（JSP），then，the hybrid algorithm is used to solve the dynamic JSP problem which based on the event driven scheduling strategy.The results of the simulation shows the good convergence and feasible of the improved algorithm，and it can make a good performance in dealing with the uncertain dynamic events.

dynamic job-shop scheduling；particle swarm optimization algorithm；genetic algorithm；event driven

TP18

A

1674－6236（2016）01-0026-05

2015-05-09稿件編號：201505080

國家自然科學(xué)基金項(xiàng)目（61203325）；上海啟明星計(jì)劃項(xiàng)目（14QA1400100）

吳再新（1990—），男，湖南婁底人，碩士。研究方向:人工智能與智能控制。