張曉玲，何彩香，陳建華

（大理學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

蟻群算法在車間調(diào)度問題中的應(yīng)用

張曉玲，何彩香，陳建華

（大理學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，云南大理 671003）

提出用蟻群算法求解車間調(diào)度問題。車間調(diào)度問題是典型的非確定性多項(xiàng)式時(shí)間難問題，蟻群算法是一種分布式進(jìn)化計(jì)算方法，具有魯棒性，正反饋，并行性等特點(diǎn)，而且算法簡單。給出了用蟻群算法求解車間調(diào)度問題的流程，并且用經(jīng)典的J SP的樣例對算法進(jìn)行了測試，實(shí)驗(yàn)結(jié)果表明用蟻群算法可以求解得到車間調(diào)度問題的最優(yōu)解或近似最優(yōu)解。

蟻群算法；車間調(diào)度問題；信息素；

0 引言

車間調(diào)度問題（Job-Shop Scheduling Problem，JSP）是在經(jīng)典的調(diào)度理論中所描述的最難的組合問題中的一種，是典型的非確定性多項(xiàng)式時(shí)間難問題（NP）。已經(jīng)有許多方法用來解決JSP，包括線性規(guī)劃、神經(jīng)網(wǎng)絡(luò)〔1〕、遺傳算法〔2〕、禁忌搜索〔3〕、粒子群算法〔4〕和螞蟻系統(tǒng)等等。

蟻群算法（Ant Colony Algorithm，ACA）是由意大利學(xué)者M(jìn).Dorigo在20世紀(jì)90年代提出的一種模仿自然界螞蟻群的覓食行為的一種分布式進(jìn)化計(jì)算方法，具有并行性、算法簡單和求解效率高等特點(diǎn)。蟻群算法模擬了自然界螞蟻尋找從蟻巢到食物源的最短路徑并找到回蟻巢路徑的機(jī)制，螞蟻之間通過一種信息素（“激發(fā)工作”，stigmergy）〔5〕來相互交流信息。螞蟻在移動(dòng)的過程中，會(huì)在經(jīng)過的路徑上散發(fā)信息素，蟻群通過感知路徑上的信息素進(jìn)行通信，個(gè)體之間并不直接進(jìn)行交互，而是通過改變它們共同存在的環(huán)境進(jìn)行交互，個(gè)體又通過對環(huán)境的改變?nèi)ビ绊懫渌鼈€(gè)體的行為，從而形成了一種正反饋機(jī)制。長度越短的路上，經(jīng)過的螞蟻越多，聚集的信息素也越多，螞蟻趨向于選擇信息素多的路徑移動(dòng)。通過這種機(jī)制，經(jīng)過一段時(shí)間后螞蟻?zhàn)罱K能夠發(fā)現(xiàn)最短路徑。蟻群算法已經(jīng)被成功地應(yīng)用于解決組合優(yōu)化問題，如：旅行商問題（Traveling Salesman Problem）〔6〕，二次分配問題（Quadratic Assignment Problem），JSP等。本文討論的是用ACA求解JSP。

1 車間調(diào)度問題

1.1 問題的描述 JSP問題可以描述為：有n（n≥3）個(gè)加工順序不同的工件要在m（m＞2）臺機(jī)器上完成加工。

