基于多種群蟻群算法的柔性作業(yè)車間調(diào)度研究

薛宏全，魏生民，張鵬，楊琳

1.西北工業(yè)大學(xué)現(xiàn)代設(shè)計與集成制造技術(shù)教育部重點實驗室，西安 710072

2.西安理工大學(xué)經(jīng)濟與管理學(xué)院，西安 710048

3.西安工業(yè)大學(xué)，西安 710032

基于多種群蟻群算法的柔性作業(yè)車間調(diào)度研究

薛宏全1，2，魏生民1，張鵬2，楊琳3

1.西北工業(yè)大學(xué)現(xiàn)代設(shè)計與集成制造技術(shù)教育部重點實驗室，西安 710072

2.西安理工大學(xué)經(jīng)濟與管理學(xué)院，西安 710048

3.西安工業(yè)大學(xué)，西安 710032

1 引言

柔性作業(yè)車間調(diào)度是Bruker和Schlie在1990年首次提出的，突破了傳統(tǒng)作業(yè)車間調(diào)度中對加工機器的限制，相對于傳統(tǒng)作業(yè)車間調(diào)度，柔性作業(yè)車間調(diào)度擴大了解的范圍，增加了優(yōu)化難度，是一個更為復(fù)雜的NP-hard，但其增加了車間作業(yè)調(diào)度的靈活性，更加符合企業(yè)實際生產(chǎn)現(xiàn)狀，因此求解更為科學(xué)合理的柔性作業(yè)車間調(diào)度方案是近年來國內(nèi)外制造系統(tǒng)調(diào)度研究中的一個熱點問題。

目前求解柔性作業(yè)車間調(diào)度的研究主要集中在運用遺傳算法[1-3]、粒子群算法[4-5]和蟻群算法[6-11]等算法通過迭代方法實現(xiàn)柔性作業(yè)車間調(diào)度方案優(yōu)化。其中，Dorigo博士等人在1991年提出的蟻群算法，因其良好的正反饋、魯棒性和群體性等特點，被越來越多地用于柔性作業(yè)車間調(diào)度求解中。張維存等人[6]以工件延遲時間和設(shè)備可用能力為啟發(fā)信息，設(shè)計螞蟻工件間和設(shè)備間的轉(zhuǎn)移概率，通過螞蟻游歷獲得最優(yōu)適應(yīng)值從而實現(xiàn)柔性作業(yè)車間調(diào)度方案求解。Andrea和王萬良等人[7-8]通過對遍歷螞蟻判斷是否陷入局部收斂分別對各路徑上的信息素進行適當(dāng)調(diào)整加速收斂速度實現(xiàn)柔性作業(yè)車間調(diào)度方案求解，李燕等人[9]以生產(chǎn)周期和關(guān)鍵工件交貨期為優(yōu)化目標，在傳統(tǒng)蟻群算法基礎(chǔ)上自適應(yīng)調(diào)整揮發(fā)系數(shù)ρ，采用機床利用率ηij(t)作為新的啟發(fā)式信息實現(xiàn)柔性作業(yè)車間調(diào)度方案求解。劉志勇和Rong-Hwa Huang等人[10-11]通過修改螞蟻信息素更新規(guī)則，規(guī)定遍歷螞蟻產(chǎn)生至今最優(yōu)解后才釋放更新全局信息素，減少求解時間，提高了柔性作業(yè)車間調(diào)度的求解效率。綜合現(xiàn)有相關(guān)研究分析，發(fā)現(xiàn)目前利用蟻群算法求解柔性作業(yè)車間調(diào)度的研究都是在傳統(tǒng)蟻群算法基礎(chǔ)上采用不同方法修改單一種群中單種信息素更改規(guī)則，雖然通過信息素更新規(guī)則的修改加快了收斂速度，提高了求解效率，但強化最優(yōu)信息的反饋容易導(dǎo)致蟻群早熟和停滯現(xiàn)象；同時利用單一種群求解僅根據(jù)概率保持解之間的差異性，不能實現(xiàn)解的多樣性。實際上蟻群在工作過程中是有組織、有分工的，不同種類的螞蟻有不同的信息素調(diào)控機制[12-13]，體現(xiàn)出不同的搜索特點，這種分工組織方式應(yīng)用到蟻群求解柔性車間調(diào)度中，對保持求解過程中解的多樣性和避免蟻群早熟和停滯現(xiàn)象具有重要意義。

