混合粒子群算法在動(dòng)態(tài)車間調(diào)度中的應(yīng)用

楚學(xué)偉

摘? ?要：車間調(diào)度問(wèn)題是廣泛存在于現(xiàn)實(shí)生活中的經(jīng)典算法規(guī)劃問(wèn)題。好的生產(chǎn)調(diào)度系統(tǒng)有利于提高企業(yè)工作效率及降低企業(yè)成本，是工業(yè)生產(chǎn)的核心競(jìng)爭(zhēng)力。粒子群算法因?yàn)閺?qiáng)大的智能規(guī)劃能力而被廣泛用于車間調(diào)度問(wèn)題當(dāng)中。文章在原有標(biāo)準(zhǔn)粒子群算法基礎(chǔ)上，引入模擬退火機(jī)制及遺傳算法中交叉變異策略形成的混合粒子群優(yōu)化算法，并在更具有實(shí)際生產(chǎn)環(huán)境的動(dòng)態(tài)車間調(diào)度中模擬應(yīng)用，與遺傳算法、離散粒子群算法進(jìn)行比較，具有較強(qiáng)優(yōu)勢(shì)。

關(guān)鍵詞：模擬退火;交叉變異;混合優(yōu)化;動(dòng)態(tài)車間調(diào)度

混合粒子群算法（Particle Swarm Optimization，PSO）[1]是基于沒(méi)有免費(fèi)的午餐定理（No Free Lunch，NFL）理論提出來(lái)的，結(jié)合粒子群算法、遺傳算法交叉變異[2-3]及局部搜索算法中模擬退火機(jī)制而形成的混合智能算法，克服了傳統(tǒng)粒子群算法容易陷入局部極值、種群?jiǎn)我坏热秉c(diǎn)，應(yīng)用于更加貼合實(shí)際生產(chǎn)的動(dòng)態(tài)車間調(diào)度問(wèn)題（Job-shop Scheduling Problem，JSP），檢測(cè)算法魯棒性，提高了實(shí)際應(yīng)用能力。

1? ? 標(biāo)準(zhǔn)粒子群算法

PSO算法是一種群智能算法，是模擬鳥(niǎo)群覓食行為的仿生算法，算法中所有粒子都用目標(biāo)函數(shù)來(lái)評(píng)價(jià)該粒子當(dāng)前位置的優(yōu)劣，通過(guò)算法迭代，每個(gè)粒子受到自身及其他粒子的影響，更新自身速度與位置，通過(guò)目標(biāo)函數(shù)確定當(dāng)前個(gè)體最優(yōu)位置pbest及全局最優(yōu)位置gbest。每次迭代粒子的更新公式如下：

Vit+1=ωVit+c1γ1（Pit-Xit）+c2γ2（Pgt-Xit）（1）

Xit+1=Xit+Vit+1（2）

公式（1—2）可看作由N個(gè)粒子組成的一個(gè)群體，在D維搜索空間中，ω為非負(fù)常數(shù)，表示慣性權(quán)重;c1，c2為學(xué)習(xí)因子。γ1，γ2為[0，1]的隨機(jī)數(shù)，為調(diào)節(jié)系數(shù)，向量Xit表示第i個(gè)粒子在第t次迭代后粒子所在的位置，Vit表示第i個(gè)粒子在第t次迭代后粒子所擁有的速度，第i個(gè)粒子t次迭代后個(gè)體最優(yōu)解為Pit，全局最優(yōu)解為Pgt，式中c1γ1（Pit-Xit）表示粒子更新迭代時(shí)對(duì)自身位置、速度的繼承行為，c2γ2（Pgt-Xit）表示粒子更新迭代時(shí)，搜索空間中其他粒子速度對(duì)其影響行為。

2? ? 混合粒子群算法

粒子群算法雖然具有很多優(yōu)點(diǎn)，但其在運(yùn)算過(guò)程中有容易陷入局部極值、魯棒性不強(qiáng)等致命缺點(diǎn)。針對(duì)以上情況，本研究提出對(duì)粒子群算法的幾點(diǎn)改進(jìn)：增加局部搜索策略，引入模擬退火極值，提高局部搜索算法精度;在種群多樣性方面，引入遺傳算法中的交叉變異策略，動(dòng)態(tài)調(diào)節(jié)種群多樣性，增強(qiáng)算法魯棒性。

2.1? 局部搜索策略