已知：工件集J=｛J1，J2，…，Jn｝，Ji為第i個(gè)工件，i= 1，2，…，n；機(jī)器集M={M1，M2，…，Mm}，Mj為第j號機(jī)器，j=1，2，…，m；每個(gè)工件有k道工序，每道工序要求在不同的機(jī)器上加工，并且預(yù)先已經(jīng)定義了每個(gè)工件在m臺機(jī)器上的加工順序，uij表示工件i在機(jī)器j上加工，工序序列集O={uij｜i∈〔1，n〕，j∈〔1，m〕｝，其中n為工件的數(shù)目，m為機(jī)器的數(shù)目。

每個(gè)工件使用每臺機(jī)器的時(shí)間矩陣T，tij∈T為第i個(gè)工件Ji使用第j臺機(jī)器的時(shí)間。tij=0表示工件Ji不使用機(jī)器Mj。

JSP問題滿足以下約束：①每個(gè)工件使用每臺機(jī)器不多于1次；②不同的工件的工序之間沒有先后約束；③每臺機(jī)器一次只能加工一個(gè)工件，并且工序一旦進(jìn)行不能間斷；④工件加工過程中沒有新工件加入，也不臨時(shí)取消工件的加工。

cij=cik+Tij是工序uij相對于關(guān)系uik→uij的完整的執(zhí)行時(shí)間，調(diào)度目標(biāo)：求出可行的工序的加工序列，使其最后一道工序的最大完工時(shí)間Cmax最小。

1.2 JSP的表示 可以用析取圖D=（N，A，B）來表示JSP問題，N是所有結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)工件的一個(gè)工序uij，并且N=m·n。A是工件使用機(jī)器的加工順序的有向弧的集合。B是連接在同一臺機(jī)器上處理的不同工件工序的無向弧的集合。為了確定先對哪個(gè)工件進(jìn)行加工和什么時(shí)候加工結(jié)束，需要設(shè)置一個(gè)初始結(jié)點(diǎn)O0和調(diào)度結(jié)束的結(jié)點(diǎn)O10。以3個(gè)工件3臺機(jī)器的問題作為例子。如圖1。

圖1 3／3／G／Cmax JSP的表示圖

在圖1中，0=O0，10=O10，1=u12，2=u13，3= u11，4=u21，5=u22，6=u23，7=u31，8=u33，9=u32，結(jié)點(diǎn)1旁邊的（1，2）5表示工件1的第一道工序在機(jī)器2上處理，處理時(shí)間為5，圖中除與O0和O10相連的有向弧，其它的有向弧表示同一個(gè)工件的加工順序，工序必須按照該順序進(jìn)行加工，其它的為無向弧。每一行加工一個(gè)工件，123加工工件1，456加工工件2，789加工工件3。每個(gè)工件只能使用每臺機(jī)器一次，有m臺機(jī)器，則每個(gè)工件就有m道工序。因此求解JSP就變成在滿足約束的前提下，求得上圖中結(jié)點(diǎn)的一個(gè)序列，例如{4，1，7，8，2，3，5，9，6｝，求出在每臺機(jī)器上加工完畢所有的工件的最后一道工序時(shí)的最大完工時(shí)間，求解目標(biāo)：求出最大完工時(shí)間最小的序列，即為調(diào)度的最佳序列。

2 ACA求解JSP

根據(jù)圖1，ACA求解JSP的基本工作過程如下：

由于在整個(gè)工件調(diào)度的過程中添加了一個(gè)開始的結(jié)點(diǎn)O0和結(jié)束的結(jié)點(diǎn)On+1，因此所有的螞蟻從結(jié)點(diǎn)0（工序0）出發(fā)，最后到達(dá)的結(jié)點(diǎn)是結(jié)點(diǎn)10。設(shè)集合Gk是沒有訪問過的結(jié)點(diǎn)的集合，Sk表示根據(jù)約束規(guī)則下一步允許訪問的結(jié)點(diǎn)的集合，還需要一個(gè)禁忌表J k，存放已經(jīng)訪問過的結(jié)點(diǎn)。在上面的例子中，Gk={1，2，3，4，5，6，7，8，9}，Sk={1，4，7}。首先螞蟻分布在0結(jié)點(diǎn)，然后每個(gè)螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一個(gè)結(jié)點(diǎn)，螞蟻傾向于選擇那些加工時(shí)間較短且信息素強(qiáng)度較高的路徑，圖中的每個(gè)弧表示節(jié)點(diǎn)間信息素的量和啟發(fā)式距離的一對值 {αij，Tij}，Tij通常為對工件j的第i步工序的加工時(shí)間。每選擇一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)就被追加到禁忌表Jk中并從Gk中刪除：如果被選的結(jié)點(diǎn)不是工件的最后一步，那工件中緊鄰的下一個(gè)結(jié)點(diǎn)就會(huì)被加入到Sk中。單個(gè)的螞蟻在遍歷過程中根據(jù)信息素局部更新規(guī)則在路徑上釋放一定數(shù)量的信息素，同時(shí)螞蟻經(jīng)過的路徑上的信息素隨著時(shí)間的推移而蒸發(fā)。當(dāng)所有的螞蟻都完成了它們的遍歷過程之后，Gk=?。最后禁忌表中得到的結(jié)點(diǎn)的排序序列就是螞蟻k找到的解。此時(shí)可以計(jì)算出此次迭代的最小的最大完工時(shí)間，再應(yīng)用信息素全局更新規(guī)則對獲得最小的最大完工時(shí)間的螞蟻所經(jīng)歷的邊上的信息素進(jìn)行更新。此后算法反復(fù)迭代直至滿足終止條件后結(jié)束?？梢?，蟻群算法的求解過程主要由三個(gè)規(guī)則控制，即狀態(tài)轉(zhuǎn)移規(guī)則，信息素全局更新規(guī)則和信息素局部更新規(guī)則。下面將對這三個(gè)規(guī)則進(jìn)行說明。

