Job—shop調度求解的廣義蟻群算法

張宏國　宮雪

摘要：針對蟻群算法求解Job-shop調度問題，該算法考慮到利用析取圖來描述工件加工關系給算法帶來的復雜度，提出了一種廣義蟻群算法。在綜合考慮設備和工序關系約束的前提下，將信息素更新機制運用到求解Job-shop調度問題中，從而提高解的質量。為了提高搜索效率，根據蟻群算法的狀態轉移規則，對算法中參數的選擇進行了詳細的研究，設計了信息素更新策略。仿真實驗結果表明，廣義蟻群算法得到的解更接近最優解，該算法的收斂速度明顯高于其他算法的收斂速度。

關鍵詞：Job-shop調度問題；廣義蟻群算法；信息素更新機制

中圖分類號：TP391 文獻標志碼：A 文章編號：1007-2683（2017）01-0091-05

0 引言

現代制造業的市場競爭日益激烈，生產調度是現代制造業面臨的重要問題，它的解決有利于提高企業的生產效率與經濟。Job-shop調度問題（Job-shop scheduling problem，JSP）是生產調度中最基本的組合優化問題，在滿足工藝路線、交貨期與資源利用等約束條件下，合理安排工藝加工時間、先后順序及使用資源，可以減小生產周期，減少庫存，獲得產品時間或成本的優化。因此Job-shop調度問題的優化求解具有重要的理論價值和實際意義，是學術界與工程界共同關注的熱點。

目前求解Job-shop調度問題的主要方法是建立智能優化算法，以禁忌搜索、模擬退火、遺傳算法為代表。蟻群算法具有正反饋、較強的魯棒性、全局性、普遍性、優良的分布式并行計算機機制，易于與其他方法相結合等諸多優點。近年來，很多學者將蟻群算法逐漸地應用于Job-shop調度求解中。文提出了一種自適應蟻群算法（AACA），自適應地初始化信息素并限定其大小范圍以得到優解。文提出了最大最小蟻群算法，對信息素進行限制防止算法陷入局部最優。文提出了混合算法，將蟻群算法和遺傳算法相結合的ACSGA算法，充分利用它們的特性。

但上述文獻都是采用傳統蟻群算法中析取圖的方式對工件加工關系進行描述的。雖然析取圖是用來描述路徑關系比較好的視圖形式，但是車間生產中各工件之間的加工關系不同于旅行商問題（TSP）中的路徑選擇。特別是對于加工規模較大的Job-shop調度問題，每增加一個機器，析取圖就會增加條邊，則形成的析取圖結構會十分復雜，使得算法的復雜度增加，收斂速度變慢，影響解的質量。

本文提出一種廣義蟻群算法，將其用于Job-shop調度求解中。該算法利用一次調度就是螞蟻的一次爬行的思想，擺脫傳統的析取圖方式，把信息素更新機制應用到Job-shop調度問題中，這樣能有效的簡化算法復雜度，提高算法的收斂速度，優化解的質量。將信息素機制合理的應用在每一道工序上，在滿足約束條件和解的合法性的前提下，越早完成加工的工序和同一工件優先進行加工的工序上殘留的信息素濃度越高。

1 Job-shop調度問題分析

1.1 問題描述

n個工件在m臺機器上加工，每個工件有m道工序，加工時間已知，要求總完工時間最小。針對Job-shop調度問題的具體約束條件如下：

1）同一時刻同一臺機器只能加工一個工序；

2）前一道工序加工完畢后才能加工下一道工序；

3）每個工序在可用機器上的加工時間不同且已經確定；

4）允許工件在工序間等待，也允許機器在工件未到達前閑置；

5）工序一旦開始，不允許中斷。

1.2 問題建模

關于Job-shop調度問題，作如下定義：1）n：工件數目；

2）m：機器數目；

3）工件集J={J₁，J₂，…，J_n}，1≤i≤n；

4）機器集M={M₁，M₂，…，M_m}，1≤k≤m；

5）工序集O_i={O_i，1，O_i，2，…，O_i，m}，其中O_i，j表示工件i的第j道工序；

6）M_i，j表示O_i，j占用的機器，M_i，j∈M；

7）T_i，j表示第i個工件第j道工序的加工時間；

8）S_i，j表示第i個工件第j道工序的開始時間；

9）C_i，j表示第i個工件第j道工序的完工時間，C_i，j=S_i，j+T_i，j。

因為工件完工要求所有工序加工完畢，并且每道工序開始加工時，它的緊前工序必須加工完畢，所以工件加工完畢的時間為各設備完工的最大時間值。因此在給定約束條件的前提下，調度的最短時間值是所求的結果，其數學描述為：

（1）

（2）

（3）

