基于多種群蟻群算法的柔性作業車間調度研究

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

1.西北工業大學現代設計與集成制造技術教育部重點實驗室，西安 710072

2.西安理工大學經濟與管理學院，西安 710048

3.西安工業大學，西安 710032

基于多種群蟻群算法的柔性作業車間調度研究

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

1.西北工業大學現代設計與集成制造技術教育部重點實驗室，西安 710072

2.西安理工大學經濟與管理學院，西安 710048

3.西安工業大學，西安 710032

1 引言

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

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

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

2 柔性作業車間調度模型

2.1 問題描述

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

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

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

表14 ×5的柔性作業車間調度實例

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

（3）不同工件間具有相同的加工優先級。

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

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

2.2 析取圖模型

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

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

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

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

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

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

圖2 多種群蟻群結構

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

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

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

3.2 搜索種群間競爭規則

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

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

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

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

3.3 信息素更新規則

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

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

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

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

其中，Q為預設參數，Lk為所發現的最佳路徑長度，Lbs為歷史最優路徑。

蟻群系統螞蟻的信息素更新策略為：

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

4 柔性作業車間調度求解過程描述

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

圖3 調度方案求解流程圖

圖4 表1所示實例的最優甘特圖

多種群蟻群算法求解柔性作業車間調度的具體步驟如下：

步驟1根據調度問題的工件、機器和工件加工時間等信息建立柔性作業車間調度的析取圖模型，初始化相關信息。

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

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

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

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

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

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

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

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

步驟9執行循環。判斷是否滿足停止條件?是，則結束循環輸出最優調度方案；否則，清空Tabu[][]、G[][]和S[][]，轉至步驟2。

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

5 實驗結果與分析

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

表2 車間加工信息

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

圖5 實例求解結果

圖6 收斂曲線

表3 不同算法30次求解結果

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

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

表4 與相關文獻比較

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

6 結束語

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

[1]劉瓊，張超勇，饒運清，等.改進遺傳算法解決柔性作業車間調度問題[J].工業工程與管理，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]劉冬梅，傅衛平，來春為，等.改進遺傳算法求解柔性車間調度問題[J].西北大學學報：自然科學版，2011，41（4）：611-616.

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

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

[6]張維存，鄭丕諤，吳曉丹.蟻群遺傳算法求解能力約束的柔性作業車間調度問題[J].計算機集成制造系統，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]王萬良，趙澄，熊婧，等.基于改進蟻群算法的柔性作業車間調度問題的求解方法[J].系統仿真學報，2008，20（16）：4326-4329.

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

[10]劉志勇，呂文閣，謝慶華，等.應用改進蟻群算法求解柔性作業車間調度問題[J].工業工程與管理，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]張鵬，魏云霞，薛宏全，等.基于優勝劣汰的異類多種群蟻群算法[J].計算機工程，2012，38（18）：182-185.

[13]鄧可，林杰，張鵬.基于信息熵的異類多種群蟻群算法[J].計算機工程與應用，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]蘇子林，苑金梁，陳煒，等.柔性作業車間調度分析及其啟發式算法[J].計算機工程與應用，2012，48（10）：233-237.

[16]董蓉，何衛平.求解FJSP的混合遺傳-蟻群算法[J].計算機集成制造系統，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

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

柔性作業車間調度；多種群蟻群；競爭規則；析取圖

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）；陜西省科技廳自然科學基金（No.2013JM8039）；陜西省教育廳科學研究計劃（No.12JK0998）。

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

2013-06-26

2013-08-15

1002-8331（2013）24-0243-06