為此，本文結(jié)合蟻群分工組織方式，給出一種基于競爭規(guī)則的多種群蟻群算法求解柔性作業(yè)車間調(diào)度方法。求解中首先運用析取圖表示柔性作業(yè)車間調(diào)度，再將螞蟻分為不同種類的蟻群，把子種群的螞蟻放到圖中各個不同的節(jié)點上，通過螞蟻的移動構(gòu)造出完整的作業(yè)路徑，構(gòu)造路徑過程中核心種群引導(dǎo)子種群在競爭中不斷進化，經(jīng)過反復(fù)迭代不斷優(yōu)化性能指標，最終根據(jù)核心種群對搜索子種群搜索結(jié)果的比較獲得柔性作業(yè)車間最優(yōu)調(diào)度方案。整個求解過程中算法在保證螞蟻總數(shù)不變的前提下，通過不同種群間的行為差異實現(xiàn)種群的多樣性來保障求解過程解的多樣性；同時搜索子種群中應(yīng)用競爭規(guī)則通過種群間競爭，充分發(fā)揮各種群自身的優(yōu)勢，動態(tài)調(diào)整搜索螞蟻的分配，將有限的螞蟻資源分配給搜索率高的種群，有效地緩解柔性作業(yè)車間調(diào)度求解過程中蟻群早熟和停滯現(xiàn)象發(fā)生。

2 柔性作業(yè)車間調(diào)度模型

2.1 問題描述

柔性作業(yè)車間調(diào)度在文獻[14]中被描述為：作業(yè)車間中有n個工件在m臺機器上加工，其中工件集合J為{J1,J2,…,Jn}，機器集合M為{M1,M2,…,Mm}；每個工件Ji由工序{Oi1k,Oi2k,…,Oink}按預(yù)先確定的加工順序加工而成，每道工序Oijk（工件Ji的第j道工序在機器k上加工）可以在一組不同加工機器集合Mij(Mij?M)中任一臺上加工，工序的加工時間隨加工機器的不同而不同；調(diào)度目標是在為每個工件的每道工序選擇最佳加工機器的同時確定每臺加工機器上不同工序的最佳加工順序及開工時間，使整個作業(yè)車間生產(chǎn)達到指定性能指標的最優(yōu)。一個4×5的柔性作業(yè)車間調(diào)度實例[15]如表1所示。

每件工件在不同機器上加工過程中還滿足：

（1）每臺機器在同一時刻只能加工一個工件。

表14 ×5的柔性作業(yè)車間調(diào)度實例

（2）每一個工件在某時刻，只能在一臺機器上加工，工序一旦開始被加工便不能中斷（即不考慮機器故障），直到該工序被加工完成。

（3）不同工件間具有相同的加工優(yōu)先級。

（4）不同工件的工序之間沒有先后約束。

（6）在零時刻，所有工件都可以被加工。

2.2 析取圖模型

析取圖是Roy和Sussman在1964年提出的，由于其簡單直觀和便于分析的突出優(yōu)點，被成功應(yīng)用于旅行商問題的表示中。旅行商問題是推銷員去N個城市推銷貨物，從城市vi(i＜N)出發(fā)，經(jīng)其余所有城市一次，然后回到城市vi，要求所走路線最短。其析取圖描述為：給定圖G=(V,A)，其中V為各城市集合，A為城市間相互連接線組成的邊集，已知各城市間的距離，確定一條長度最短的Hamilton回路，即遍歷所有城市當(dāng)且僅當(dāng)一次的最短回路。