在上面式子中，式（1）表示目標函數，調度的整體完工時間最短。式（2）表示對于同一工件i來說，工序j+1的開始加工時間，一定會大于其緊前工序j的開始加工時間與連續加工時間之和。式（3）表示對于同一設備來說，同一設備在同一時刻只能加工一道工序。

2 Job-shop調度求解的廣義蟻群算法

2.1 廣義蟻群算法的總體思想

蟻群算法是一種基于反饋機制和并行機制的模擬進化算法，在大規模的調度問題中有其固有的優勢，但也容易出現搜索時間過長導致局部優解。傳統的蟻群算法用析取圖來求解JSP問題，析取圖被描述為一個有向圖，更直觀的展現便于分析。但對于規模大的JSP問題會加劇蟻群算法的缺陷，因需要優化的問題規模變大，那么得到相應的解就會增加迭代次數，增加了相應的計算時問，進而影響解的質量和算法的收斂速度。

廣義蟻群算法利用每一次的調度需要螞蟻爬行一次的思想，尋找的最優路徑就是螞蟻爬行所走的最短路徑。運用廣義蟻群算法求解時，一只螞蟻從一個工件的第一道工序開始爬行，根據轉移狀態規則對可調度的工序進行選擇。將選擇的工序標記為已操作工序，計算概率繼續選擇接下來要調度的工序，直到每臺機器未調度的工序集為空為止，即完成一次調度。

每次調度之后更新信息素，信息素的改變直接影響工序轉移概率的計算結果，因此信息素的更新要與工序的優先級緊密聯系。針對蟻群算法的特點，對信息素更新機制進行改進，以便更快找到工序在各機器上加工的一組優先序列。

2.2 信息素更新機制

1）狀態轉移規則

螞蟻根據信息素的濃度和工序問的啟發式信息，在其可選尚未調度的集合中選擇接下來的目標工序。選擇工序的時候需要判斷各工序在機器上的加工概率，狀態轉移概率公式如下：

（4）從式（4）可看出，狀態轉移概率主要根據t時刻工序i轉移到工序j上的信息素濃度τ_ij（t）以及工序i到工序j的啟發式信息η_ij（t）。其中，α和β是兩個參數，分別表示信息素的影響力和啟發式信息的相對重要性，AS表示可選尚未調度的集合。

2）信息素計算公式

在求解Job-shop調度問題時，螞蟻在遍歷過程中留下信息素，路徑上的信息素濃度隨著螞蟻每次遍歷進行更新。信息素濃度的強弱引導著后面的螞蟻對工序的選擇，某個路徑上螞蟻遍歷的次數越多，信息素濃度越大，后來者選擇該路徑遍歷的概率就越大。當螞蟻所走的路徑越短即調度結果越優時，該路徑的信息素濃度越大。

信息素更新機制是工件加工排序中的重中之重，因此本文對信息素的更新公式進行優化，會著重突出信息素的作用和影響，削弱啟發式信息的重要性。信息素濃度的變化受工序節點開始時間以及局部目標函數完成時間的影響，根據這一原則區分工序的優先級，優先安排信息素濃度大的工序。

在一次遍歷工序中，螞蟻遍歷工序的完成時間越早，信息素濃度越大。其次，開始時間越早的工序，信息素濃度越大，越優先安排。在傳統的信息素公式中，由于開始時間和完成時間都與信息素的大小有直接影響，所以在信息素濃度相同的情況下，確定不了工序的優先順序。因此對計算信息素濃度的公式加以完善，這樣會更快得到較優的加工序列。計算信息素的公式如下：

（5）

通過式（5）對信息素濃度的賦值，保證了越早完成加工的工件對應的工序上信息素濃度越大，并且同一工件的前道工序獲得的信息素濃度比后道工序獲得的信息素濃度大。

3）公式參數的分析

為了避免信息素過小而影響解的計算，故在式（5）的分母上加上系數γ以保證解的合理性公式，γ為信息素放大系數，取經驗值γ=∑T_ij。同時為了保證工序的選擇不會因為開始時間而淹沒完工時間的影響，故在式（5）的分子中的完成時間上乘上一個常數z，適當擴大完工時間對信息素的影響，z為調整信息素濃度系數，z取經驗值。在算法的具體實行時通常取z=n，這樣通過對公式參數的設置更有效的保證了對調度周期的優化。

4）信息素更新方式

螞蟻完成一次調度后，更新當前路徑上的各工序信息素濃度，更新方式如下：

（6）

（7）式（6）中，△τ^k_ij（t，t+1）表示第k只螞蟻在（t，t+1）時刻從工序i移動到工序j這一過程的信息素增量。式（7）表示信息素的更新方式，其中ρ表示信息素揮發系數，信息素會隨著時間不斷揮發，ρ∈（0，1）。

2.3 算法步驟