2.1 狀態(tài)轉(zhuǎn)移規(guī)則 ACA中的狀態(tài)轉(zhuǎn)移規(guī)則（又叫做“偽隨機(jī)比例規(guī)則”），“偽隨機(jī)比例規(guī)則”為在保持探索（exploration）一條新的邊和利用螞蟻所積累的搜索經(jīng)驗(yàn)開發(fā)（exploitation）一條邊之間的平衡提供了一種直接的方式，狀態(tài)轉(zhuǎn)移規(guī)則如下：位于結(jié)點(diǎn)r的螞蟻k使用以下的規(guī)則（1）選擇結(jié)點(diǎn)s為下一個(gè)要訪問的結(jié)點(diǎn)

在（2）中，τ是信息素，η是啟發(fā)函數(shù)，η（s）=1/T（s）是在結(jié)點(diǎn)s的工序在機(jī)器上的處理時(shí)間的倒數(shù)，Sk是螞蟻k還沒有訪問過的結(jié)點(diǎn)的集合，而β＞0是一個(gè)參數(shù)，用來定義信息素和時(shí)間之間的相對重要性。q是一個(gè)均勻分布的隨機(jī)數(shù)，q∈〔0，1〕，0≤q0≤1是自定義的一個(gè)參數(shù)。S是根據(jù)以下的概率公式（3）計(jì)算得來的隨機(jī)變量。

偽隨機(jī)比例規(guī)則使得螞蟻傾向于選擇加工時(shí)間短且信息素強(qiáng)度濃的路徑。參數(shù)q0決定了“探索”和“開發(fā)”之間的相對重要性。當(dāng)位于結(jié)點(diǎn)r的螞蟻k要選擇下一個(gè)將要訪問的結(jié)點(diǎn)時(shí)，它選擇一個(gè)隨機(jī)數(shù)0≤q≤1，如果q≤q0則按照式（1）根據(jù)啟發(fā)信息和信息素強(qiáng)度取最好的邊，否則，按照式（2）隨機(jī)比例規(guī)則選擇下一條要移動(dòng)的邊。

2.2 信息素全局更新規(guī)則 在ACA中，當(dāng)所有的螞蟻都訪問完所有的結(jié)點(diǎn)以后，只有那些屬于最小的最大完工時(shí)間的邊上的信息素才被得到增強(qiáng)，信息素全局更新規(guī)則的使用使算法的尋優(yōu)過程更具有指導(dǎo)性：最小的最大完工時(shí)間尋找始終是在當(dāng)前找到的最小完工時(shí)間的附近進(jìn)行。按以下的公式（4）對最小的最大完工時(shí)間的邊上的信息素進(jìn)行更新。