柔性作業(yè)車間調(diào)度是將n種不同工件的所有工序安排到m臺機器上加工，要求最大完工時間makespan最小。通過比較分析發(fā)現(xiàn)，柔性作業(yè)車間調(diào)度和旅行商問題都是NP-hard問題，兩者間具有很強相似性，都可采用析取圖對問題進行表示。因此，在本文中借鑒析取圖表示旅行商問題的方法建立柔性作業(yè)車間調(diào)度模型[15]。柔性作業(yè)車間調(diào)度的析取圖模型描述為：給定圖G=(V,C∪D)，其中V為所有加工工序節(jié)點v和兩個虛擬工序節(jié)點S和E的集合，兩個虛擬工序節(jié)點分別表示調(diào)度的開始和結(jié)束，加工工序節(jié)點v由不同該工序可加工機器組成；C為連通弧集合，C={＜v,w＞|v∈V,w∈V,v和w表示的兩個工序為同一個作業(yè)}，對于?＜v,w＞∈C，stw-stv≥pv表示節(jié)點v到節(jié)點w有一條連通?。閱蜗蚧。ＷC同一工件上的各工序加工順序的先后約束，stv和stw為節(jié)點v和w所表示工序的開始加工時間，pv為節(jié)點v表示工序的加工時間；D為析取弧集合，D=Dr,r=1，2，…，m，Dr={(v,w)|v∈V,w∈V}，每一條析取?。殡p向弧）表示連接的節(jié)點v和節(jié)點w的工序?qū)⒃谕慌_機器上加工。表1所示實例的析取圖模型如圖1所示。

圖1 表1所示實例的析取圖模型

在以最大完工時間makespan最小化為優(yōu)化目標時，對于圖1中第任意一臺機器k(k∈M)的所加工工序而言，每一個加工方案都等價于D中的一個選擇，即在D中的每個雙向弧中選擇一個確定的方向，若為有向非循環(huán)，則對應(yīng)著第k臺機器上所有工序的一個最優(yōu)調(diào)度；同理，對所有加工機器進行選擇，確定一個完整的有向非循環(huán)圖G′=(V,C∪D′)即為Hamilton回路，使得最大完工時間makespan最小。

3 多種群蟻群算法求解原理

根據(jù)蟻群分工組織的工作方式，本文將蟻群分為2大類不同種群的蟻群，如圖2所示。一類是核心蟻群，該種群根據(jù)各搜索蟻群的尋優(yōu)結(jié)果，設(shè)定搜索種群間的信息交流方案，引導(dǎo)搜索蟻群向高效的方向搜索，最終獲得最優(yōu)調(diào)度方案。另一類是搜索種群，該類種群被分布在不同工序節(jié)點上，進行不同資源組合的調(diào)度方案尋優(yōu)，為了保證搜索種群搜索效率，又進一步在搜索種群中引入精英螞蟻和蟻群系統(tǒng)，將搜索種群分解為2子類種群，通過2子類蟻群間的競爭，充分發(fā)揮各子種群自身的優(yōu)勢，動態(tài)調(diào)整搜索螞蟻的分配，將有限的螞蟻資源分配給搜索率高的種群，有效地緩解柔性作業(yè)車間調(diào)度求解過程中蟻群早熟和停滯的現(xiàn)象發(fā)生。

圖2 多種群蟻群結(jié)構(gòu)

3.1 搜索種群間信息交流方案

搜索種群colonyi迭代滿規(guī)定代數(shù)后，根據(jù)交換概率Intervalcolony(i,j)判斷是否與外部種群j進行信息交換，交換時機選擇：

為了避免信息交換對象的隨機選擇，信息交換對象根據(jù)種群間相似度Scolony(i,j)選擇，有：

3.2 搜索種群間競爭規(guī)則

搜索種群搜索過程中，蟻群間的競爭通過淘汰差種群和裂變新種群實現(xiàn)動態(tài)調(diào)整搜索螞蟻的分配，將有限的螞蟻資源分配給搜索率高的種群。

種群間進行淘汰的主要依據(jù)是以各種群搜索效率為依據(jù)建立的種群淘汰裂變數(shù)，淘汰裂變數(shù)定義為：

其中，lit為設(shè)定閾值，iternum(i)表示種群i自最近一次獲得歷史最優(yōu)解到現(xiàn)在的迭代次數(shù)，H為搜索種群的子種群數(shù)。若淘汰裂變數(shù)未達到閾值則認為colonyi種群還有發(fā)現(xiàn)最優(yōu)解的機會，不會被淘汰。

