改進的蟻群算法求解置換流水車間調度問題

張麗萍(青島科技大學 信息科學技術學院，山東 青島266061)

置換流水車間是很多實際流水線生產調度問題的簡化模型，是目前研究最廣泛的一類經典的調度問題。由于置換流水車間調度問題屬于NP-hard難題，不存在多項式精確求解算法，因此，對這類問題的研究具有重要意義。

求解置換流水車間調度問題的方法大致可以分為三類[1]：經典算法(如線性規劃、動態規劃、整數規劃、分枝定界等)、啟發式算法(如 Gupta 法、Palmer法、Johnson 法、CDS法、NEH法等)和基于人工智能的元啟發式算法(如模擬退火、禁忌搜索、遺傳算法、螞蟻算法等)。經典算法的計算復雜性一般很大，只適合求解小規模置換流水車間調度問題，在工程中往往不實用。啟發式算法通過一定的規則可以快速地構造出問題的解，但通常解的質量較差[2]。基于人工智能的元啟發式算法能夠較快地構造出問題的解，因此，在置換流水車間調度問題中被廣泛使用。

蟻群算法是受到自然界中真實螞蟻的啟發，由意大利學者DORIGO M于1991年提出的一種元啟發式算法。該算法具有魯棒性和通用性等良好特性，在求解作業車間、流水車間等調度問題上取得了較好的效果。但是，傳統的蟻群算法存在計算時間長和易陷入停滯的問題，故本文從結合NEH算法和自適應調節策略兩方面來改善蟻群算法的性能，經Taillard基準測試驗證，改進后的蟻群算法有效。

1 問題描述

置換流水車間調度問題研究的是n個工件在m臺機器上的流水加工過程，所有工件以相同的順序在每一臺機器上加工完成，同時約定每個工件在每臺機器上只加工一次，每臺機器每次最多只能加工一個工件，各工件在各機器上所需的加工時間已知，要求得到某調度方案使得總加工時間最小。定義J=(j1，…，jn)為所有機器上的一個加工排序，ti，j為操作的執行時間，Ci，j表示操作的完成時間。則加工任務jk在機器i上的完成時間Ci，jk按式(1)計算：

2 蟻群算法

2.1 蟻群算法簡介

螞蟻是一種沒有視覺的動物，但是它們可以通過信息素，協同找到食物和巢穴之間的最短路徑[3]。螞蟻在運動過程中能夠感知這種物質的存在及其強度，并以此指導自己的運動方向，使螞蟻傾向于朝著該物質強度高的方向運動。這樣，由大量螞蟻組成的蟻群的集體行為便表現出一種自催化的正反饋行為，較短路徑上會有較多的信息素累積，越來越多的螞蟻選擇信息素濃度高的路徑，而其他路徑上的信息素濃度卻會隨時間衰減，最終蟻群能找到一條從食物源到巢穴的最短路徑[4]。

蟻群算法最初用于解決旅行商問題，之后陸續滲透到其他領域中。較早把蟻群算法應用到置換流水車間問題的是YING K C和LIAO C J，后者在Tailard的benchmark問題上做了測試，證實該方法非常有效。

2.2 蟻群算法

本文以求解置換流水車間問題說明MMAS模型。求解這類問題有兩種解構造模式，分別為弧模式和節點模式[5]。本文采用的是節點模式。

在解構造的結點模式下，代表流水車間調度問題的有向圖 G=(N，A)，如圖 1所示。 其中，N={Oij}是圖中的節點集合，節點Oij代表作業j位于作業處理序列π的第i個位置；A是圖G中部分連接節點集N中各節點的有向弧的集合，連接節點 Oij和 O(i+1)，l的有向弧方向為從 Oij～O(i+1)，l。 這里的路徑選擇 概率為：

圖1 節點模式下的流水車間

在節點模式下，式(2)中 Nk(Oij)={O(i+1)，l|l?π′}代表節點 Oij的可行領域集合。 其中 τij和 ηij分別代表對應于節點Oij的信息素濃度和基于問題的啟發式信息。表示人工蟻搜索過程中從節點移到節點 Oij的概率。

從虛構節點job0出發，按照式(2)給出的狀態遷移規則，在G圖中一步步地構造出問題的解，蟻群算法的流程如下：

(1)設置參數。設置迭代次數counter=0,設置最大迭代次數Ncmax。計算每個工件的總加工時間Si(i=1，…，n)，定義能見度ηij=Si。按照工件總加工時間 Si最大優先的原則計算出最大流程時間makespan，設置信息素賦初始值 τ0=1/((1-ρ)·makespan)；τmax=τ0，τmin=τmax/5。

(2)初始化m個螞蟻，將m個螞蟻放在虛擬節點job0上。

(3)每個螞蟻都按照式(2)選擇下一步路徑。

(4)將新選擇的工序添加到禁忌表中，判斷是否遍歷了所有的工件，是則執行步驟(5)，否則執行步驟(3)。

(5)按照式(3)更新信息素。

其中，ρ為信息素殘留系數(1-ρ為揮發系數)；△τij=1/Cbest，令Cbest為迭代以來最優解，|Cbest|為 Cbest的 makespan值，如果Cbest中位置 j上工件不為 i，則 △τij為 0，否則 △τij=1/|Cbest|。信 息 素 取 值 區 間 為 [τmin，τmax]， 若 τij＞τmax， 則 設 定 τij=τmax；若 τij＞τmin，則設定 τij=τmin。 這樣可以較好地防止早熟現象。

(6)count++。 如果 count＜Ncmax，則清空禁忌表，返回步驟(2)繼續執行；否則，結束循環。

3 MMAS的優化

3.1 NEH啟發式算法