模擬退火思想[4]來(lái)源于物理退火原理，分為加溫、平衡、冷卻3個(gè)階段。加溫是使固態(tài)物體變?yōu)橐簯B(tài)的過(guò)程，由相對(duì)穩(wěn)定狀態(tài)轉(zhuǎn)為不平衡狀態(tài)，同時(shí)，固態(tài)液化，消除固態(tài)時(shí)的不均勻狀態(tài);平衡階段是物體與周圍環(huán)境進(jìn)行熱量交換的過(guò)程，當(dāng)物體的自由能降到最低時(shí)，系統(tǒng)達(dá)到平衡狀態(tài);冷卻階段是物體由液態(tài)凝固到固態(tài)的過(guò)程，在此階段，系統(tǒng)內(nèi)能量逐漸減少，物體內(nèi)粒子相對(duì)運(yùn)動(dòng)減弱，物體由液態(tài)變?yōu)楣虘B(tài)。模擬退火算法可以接受比當(dāng)前更差的解，因此，具有很好的局部搜索能力。

模擬退火機(jī)制利用Metropolis接受機(jī)制[5]，有一定概率會(huì)產(chǎn)生較差鄰域解，從而使得新解跳出局部極值，實(shí)現(xiàn)全局搜索的目的。設(shè)目標(biāo)函數(shù)為f（x），當(dāng)前迭代次數(shù)時(shí)全局最優(yōu)解為f（x1），產(chǎn)生鄰域解為f（x2），兩者差值設(shè)定df=f（x2）- f（x1），則Metropolis準(zhǔn)則接受鄰域值得概率p為：

（3）

由公式（3）可以看出，當(dāng)df<0時(shí)，一定會(huì)產(chǎn)生新的鄰域解，即當(dāng)前迭代沒(méi)有達(dá)到局部最優(yōu)解狀態(tài)，可繼續(xù)產(chǎn)生最優(yōu)解;當(dāng)df≥0時(shí)，算法以概率接受鄰域解，即當(dāng)前全局最優(yōu)解好于鄰域解時(shí)，會(huì)以一定概率產(chǎn)生鄰域較差解，以便跳出局部極值，達(dá)到全局搜索目的。

2.2? 交叉變異策略

交叉變異操作[6]是遺傳算法的重要組成部分，算法通過(guò)交叉操作從父代獲取有利基因，淘汰不利基因，從而讓后臺(tái)保持有利基因;算法通過(guò)變異操作引導(dǎo)算法向適應(yīng)度更高的最優(yōu)解靠攏，更好地實(shí)現(xiàn)全局搜索，增強(qiáng)種群多樣性。

2.2.1? 交叉操作

兩個(gè)父代粒子x1，x2，將x1粒子隨機(jī)選中和保留粒子的基因位，并記錄選中基因個(gè)數(shù)，在x2粒子隨機(jī)選中與x1粒子選中基因相同的對(duì)應(yīng)基因位，并保留其所在基因，復(fù)制到子代y粒子中，同時(shí)，將x1粒子中保留基因按照順序重新排列插入到子代粒子中，完成交叉操作，如圖1所示。

2.2.2? 變異操作

變異操作是提高種群多樣性的有效途徑，引導(dǎo)算法向更高的適應(yīng)度函數(shù)進(jìn)化。變異操作是隨機(jī)選擇父代基因中基因片段的多組不同基因位進(jìn)行互換，如果調(diào)換位置的基因位相同，則父代基因與變異后的子代基因相同，實(shí)質(zhì)上沒(méi)有進(jìn)行變異，圖2為兩組基因位變異操作。

3? ? 動(dòng)態(tài)車間調(diào)度

動(dòng)態(tài)車間調(diào)度是針對(duì)傳統(tǒng)靜態(tài)車間調(diào)度問(wèn)題提出來(lái)的[7]，加工環(huán)境更加復(fù)雜，受外界不可抗力的干擾更多，更加符合現(xiàn)代工業(yè)生產(chǎn)的需要。

3.1? 問(wèn)題描述

靜態(tài)車間調(diào)度問(wèn)題來(lái)源于傳統(tǒng)工業(yè)生產(chǎn)，是從實(shí)際問(wèn)題中產(chǎn)生的抽象數(shù)據(jù)模型。假設(shè)N個(gè)工件在M臺(tái)機(jī)器上進(jìn)行加工，則在靜態(tài)車間調(diào)度下，工件和機(jī)器需要滿足的約束條件包括：（1）預(yù)先指定工件加工工序。（2）預(yù)先指定加工時(shí)間與加工機(jī)器，不得隨意更改。（3）同一時(shí)間，一臺(tái)機(jī)器只能加工一個(gè)工件。（4）無(wú)特殊指定，工件加工優(yōu)先級(jí)一樣[8]。在此基礎(chǔ)上，動(dòng)態(tài)車間調(diào)度增添外界干擾因素，例如：增加緊急訂單、取消訂單、機(jī)器故障等突發(fā)事件。