當(dāng)搜索種群的淘汰裂變數(shù)達到閾值時colonyi種群將被淘汰，淘汰種群中的螞蟻數(shù)被平均分配到其他未淘汰種群中，加大這些種群搜索效率。經(jīng)過若干次淘汰種群后，剩下種群數(shù)目小于維持多種群蟻群最低搜索所需數(shù)量時，通過核心種群選取搜索種群中最差值的種群進行裂變，裂變后的種群將生成兩個螞蟻數(shù)與裂變前種群螞蟻數(shù)相同的種群，新生的兩個蟻群中一個繼承原種群的路徑信息繼續(xù)搜索，一個對種群路徑信息進行歸一化處理，加大其他方向的搜索力度，減少現(xiàn)有作業(yè)路徑搜索停滯的可能性。

3.3 信息素更新規(guī)則

核心蟻群通過3.1節(jié)中的種群信息交流方法設(shè)定搜索種群間的信息交流方案，引導(dǎo)搜索種群向高效方向搜索，同時根據(jù)既定優(yōu)化目標對各搜索種群的搜索結(jié)果進行評價，由當(dāng)前獲得的最優(yōu)解作為依據(jù)，使用公式（5）定義的函數(shù)確定迭代過程中信息素的更新變化量。

其中，τmax和τmin分別表示信息素的最優(yōu)和最差值，Δy表示信息素迭代過程中的取值。

搜索種群被放在不同工序節(jié)點上，從不同節(jié)點出發(fā)開始對所有節(jié)點進行遍歷搜索構(gòu)建出完整的加工序列，為了保證搜索種群搜索效率，在搜索種群中引入精英螞蟻和蟻群系統(tǒng)實現(xiàn)對所有節(jié)點的搜索。精英螞蟻在搜索過程中對找到的最優(yōu)路徑Tbs進行額外強化，強化量為e/Lbs，e為常數(shù)，Lbs為Tbs的長度，精英螞蟻信息素更新策略為：

其中，ρ∈[0,1)表示路徑信息素揮發(fā)程度，τvw(t)表示一次循環(huán)中走過vw路徑的螞蟻在該路徑上釋放的信息素總量，Δ(t)表示螞蟻k在這次循環(huán)中在vw路徑上釋放的信息素濃度，Δ(t)表示螞蟻k在到目前循環(huán)中在vw路徑上釋放的最優(yōu)信息素濃度，Δ(t)和Δ(t)更新如下：

其中，Q為預(yù)設(shè)參數(shù)，Lk為所發(fā)現(xiàn)的最佳路徑長度，Lbs為歷史最優(yōu)路徑。

蟻群系統(tǒng)螞蟻的信息素更新策略為：

其中，τvw(t)表示一次循環(huán)中走過vw路徑的螞蟻在該路徑上釋放的信息素總量，Δτ?表示精英種群信息素的更新量。

4 柔性作業(yè)車間調(diào)度求解過程描述

柔性作業(yè)車間調(diào)度求解中首先根據(jù)調(diào)度問題的工件、機器和加工時間等信息，借鑒旅行商問題的析取圖表示方法建立如圖1所示的柔性作業(yè)車間調(diào)度析取圖模型G= (V,C∪D)，同時初始化工件數(shù)組J[][]，機器數(shù)組M[][]，工序數(shù)組O[][]和工件加工時間數(shù)組T[][]等信息；然后采用如圖2的方式，將搜索蟻群向核心蟻群注冊，并初始化所有蟻群；最后核心蟻群向所有搜索蟻群發(fā)布指令，分布在不同節(jié)點上的螞蟻開始搜索，在整個運算過程中搜索蟻群將相關(guān)信息反饋給核心蟻群，核心蟻群根據(jù)反饋信息調(diào)整搜索種群的相關(guān)信息，控制所有螞蟻完成路徑遍歷，并根據(jù)核心種群對搜索子種群搜索結(jié)果比較獲得柔性作業(yè)車間最優(yōu)調(diào)度方案，整個調(diào)度方案求解流程如圖3所示。求解表1所示實例的最優(yōu)調(diào)度方案如圖4所示。

圖3 調(diào)度方案求解流程圖

圖4 表1所示實例的最優(yōu)甘特圖

多種群蟻群算法求解柔性作業(yè)車間調(diào)度的具體步驟如下：

步驟1根據(jù)調(diào)度問題的工件、機器和工件加工時間等信息建立柔性作業(yè)車間調(diào)度的析取圖模型，初始化相關(guān)信息。

