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

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

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

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

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

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

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

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

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

1 引言

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

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

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

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

2.1 問(wèn)題描述

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

每件工件在不同機(jī)器上加工過(guò)程中還滿足：

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

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

（2）每一個(gè)工件在某時(shí)刻，只能在一臺(tái)機(jī)器上加工，工序一旦開始被加工便不能中斷（即不考慮機(jī)器故障），直到該工序被加工完成。

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

（4）不同工件的工序之間沒(méi)有先后約束。

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

2.2 析取圖模型

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

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

圖1 表1所示實(shí)例的析取圖模型

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

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

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

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

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

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

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

3.2 搜索種群間競(jìng)爭(zhēng)規(guī)則

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)結(jié)果與分析

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

表2 車間加工信息

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

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

圖6 收斂曲線

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

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

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

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

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

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

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

[1]劉瓊，張超勇，饒運(yùn)清，等.改進(jìn)遺傳算法解決柔性作業(yè)車間調(diào)度問(wèn)題[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)平，來(lái)春為，等.改進(jìn)遺傳算法求解柔性車間調(diào)度問(wèn)題[J].西北大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，41（4）：611-616.

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

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

[6]張維存，鄭丕諤，吳曉丹.蟻群遺傳算法求解能力約束的柔性作業(yè)車間調(diào)度問(wèn)題[J].計(jì)算機(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]王萬(wàn)良，趙澄，熊婧，等.基于改進(jìn)蟻群算法的柔性作業(yè)車間調(diào)度問(wèn)題的求解方法[J].系統(tǒng)仿真學(xué)報(bào)，2008，20（16）：4326-4329.

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

[10]劉志勇，呂文閣，謝慶華，等.應(yīng)用改進(jìn)蟻群算法求解柔性作業(yè)車間調(diào)度問(wèn)題[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].計(jì)算機(jī)工程，2012，38（18）：182-185.

[13]鄧可，林杰，張鵬.基于信息熵的異類多種群蟻群算法[J].計(jì)算機(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].計(jì)算機(jī)工程與應(yīng)用，2012，48（10）：233-237.

[16]董蓉，何衛(wèi)平.求解FJSP的混合遺傳-蟻群算法[J].計(jì)算機(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

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

柔性作業(yè)車間調(diào)度；多種群蟻群；競(jìng)爭(zhēng)規(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é)研究計(jì)劃（No.12JK0998）。

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

2013-06-26

2013-08-15

1002-8331（2013）24-0243-06