NEH啟發式算法是由 NAWAZ M、ENSCORE E、和HAM I共同提出的算法[6]，該算法步驟如下：

(1)按n個工件在機器上總加工時間遞減的順序排列各個工件。

(2)取前兩個工件調度使部分最大流程時間達到極小。

(3)從k=3～n把第k個工件插入到k個可能的位置，求得最小部分的最大流程時間。

3.2 與NEH算法的結合

(1)獲取初始解。利用NEH啟發式算法計算得到最大流程時間 makespan，并定義 τ0=1/((1-ρ)·makespan)。

(2)部分NEH局部搜索。在使用MMAS構造出路徑之后，對構造的工件順序按照NEH啟發式算法的步驟(2)、(3)構造出解。利用NEH啟發式算法進行局部尋優，可以進一步提高MMAS的求解質量。但是為了保證算法的時間效率，在此只對Nmax次迭代中的前N次迭代利用NEH啟發式算法對迭代最優螞蟻進一步局部尋優。

3.3 自適應信息素揮發系數

與NEH算法相結合，雖然極大程度地提高了MMAS解質量，但是也從一定程度上加速了MMAS的局部收斂速度。為此，本文引入自適應改變揮發度系數的方法，以進一步提高MMAS的全局搜索能力。

在算法模型中，信息素揮發系數ρ的大小直接關系到蟻群算法的全局搜索能力及收斂速度[3]。ρ過小，從未被搜索到的節點的信息量會減少到接近于0，降低了算法的全局搜索能力；而ρ過大，以前搜索過的解被選擇的可能性過大，也會影響到算法的全局搜索能力。因此可以自適應地改變ρ的值，當最優值在一定循環次數內沒有明顯改變時，降低ρ的值。公式如下：

其中，ρmin為 ρ的最小值，用來防止 ρ過小，降低算法收斂速度。

3.4 改進MMAS的實現流程

改進后的MMAS算法求解置換流水車間問題的流程圖如圖2所示。

圖2 改進MMAS算法流程圖

(1)初始化各個參數。設置螞蟻數量為m、迭代次數counter=0、最大迭代次數為Ncmax、局部搜索次數為 N。計算每個工件的總加工時間Si(i=1，…，n)，定義能見度ηij=Si。 設置信息素殘留系數為 ρ，ρmin為 ρ的最小值，定義Nm次迭代最優解相同，則判定陷入局部最優。

(2)利用NEH啟發式算法得到總加工時間的初始值makespan，設置 τ0=τmax=1/((1-ρ)·makespan)，τmin=1/5·τmax。

(3)將各只螞蟻放在虛擬節點job0上，對于每只螞蟻，按照式(2)選擇下一步路徑，直到所有螞蟻均構造出解。

(4)若count＜N，則利用NEH啟發式算法的后兩步對最優迭代螞蟻選擇的路徑做進一步局部尋優；否則，執行步驟(5)。

(5)判斷迭代最優解相同次數小于 Nm，則執行步驟(6)；否則，按照式(4)改變揮發系數的值，再執行步驟(6)。

(6)按照式(3)進行信息素的更新，檢查信息素的邊界，使其保持在[τmin，τmax]的范圍內。

(7)count++。如果 count＜Ncmax，清空禁忌表，返回步驟

(3)繼續向下執行；否則，結束循環，輸出結果。

4 仿真實驗

本文測試數據采用Taillard在1993年提出的基準測試問題，并將運行結果與其他參考文獻提出的算法進行比較，以此驗證提出的改進蟻群算法是有效的。

本文算法各參數設置如下：螞蟻個數 na=20，揮發系數 ρ=0.99，揮發系數最小值 ρmin=0.5，α=1.0，β=4.0，最大迭代次數為300，局部搜索次數為10。本文選取每種規模系列問題中的第一個問題進行計算，并與NEARCHOU A C[5]提出的算子遺傳算法(GA)、Lian Zhigang[7]提出的NPSO粒子群算法進行比較，每個算例連續運行20次，記錄其中的最優結果，如表1所示。其中，BS表示運行結果中的最優解，RPD(Relative Percentage Deviation)表示相對誤差百分率。由表1可知，相比其他兩種算法，本文提出的算法在求解Taillard系列問題方面能夠更好地收斂在最優解附近。

表1 改進蟻群算法的運行結果

本文針對解置換流水車間調度問題提出了一種改進的蟻群算法。在該算法中，采用NEH算法產生初始解，并利用自適應揮發系數的方法避免算法早熟，使分散搜索和集中搜索達到有效平衡，提高了算法的搜索能力。Taillard系列基準問題測試表明，本文的算法是有效的。

[1]高海兵，周馳.廣義粒子群優化模型[J].計算機學報，2005，28(12)：1980-1987.

[2]王凌.車間調度及其遺傳算法[M].北京：清華大學出版社，2003.

[3]李士勇.蟻群算法及其應用[M].哈爾濱：哈爾濱工業大學出版社，2004.

[4]吳啟迪，汪鐳.智能蟻群算法及其應用[M].上海：上海科技教育出版社，2004.

[5]NEARCHOU A C.The effect of various operators on the genetic search for large scheduling problems[J].International Journal of Production Economy，2004，88(1)：191-203.

[6]NAWAZ M，ENSCORE E，HAM I.A heuristic algorithm for the mmachine，n job flow shop[J].The International Journal of Management Sciences，1983，11(1)：91-95.

[7]Lian Zhigang，Gu Xingsheng，Jiao Bin.A Novel particle swarm optimization algorithm for permutation flow shop scheduling to minimize makespan[J].Chaos，Solitons and Fractals，2008，35(5)：851-861.