符號表示：AS為可調度的工序集合，CS為完成調度的工序集合，GS為未調度的工序集合，IS為正在調度的工序集合。

步驟1：初始化AS={O_i1|i=1…n}，CS=φ，GS={O_ij|i=1…n，j=1…m}，IS=φ。

步驟2：初始化螞蟻數目n，參數α，β，ρ，機器M_ij的可用時刻為MT_mij以及當前時刻ST_ij。

步驟3：當調度解多次不再優化時，算法停止，輸出結果。否則重置并轉到步驟1。

步驟4：一共有k=1～n只螞蟻，當初始時刻t=0時，分別放在各工件的第一道工序O_，1上，更新當前時刻ST_ij=ST_k，1，各機器可用時刻MT_mij=T_k，1，更新集合AS=AS-{O_k，1}，GS=GS-{O_k，1}，IS=IS+{O_k，1}。

步驟5：對于m個機器，如果機器可用時刻MT_mij≤T_k，1，則機器空閑，進行下一個工序的選擇。如果AS中只有一個可調度工序，則直接將此工序放人IS；如果存在多個可調度工序，根據式（7）計算轉移概率，按輪盤賭的方式選擇接下來要加工的工序O_ij；如果不存在直接跳過，轉步驟7。

步驟6：當螞蟻移動到所選工序O_ij時，AS=AS-{O_ij}，GS=GS-{O_ij}，IS=IS+{O_ij}。O_ij完成調度之后，CS=CS+{O_ij}，當前時刻ST_ij=ST_k，1+T_ij，將接下來要調度的工序O_i，j+1放入AS中。

步驟7：判斷GS是否為空。如果GS=φ，說明螞蟻遍歷所有工序，完成了一次調度，執行步驟8；否則，轉步驟4。

步驟8：螞蟻完成一次調度后，記下調度序列，對該螞蟻當前路徑各工序信息素濃度進行更新。

步驟9：比較前后兩只螞蟻爬行所用的完成時間，選擇完成時間短的。每次調度后都選出較優的調度序列，對目標函數值進行更新并記錄調度序列。

步驟10：直到所有螞蟻都完成尋優，得到最優的完工時間及調度序列。

3 仿真實驗

3.1 實例驗證

根據上述理論，針對所描述的廣義蟻群算法進行模擬仿真實驗，并做出分析與評價，驗證算法的可行性。應用實例是6個待加工工件（J₁，J₂，…，J₆）在6臺機器（M₁，M₂，…，M₆）上加工的典型Job-shop調度問題。

1）參數確定：α=2，β=3，ρ=0.5；

2）實例中加工機器對應的加工工序如表1所示，加工時間如表2所示。

表2的加工時間與表1中的加工工序對應著，根據廣義蟻群算法得到最優調度序列，用6行6列的S矩陣表示。矩陣的每一行代表一個加工機器，矩陣的每一列表示工序的由開始到最后的加工順序。例如一行一列的（1，2）代表在M₁上首先加工的是O₁₂，第二行第二列的（4.1）代表在M₂上第二個加工的是O₄₁，依此類推。

為了更直觀的看出機器的加工狀態，根據S矩陣繪制甘特圖如圖1所示。圖中每個實線方塊代表一個加工工序O_ij，方塊的長度代表此工序在此臺機器上的加工時間，方塊外的空白之處代表機器的空閑時間。從甘特圖可看出完成時間是55，也是已知的最優解，該算例證明了廣義蟻群算法的可行性和有效性。

3.2 算法評價

用廣義蟻群算法求解Job-shop調度問題的5個經典算例，采用Matlab軟件進行編程仿真。仿真結果與其他算法得到的結果進行對比，其他算法的結果由文獻給出，如表3所示。由表可知，與遺傳算法、傳統蟻群算法相比，廣義蟻群算法的結果更接近最優解，可見達到了優化的目的。

收斂曲線對比：圖2中縱坐標表示目標函數值，橫坐標表示循環次數，黑色曲線是本文提出的廣義蟻群算法的收斂曲線，紅色曲線是基本蟻群算法的收斂曲線，藍色曲線是遺傳算法的收斂曲線。從圖中可以看出本文的算法更優，不僅收斂的速度快而且得到的目標函數值更貼近最優解。

4 結論

根據蟻群算法求解Job-shop調度問題，考慮到用析取圖求解規模較大的調度問題時會非常復雜，而且缺少對蟻群算法并行特性的體現。本文從算法的調度方式、信息素的更新機制方面進行改進，提出了廣義蟻群算法。通過應用實例進行試驗，檢驗了該算法對實際問題的有效性，與傳統蟻群算法，遺傳算法進行對比，結果表明本文提出的廣義蟻群算法獲得的解更接近最優解，而且算法的收斂速度更快，這說明本文求解Job-shop調度問題的方法更有效。

（編輯：關毅）