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

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

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

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

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

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

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

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

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

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

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

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

1）每個(gè)工件的加工工序不能改變。

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

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

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

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

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

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

2　GSPSO算法描述

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

微粒群優(yōu)化算法是基于群體尋優(yōu)的進(jìn)化算法，它將每個(gè)個(gè)體看作是D維搜索空間中的一個(gè)沒(méi)有體積的微粒，每個(gè)微粒都代表極值優(yōu)化問(wèn)題的一個(gè)潛在最優(yōu)解，用位置、速度和適應(yīng)度值三項(xiàng)指標(biāo)表示該微粒的特性適應(yīng)度值由適應(yīng)度函數(shù)計(jì)算而來(lái)，其值的好壞表示粒子的優(yōu)劣。微粒在解空間中運(yùn)動(dòng)，通過(guò)跟蹤個(gè)體極值Pbest和群體極值Gbest更新個(gè)體位置。個(gè)體極值Pbest是指?jìng)€(gè)體所經(jīng)歷位置中計(jì)算得到的適應(yīng)度值最優(yōu)位置，群體極值Gbest是指種群中所有粒子搜索到的適應(yīng)度最優(yōu)位置。其優(yōu)化過(guò)程可用下式表示[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)化算法是針對(duì)連續(xù)優(yōu)化問(wèn)題提出，而要用于解決離散問(wèn)題必須對(duì)算法進(jìn)行改進(jìn)。由式（2）和式（3）可知，微粒具有自身的認(rèn)知能力和社會(huì)信息共享能力，這也是種群進(jìn)化的依據(jù)。為了能使用PSO算法對(duì)離散的JSP問(wèn)題進(jìn)行處理，文中提出了式（4）用于粒子更新：

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

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

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

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

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

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

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

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

Step4：最優(yōu)選擇

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

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

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

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

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

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

PSO算法是通過(guò)適應(yīng)度值函數(shù)來(lái)對(duì)個(gè)體的自身性能及種群的整體性能進(jìn)行評(píng)價(jià)的，根據(jù)適應(yīng)度的大小對(duì)個(gè)體進(jìn)行優(yōu)勝劣汰的選擇，進(jìn)而決定個(gè)體的下一步操作。由于本文以調(diào)度任務(wù)的最大完工時(shí)間最少為優(yōu)化目標(biāo)，因此可以用式（1）的倒數(shù)作為算法的適應(yīng)度值評(pí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ù)最小的最大完工時(shí)間為f（t），則當(dāng)前解最小的最大完工時(shí)間為，新解最小的最大完工時(shí)間為，兩者的差值為，則Metropolis準(zhǔn)則接受概率為：

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

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

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

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

為了使算法能夠在全局范圍內(nèi)搜索最優(yōu)解，避免進(jìn)入局部最優(yōu)解，增加種群的多樣性，對(duì)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ī)的交換微粒中若干對(duì)工序的位置。

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

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

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

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

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

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

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)度問(wèn)題對(duì)算法進(jìn)行測(cè)試，算法的基本參數(shù)設(shè)置如下：

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

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

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

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

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

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

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

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

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

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

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

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

4　結(jié)束語(yǔ)

文中把遺傳算法的交叉、變異操作和模擬退火算法的Metropolis接受準(zhǔn)則融入到粒子群[9-11]優(yōu)化算法當(dāng)中，形成了混合粒子群算法GSPSO，該算法能自適應(yīng)的調(diào)整變異概率，在全局范圍內(nèi)高效地搜索最優(yōu)解。通過(guò)實(shí)驗(yàn)結(jié)果表明該算法對(duì)小規(guī)模的JSP問(wèn)題具有很好的搜索質(zhì)量和較快的收斂速度，能對(duì)車間調(diào)度生產(chǎn)過(guò)程中發(fā)生的動(dòng)態(tài)事件進(jìn)行及時(shí)有效的處理；但是對(duì)大規(guī)模的JSP問(wèn)題是否能取得好的效果還有待驗(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]雷蕾.基于混合蟻群算法的動(dòng)態(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ū)動(dòng)的作業(yè)車間動(dòng)態(tài)調(diào)度[J].控制工程，2007（S1）:209-213.

[9]孫會(huì)明，陳薇.基于粒子群優(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稿件編號(hào)：201505080

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

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