3.2? 動(dòng)態(tài)調(diào)度窗口

靜態(tài)車間調(diào)度系統(tǒng)一旦初始開(kāi)啟調(diào)度，后期加工就按照原有初始調(diào)度執(zhí)行，不能出現(xiàn)偏差。而在動(dòng)態(tài)調(diào)度系統(tǒng)中，由于不可抗力等突發(fā)情況打破了原有調(diào)度系統(tǒng)，破壞了初始調(diào)度規(guī)則，把產(chǎn)生突發(fā)事件時(shí)需要暫停調(diào)度的窗口稱為動(dòng)態(tài)調(diào)度窗口[9]。由此，動(dòng)態(tài)車間調(diào)度可以看成多個(gè)靜態(tài)車間調(diào)度系統(tǒng)的集合，發(fā)生突發(fā)事件的動(dòng)態(tài)調(diào)度窗口立即暫停當(dāng)前靜態(tài)調(diào)度系統(tǒng)，等待資源分配后進(jìn)行下一次調(diào)度。圖3為動(dòng)態(tài)調(diào)度窗口，在ti時(shí)刻，由于發(fā)生突發(fā)事件，機(jī)器不再執(zhí)行原有調(diào)度程序算法，暫停執(zhí)行。

3.3? 數(shù)據(jù)模型修復(fù)

當(dāng)調(diào)度系統(tǒng)由于發(fā)生突發(fā)事件而產(chǎn)生動(dòng)態(tài)調(diào)度時(shí)，原有調(diào)度系統(tǒng)暫停，在開(kāi)啟新的靜態(tài)調(diào)度系統(tǒng)之前，要保證所有加工機(jī)器及工件等資源已準(zhǔn)備就緒，需要進(jìn)行數(shù)學(xué)模型修正。

3.3.1? 加工時(shí)間修正

當(dāng)在ti時(shí)刻發(fā)生動(dòng)態(tài)調(diào)度時(shí)，加工工件所處狀態(tài)為3種：（1）已加工、正加工及待加工狀態(tài)，由于調(diào)度系統(tǒng)暫停，待加工工件將不再進(jìn)行加工工作。（2）正在加工工件不打斷問(wèn)題連續(xù)性，將繼續(xù)加工至完成。（3）已加工工件正常退出加工調(diào)度系統(tǒng)流程。

3.3.2? 修復(fù)時(shí)間修正

當(dāng)在ti時(shí)刻發(fā)生動(dòng)態(tài)調(diào)度時(shí)，加工機(jī)器所處狀態(tài)為3種：（1）空閑、正加工、故障，由于調(diào)度系統(tǒng)暫停，本處空閑狀態(tài)機(jī)器不再加工工件。（2）正加工工件不打斷問(wèn)題連續(xù)性，將正加工工件加工完成。（3）故障機(jī)器在指定修復(fù)時(shí)間內(nèi)完成修復(fù)，重啟調(diào)度系統(tǒng)。

4? ? 仿真模擬實(shí)驗(yàn)

本研究在經(jīng)典實(shí)例FT06基礎(chǔ)上引入突發(fā)機(jī)器故障情況，以最短加工時(shí)間為優(yōu)化目標(biāo)，討論混合粒子群算法與遺傳算法、離散粒子群算法[10]對(duì)此類問(wèn)題的求解。依照FT06經(jīng)典實(shí)例有以下時(shí)間加工矩陣及機(jī)器加工矩陣：

Jt=，Jm=

假設(shè)t=26時(shí)，機(jī)器4故障，修復(fù)時(shí)間為9。如圖4所示，當(dāng)t=26時(shí)，機(jī)器4故障，機(jī)器2此時(shí)處于空閑狀態(tài)，由于調(diào)度暫停，不再接受調(diào)度任務(wù)，機(jī)器1，3，5，6保持問(wèn)題連續(xù)性，不打斷正在加工工件，可保持正常運(yùn)行至加工完成，t=35時(shí)刻，機(jī)器4修復(fù)完成，資源重新分配，重啟調(diào)度系統(tǒng)。