其中，

0＜α＜1是信息素衰減系數(shù)，而Tgb是螞蟻k在本次循環(huán)中找到的最小的最大完工時(shí)間。

2.3 信息素局部更新規(guī)則 單個(gè)的螞蟻在遍歷過程中按照式（5）信息素局部更新規(guī)則對它所經(jīng)過的邊上的信息素進(jìn)行更新。

0＜ρ＜1是信息素?fù)]發(fā)系數(shù)，τ0是預(yù)先設(shè)置的信息素的初始值，信息素局部更新規(guī)則使得被螞蟻經(jīng)過的路徑減少了一部分信息素，使得這些邊被后來的螞蟻經(jīng)過的可能性減少，增強(qiáng)了算法的“勘探”能力，從而有效的避免算法進(jìn)入停滯狀態(tài)（所有的螞蟻收斂到同一解）。

2.4 ACA求解JSP的算法描述 假設(shè)以下是求n個(gè)工件m個(gè)機(jī)器的JSP問題，螞蟻的個(gè)數(shù)為工件的個(gè)數(shù)，則求解JSP的ACA流程圖。見圖2。

描述如下：

步驟1：初始化算法的各項(xiàng)參數(shù)：初始信息素τ0，ρ，β，α，螞蟻個(gè)數(shù)n，最大迭代次數(shù)，工件數(shù)n，機(jī)器數(shù)m等等；

步驟2：把n只螞蟻放在開始結(jié)點(diǎn)0上；

步驟3：每一只螞蟻應(yīng)用偽隨機(jī)比例規(guī)則（2）和（3）選擇下一個(gè)要訪問的工序，并應(yīng)用信息素局部更新規(guī)則（5）更新螞蟻所經(jīng)過的路徑上的信息素；

步驟4：所有的螞蟻都到達(dá)了最后結(jié)束的結(jié)點(diǎn)n+l，每只螞蟻就構(gòu)建了JSP的一個(gè)解，計(jì)算出此次迭代中所有螞蟻的最大完工時(shí)間，求出其中完工時(shí)間最小的值，應(yīng)用信息素全局更新規(guī)則（4）更新最小的最大完工時(shí)間的邊上的信息素；

步驟5：判斷是否已經(jīng)滿足結(jié)束的條件，如果滿足，則輸出最小的最大完工時(shí)間的值，否則跳轉(zhuǎn)到步驟2繼續(xù)執(zhí)行下一次的迭代。

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

本文采用了4個(gè)經(jīng)典的JSP問題：FT03，F(xiàn)T06，LA06和LA07的測試用例來說明用ACA求解JSP的優(yōu)勢。

3.1 實(shí)驗(yàn)仿真 樣例的規(guī)模不同，ACA在求解時(shí)候的參數(shù)的設(shè)置也不同，具體的參數(shù)設(shè)置見表1。

表1 蟻群算法求解JSP的參數(shù)設(shè)置

為了降低由于系統(tǒng)和統(tǒng)計(jì)的誤差，對求解的每個(gè)用例都進(jìn)行了10次的仿真，實(shí)驗(yàn)結(jié)果是10次仿真的統(tǒng)計(jì)值（平均最優(yōu)值和方差等）。

3.2 結(jié)果比較 表2給出了使用ACA求解4個(gè)樣例的結(jié)果，由于這里給出的數(shù)據(jù)是基于10次測試的平均值，因此可能會(huì)有小數(shù)。同時(shí)，表中的“OPT”一列是樣例的已知的最優(yōu)解。從表2的數(shù)據(jù)中可以看出，采用ACA來求解JSP具有非常明顯的優(yōu)勢。ACA能夠很快的找到問題的最優(yōu)解。為了能更加直觀地反映算法的優(yōu)勢，圖3給出了FT06，LA06和ABZ6在優(yōu)化問題的時(shí)候的進(jìn)化特征曲線。

