張宏國　宮雪

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

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

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

0 引言

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

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

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

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

1 Job-shop調(diào)度問題分析

1.1 問題描述

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

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

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

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

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

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

1.2 問題建模

關于Job-shop調(diào)度問題，作如下定義：1）n：工件數(shù)目；

2）m：機器數(shù)目；

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。

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

（1）

（2）

（3）

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

2 Job-shop調(diào)度求解的廣義蟻群算法

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

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

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

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

2.2 信息素更新機制

1）狀態(tài)轉移規(guī)則

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

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

2）信息素計算公式

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

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

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

（5）

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

3）公式參數(shù)的分析

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

4）信息素更新方式

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

（6）

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

2.3 算法步驟

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

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

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

步驟3：當調(diào)度解多次不再優(yōu)化時，算法停止，輸出結果。否則重置并轉到步驟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中只有一個可調(diào)度工序，則直接將此工序放人IS；如果存在多個可調(diào)度工序，根據(jù)式（7）計算轉移概率，按輪盤賭的方式選擇接下來要加工的工序O_ij；如果不存在直接跳過，轉步驟7。

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

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

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

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

步驟10：直到所有螞蟻都完成尋優(yōu)，得到最優(yōu)的完工時間及調(diào)度序列。

3 仿真實驗

3.1 實例驗證

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

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

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

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

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

3.2 算法評價

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

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

4 結論

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

（編輯：關毅）