本研究對(duì)FT06測(cè)試實(shí)例分別在加急訂單、取消訂單、機(jī)器故障情況下，與遺傳算法、離散粒子群算法進(jìn)行對(duì)比實(shí)驗(yàn)，如表1所示，在加急訂單情況下，離散粒子群算法無(wú)法完成尋優(yōu)情況，程序中斷;在取消訂單、機(jī)器故障等情況下，混合粒子群算法優(yōu)于離散粒子群算法與遺傳算法。為進(jìn)一步驗(yàn)證混合粒子群算法收斂性、魯棒性，將FT06動(dòng)態(tài)實(shí)例問(wèn)題用3種算法分別求解10次，每種算法迭代200次，如圖5所示，可以看出，混合粒子群算法在動(dòng)態(tài)車間調(diào)度上收斂速度和收斂效果都優(yōu)于離散粒子群算法（Discrete Particle Swarm Optimization，DPSO）、遺傳算法（Genetic Algorithm，GA）。

5? ? 結(jié)語(yǔ)

在標(biāo)準(zhǔn)粒子群算法基礎(chǔ)上引入模擬退火機(jī)制，增強(qiáng)局部搜索能力，增加遺傳算法中交叉變異策略，增添除原有影響外的其他參考點(diǎn)，增強(qiáng)種群多樣性，并將算法應(yīng)用于動(dòng)態(tài)車間調(diào)度，考慮加急訂單、取消訂單、機(jī)器故障等突發(fā)情況，與DPSO，GA算法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明混合粒子群算法在動(dòng)態(tài)車間調(diào)度中收斂性更強(qiáng)，收斂速度更快，魯棒性更好。

[參考文獻(xiàn)]

[1]EBERHART R，KENNEDY J.A new optimizer using particle swarm theory[C].Nagoya：the 6th International Symposium on Micro Machine and Human Science，1995.

[2]鞠全勇，朱劍英.基于混合遺傳算法的動(dòng)態(tài)車間調(diào)度系統(tǒng)的研究[J].中國(guó)機(jī)械工程，2007（1）：40-43.

[3]于瑩瑩.改進(jìn)自適應(yīng)遺傳算法在作業(yè)車間調(diào)度問(wèn)題中的應(yīng)用研究[D].大連：大連交通大學(xué)，2012.

[4]王瑩，曹軍，張福元.基于模擬退火的改進(jìn)混沌粒子群算法[J].內(nèi)蒙古工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2017（3）：173-177.

[5]林敏，劉必雄，林曉宇.帶Metropolis準(zhǔn)則的混合離散布谷鳥(niǎo)算法求解旅行商問(wèn)題[J].南京大學(xué)學(xué)報(bào)（自然科學(xué)），2017（5）：972-983.

[6]寇保華，楊濤，張曉今，等.基于交叉變異的混合粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用，2007（17）：85-88.

[7]劉建國(guó)，朱恒民，王寧生.混合流水車間符合平衡調(diào)度的免疫算法[J].西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2006（4）：655-659.

[8]劉轍，楊敬松，崔廣才.Job-shop Scheduling問(wèn)題的研究[J].長(zhǎng)春理工大學(xué)學(xué)報(bào)，2003（3）：12，19-21.

[9]張超勇，李新宇，王曉娟，等.基于滾動(dòng)窗口的多目標(biāo)動(dòng)態(tài)調(diào)度優(yōu)化研究[J].中國(guó)機(jī)械工程，2009（18）：2190-2197.

[10]王磊.基于改進(jìn)離散粒子群算法的作業(yè)車間調(diào)度方法研究及應(yīng)用[D].杭州：浙江工業(yè)大學(xué)，2012.

Application of hybrid particle swarm optimization in dynamic workshop scheduling

Chu Xuewei

（College of Information and Technology， Jilin Normal University， Siping 136000， China）

Abstract：Workshop scheduling problem is a classic algorithm planning problem widely existing in real life. A good production scheduling system is conducive to improving the work efficiency and reducing the cost of the enterprise， and is the core competitiveness of industrial production. Particle swarm optimization is widely used in workshop scheduling problems because of its powerful intelligent planning capabilities. Based on the original standard particle swarm algorithm， the hybrid particle swarm optimization algorithm formed by simulated annealing mechanism and cross variation strategy in genetic algorithm is introduced in this paper， and it is used in dynamic workshop scheduling with more practical production environment， compared with genetic algorithm and discrete particle swarm optimization， it has strong advantages.

Key words：simulated annealing; cross mutation; hybrid optimization; dynamic shop scheduling