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

張宏國　宮雪

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1007-2683（2017）01-0091-05

0 引言

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

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

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

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

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

1.1 問題描述

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

1）同一時(shí)刻同一臺(tái)機(jī)器只能加工一個(gè)工序；

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

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

4）允許工件在工序間等待，也允許機(jī)器在工件未到達(dá)前閑置；

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

1.2 問題建模

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

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

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

4）機(jī)器集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占用的機(jī)器，M_i，j∈M；

7）T_i，j表示第i個(gè)工件第j道工序的加工時(shí)間；

8）S_i，j表示第i個(gè)工件第j道工序的開始時(shí)間；

9）C_i，j表示第i個(gè)工件第j道工序的完工時(shí)間，C_i，j=S_i，j+T_i，j。

因?yàn)楣ぜ旯ひ笏泄ば蚣庸ね戤?，并且每道工序開始加工時(shí)，它的緊前工序必須加工完畢，所以工件加工完畢的時(shí)間為各設(shè)備完工的最大時(shí)間值。因此在給定約束條件的前提下，調(diào)度的最短時(shí)間值是所求的結(jié)果，其數(shù)學(xué)描述為：

（1）

（2）

（3）

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

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

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

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

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

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

2.2 信息素更新機(jī)制

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

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

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

2）信息素計(jì)算公式

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

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

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

（5）

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

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

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

4）信息素更新方式

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

（6）

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

2.3 算法步驟

符號(hào)表示：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ù)α，β，ρ，機(jī)器M_ij的可用時(shí)刻為MT_mij以及當(dāng)前時(shí)刻ST_ij。

步驟3：當(dāng)調(diào)度解多次不再優(yōu)化時(shí)，算法停止，輸出結(jié)果。否則重置并轉(zhuǎn)到步驟1。

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

3.1 實(shí)例驗(yàn)證

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

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

2）實(shí)例中加工機(jī)器對(duì)應(yīng)的加工工序如表1所示，加工時(shí)間如表2所示。

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

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

3.2 算法評(píng)價(jià)

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

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

4 結(jié)論

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

（編輯：關(guān)毅）