步驟2將蟻群分類，一類為核心蟻群，一類為搜索蟻群；初始化核心蟻群相關(guān)信息，將搜索蟻群向核心蟻群注冊，將注冊后的搜索蟻群分為精英螞蟻子群和蟻群系統(tǒng)子群，核心蟻群指令搜索蟻群初始化；搜索蟻群初始化時均被置于初始節(jié)點處，同時將每只螞蟻初始節(jié)點被放入禁忌表Tabu[][]中，并設(shè)置未被訪問的節(jié)點為G[][]以及下一步允許訪問節(jié)點S[][]。

步驟3核心蟻群通知搜索蟻群開始搜索工作，對于每一只搜索螞蟻在一步允許訪問的節(jié)點S[][]中，根據(jù)公式（8）并結(jié)合輪盤賭的策略選擇下一步將訪問的節(jié)點，搜索螞蟻在每經(jīng)過的一條邊vw后，立即更新該邊上的信息素τvw= (1-ρ)τvw+ρ/Lvw。

其中ηvw(t)=1/Stw×Tw，Stw表示工序節(jié)點w的最早加工時間，Tw表示工序節(jié)點w選擇相應(yīng)機器的加工所需的時間。

步驟4將被選中的節(jié)點插入Tabu[][]中，同時從G[][]中刪除該節(jié)點并更新S[][]。

步驟5判斷Tabu[][]是否已滿?若Tabu[][]已滿，則根據(jù)Tabu[][]計算每只螞蟻的目標函數(shù)值，否則，轉(zhuǎn)至步驟3。

步驟6每個搜索蟻群完成一次迭代后，搜索蟻群將對更新圖G中弧上信息素進行一次全局更新，精英蟻群螞蟻和蟻群系統(tǒng)螞蟻分別采用公式（6）和公式（7）實現(xiàn)搜索路徑上信息素的更新。

步驟7核心蟻群判斷搜索種群間是否進行信息交換，首先根據(jù)公式（1）計算交換時機，然后通過公式（2）計算搜索種群間相似度，當(dāng)相似度滿足指定閾值時，根據(jù)公式（3）完成信息交換。

步驟8根據(jù)公式（4）計算搜索種群的種群淘汰裂變數(shù)，當(dāng)種群淘汰裂變數(shù)小于閾值時淘汰該種群并將淘汰種群中的螞蟻數(shù)被平均分配到其他未淘汰種群中；當(dāng)種群數(shù)小于閾值時，核心種群選取搜索種群目標函數(shù)最差值的種群進行裂變。

步驟9執(zhí)行循環(huán)。判斷是否滿足停止條件?是，則結(jié)束循環(huán)輸出最優(yōu)調(diào)度方案；否則，清空Tabu[][]、G[][]和S[][]，轉(zhuǎn)至步驟2。

在上面求解過程中可以看出，蟻群間不斷通過信息交換，發(fā)揮各種群自身的優(yōu)勢，避免了大量冗余操作，在提高了收斂效率同時將有效地緩解蟻群早熟和停滯的現(xiàn)象發(fā)生。

5 實驗結(jié)果與分析

為了測試多種群蟻群算法在求解柔性作業(yè)車間調(diào)度過程中的效率，首先從某航空發(fā)動機公司柔性加工車間生產(chǎn)過程中提取出一個6工件在10臺機器上選擇加工并且每個工件有6道加工工序的柔性作業(yè)調(diào)度實例，工件可選加工機器和加工時間如表2所示。

表2 車間加工信息

算法求解實例時參數(shù)設(shè)置：核心蟻群螞蟻數(shù)為20，α=0.6,β=3，ρ=0.3,Q=15；搜索種群螞蟻數(shù)為所有工序節(jié)點數(shù)，其中搜索種群采用精英蟻群ASelitist和ACS作為兩種子蟻群，ASelitist的初始種群量為4，參數(shù)設(shè)置：α=1，β=5,ρ=0.5,Q=100,e=2，ACS的初始種群量為3，參數(shù)設(shè)置：α=1，β=1,ρ=?=0.1，兩種群間每隔2代進行一次通信，種群淘汰裂變數(shù)閾值為0.35，種群最小數(shù)目為6。整個求解過程在Intel?CoreTMi3 CPU 550@ 3.2 GHz×2，RAM 2.0 GB，操作系統(tǒng)Windows7的計算機上用Matlab 7.0編程實現(xiàn)，求解結(jié)果如圖5所示，不同算法求解收斂曲線如圖6所示，表3是本文算法與其他算法求解結(jié)果比較。