表2 基于表1的參數(shù)設(shè)置的ACA求同JSP的平均結(jié)果

圖3 ACA求解不同JSP的進(jìn)化特征曲線圖

在圖3中可以看出ACA在求解JSP（FT06，LA06和AB Z6）時(shí)用了1 000次迭代的收斂速度，一般都在500次迭代左右就可以收斂（ABZ6問題的最優(yōu)解出現(xiàn)在每次迭代中）。雖然表2和圖3都體現(xiàn)出了A C A在求解J S P時(shí)的高效性，當(dāng)然A C A在求解JSP時(shí)也存在工件數(shù)目越多算法的時(shí)間復(fù)雜度越大等問題。

對于ACA求解復(fù)雜的J S P的時(shí)間消耗，還需要對A C A進(jìn)行改進(jìn)或融入其它的一些算法，以使算法能夠在求得最優(yōu)解的基礎(chǔ)上時(shí)間消耗最小。

4 結(jié)束語

針對ACA求解JSP，對該算法的基本原理進(jìn)行了闡述并且給出了具體的實(shí)現(xiàn)方案，最后還通過典型的JSP測試樣例進(jìn)行實(shí)驗(yàn)仿真，實(shí)驗(yàn)結(jié)果證明了該策略不但在收斂速度上而且在求解精度上都有很大的優(yōu)勢。

〔1〕唐大志.用Hopfield神經(jīng)net解決作業(yè)調(diào)度問題〔J〕.遼寧工程技術(shù)大學(xué)學(xué)報(bào)，2004，23（S）：88-90.

〔2〕李勝輝，李瑩.遺傳算法與人工免疫算法對車間調(diào)度問題求解〔J〕.計(jì)算機(jī)應(yīng)用研究，2009，26（8）：2928-2930.

〔3〕李俊清，潘全科，王玉亭，等.塊鄰域結(jié)構(gòu)的禁忌搜索算法在車間調(diào)度問題中的應(yīng)用〔J〕.機(jī)床與液壓，2009，32（11）：173-188.

〔4〕張長勝，孫吉貴，歐陽丹彤，等.求解車間調(diào)度問題的自適應(yīng)混合粒子群算法〔J〕.計(jì)算機(jī)學(xué)報(bào)，2009，32（11）：2138-2145.

〔5〕Dorigo M，Stitzle T.Ant Colony Optimization〔M〕.MA：MITPress，2004.

〔6〕張曉玲，黃力.融入遺傳算子的蟻群算法求解TSP問題〔J〕.廣西民族大學(xué)學(xué)報(bào)，2009，15（3）：81-87.

Ant Colony Algorithm for Solving Job-Shop Scheduling Problem

ZHANG Xiaoling,HE Caixiang,CHEN Jianhua
（College ofMathematics and Computer Science，DaliUniversity,Dali,Yunnan 671003,China）

This paper proposes Ant Colony Algorithm（ACA）to solve Job-shop Scheduling Problem（JSP）.Job-Shop scheduling problem is a typical NP hard problems,ant colony algorithm is a distributed evolutionary computation methods,The main characteristics of this algorithm are robustness,positive feedback,parallelism,and simple.In this paper,the flow of ant colony algorithm used to solve Job-shop scheduling problem is given,the numerical experiments of ACA were implemented in a small JSP, the experimental results show that the ant colony algorithm can be used to solve job shop scheduling problem and the optimal solution or near optimal solution can be achieved.

Ant Colony Algorithm;Job-Shop Scheduling Problem;pheromone;

TP18

A

1672-2345（2010）10-0010-05

云南省教育廳科研基金資助項(xiàng)目（2010Y349）

2010-04-09

2010-05-20

張曉玲，講師，主要從事進(jìn)化計(jì)算的研究.

（責(zé)任編輯 董 杰）