圖5 實例求解結(jié)果

圖6 收斂曲線

表3 不同算法30次求解結(jié)果

從圖6中可看出，ACO和GA算法在求解過程中未能找到最小最大完工時就陷入了局部最優(yōu)中，出現(xiàn)了算法求解過程的早熟和停滯現(xiàn)象，而GA-ACO算法和本文算法都搜索到表2實例中的最小最大完工時間makespan且都為53，避免了算法求解過程的早熟和停滯現(xiàn)象。從表3中可以看出對連續(xù)運行30次所求得的平均值、最差值和平均時間三個性能指標看，本文算法都表現(xiàn)出了較高的搜索效率，從而證明了該算法應(yīng)用于求解柔性作業(yè)車間調(diào)度的可行性。

為了進一步測試本文算法的有效性，本文選取了柔性作業(yè)車間調(diào)度Kacem基準問題中的8×8、10×10和15×10三個實例及Brandimarte設(shè)計的BRdata問題中的mk01（10×6）、mk06（10×15）和mk09（20×10）三個實例，采用上例中的實驗環(huán)境和參數(shù)設(shè)置對這六個實例進行求解，與相關(guān)文獻中測試結(jié)果進行了比較，比較結(jié)果見表4。

表4 與相關(guān)文獻比較

從表4中可以明顯看出，利用多種群蟻群算法求解六個測試實例時所得的最優(yōu)值Cmax均達到了比較文獻中的求解結(jié)果，從而證實了該算法應(yīng)用于求解柔性作業(yè)車間調(diào)度的有效性。

6 結(jié)束語

本文針對柔性作業(yè)車間調(diào)度特點，借鑒旅行商問題的析取圖表示方法建立了柔性作業(yè)車間調(diào)度析取圖模型；并結(jié)合螞蟻工作過程中分工組織的方式，提出了一種基于競爭規(guī)則的多種群蟻群算法對柔性作業(yè)車間調(diào)度析取圖模型進行求解；算法求解過程中將蟻群分為核心蟻群和搜索蟻群兩大類，通過兩者的協(xié)同和搜索蟻群內(nèi)部的競爭，有效地緩解柔性作業(yè)車間調(diào)度求解過程中蟻群早熟和停滯的現(xiàn)象發(fā)生，達到了全局最優(yōu)。最后經(jīng)仿真比較證明了該算法在求解柔性作業(yè)車間調(diào)度中的可行性和有效性。

[1]劉瓊，張超勇，饒運清，等.改進遺傳算法解決柔性作業(yè)車間調(diào)度問題[J].工業(yè)工程與管理，2009，14（2）：59-66.

[2]De Giovanni L，Pezzalla F.An improved genetic algorithm for the distributed and flexible job-shop scheduling problem[J]. European Operational Research，2010，200（2）：395-408.

[3]劉冬梅，傅衛(wèi)平，來春為，等.改進遺傳算法求解柔性車間調(diào)度問題[J].西北大學(xué)學(xué)報：自然科學(xué)版，2011，41（4）：611-616.

[4]張靜，王萬良，徐新黎，等.基于改進粒子群算法求解柔性作業(yè)車間批量調(diào)度問題[J].控制與決策，2012，27（4）：513-518.

[5]盧冰原，程八一.混合粒子群算法在模糊柔性車間作業(yè)計劃中的應(yīng)用[J].計算機應(yīng)用研究，2010，27（10）：3721-3723.

[6]張維存，鄭丕諤，吳曉丹.蟻群遺傳算法求解能力約束的柔性作業(yè)車間調(diào)度問題[J].計算機集成制造系統(tǒng)，2007，13（2）：333-337.

[7]Rossi A，Dini G.Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method[J].Robotics and Computer-Integrated Manufacturing，2007，23（5）：503-516.

[8]王萬良，趙澄，熊婧，等.基于改進蟻群算法的柔性作業(yè)車間調(diào)度問題的求解方法[J].系統(tǒng)仿真學(xué)報，2008，20（16）：4326-4329.

[9]李燕，陳華平，王栓獅，等.自適應(yīng)蟻群算法在雙向生產(chǎn)車間調(diào)度中的應(yīng)用[J].運籌與管理，2008，17（3）：160-163.

[10]劉志勇，呂文閣，謝慶華，等.應(yīng)用改進蟻群算法求解柔性作業(yè)車間調(diào)度問題[J].工業(yè)工程與管理，2010，15（3）：115-119.

[11]Huang Ronghwa，Yang Changlin，Cheng Weiche.Flexible job shop scheduling with due window—a two-pheromone ant colony approach[J].International Journal of Production Economics，2013，141（2）：685-697.

[12]張鵬，魏云霞，薛宏全，等.基于優(yōu)勝劣汰的異類多種群蟻群算法[J].計算機工程，2012，38（18）：182-185.

[13]鄧可，林杰，張鵬.基于信息熵的異類多種群蟻群算法[J].計算機工程與應(yīng)用，2008，44（36）：16-19.

[14]Yazdani M，Amiri M，Zandieh M.Flexible job-shop scheduling with parallel variable neighborhood search algorithm[J].Expert Systems with Applications，2010，37（1）：678-687.

[15]蘇子林，苑金梁，陳煒，等.柔性作業(yè)車間調(diào)度分析及其啟發(fā)式算法[J].計算機工程與應(yīng)用，2012，48（10）：233-237.

[16]董蓉，何衛(wèi)平.求解FJSP的混合遺傳-蟻群算法[J].計算機集成制造系統(tǒng)，2012，18（11）：2492-2501.

XUE Hongquan1，2,WEI Shengmin1,ZHANG Peng2,YANG Lin3

1.Ministry of Education Key Lab of Contemporary Design&Integrated Manufacturing Technology,Northwestern Polytechnical University,Xi’an 710072,China
2.School of Economics and Management,Xi’an University of Technology,Xi’an 710048,China
3.Xi’an Technological University,Xi’an 710032,China

To the characteristics of flexible job-shop scheduling,this paper designs the disjunctive graph model of the flexible job-shop scheduling and presents the solution of the multiple ant colony algorithm for the competitive rule.According to the labor mode of ant colony,different colonies are located in different processing nodes in the algorithm.By the command of core colony, all types of ant colonies with pheromone updating mechanism and searching traits have mutual compensation of advantages as well as mutual competitive exclusion so that they can potentially cooperate smoothly,and fulfill the scheduling requirements of flexible job-shop scheduling.Through the analysis of the simulating experiment results prove the feasibility and effectiveness of the algorithm.

flexible job-shop scheduling;multiple ant colony;competitive rule;disjunctive graph

針對柔性作業(yè)車間調(diào)度的特點，設(shè)計了柔性作業(yè)車間調(diào)度析取圖模型，結(jié)合蟻群分工組織的工作方式，給出了基于競爭規(guī)則的多種群蟻群算法求解方法。算法中不同種群的螞蟻被放置在析取圖中不同的工序節(jié)點上，通過核心種群的引導(dǎo)，充分發(fā)揮蟻群協(xié)作競爭的并行高效特點，滿足柔性作業(yè)車間調(diào)度的要求。仿真實驗表明該算法求解柔性作業(yè)車間調(diào)度具有可行性和有效性。

柔性作業(yè)車間調(diào)度；多種群蟻群；競爭規(guī)則；析取圖

A

TP278

10.3778/j.issn.1002-8331.1306-0315

XUE Hongquan,WEI Shengmin,ZHANG Peng,et al.Flexible job-shop scheduling based on multiple ant colony algorithm.Computer Engineering and Applications,2013,49（24）：243-248.

教育部人文社科基金（No.13YJC630224）；陜西省科技廳自然科學(xué)基金（No.2013JM8039）；陜西省教育廳科學(xué)研究計劃（No.12JK0998）。

薛宏全（1978—），男，博士研究生，講師，研究領(lǐng)域為計算智能，先進制造管理；魏生民（1948—），男，博士，教授，博導(dǎo)，研究領(lǐng)域為現(xiàn)代集成制造技術(shù)，信息化工程與管理；張鵬（1975—），男，博士，講師，研究領(lǐng)域為計算智能。E-mail：msxuehq@xaut.edu.cn

2013-06-26

2013-08-15

1002-8331（2013）24-0243-06