求解作業車間調度問題的改進蟻群算法

馬 軍，李 薇

(1.安徽財經大學 國際經濟貿易學院，安徽 蚌埠 233041；2.安徽財經大學 商務學院，安徽 蚌埠 233030）

0 引言

作業車間調度問題(Job Shop Scheduling Problem，JSSP)是用m臺機器(資源)來加工n個工件(任務)，并且每個工件又由k個工序組成，每個工序要按照一定的順序來完成[1]。JSSP的調度目標是在滿足各工序加工順序約束條件下，確定每臺機器上各工序的加工順序及加工開始時間，并使某個性能指標最優，如制造周期最短[2]。作業車間調度問題是一類典型的復雜生產調度問題，具有約束松弛度緊、NP-Hard等特性[3]。近年來，各國嘗試采用不同方法來求解作業車間調度問題，例如：遺傳算法 (genetic algorithm)[4～6]、禁忌搜索(taboo search)[7,8]、蟻群算法 (ant colony optimization)[9,10]、演化算法(evolutionary algorithm)[11,12]以及模擬退火(simulated annealing)[13,14]等。各國學者通常使用各種混合方法來求解作業車間調度問題：(1)將現有方法進行一定程度地改進[15～17]；(2)將一些啟發式規則集成到已有方法中[18～20]；(3)多種現有方法 的 混 合 集 成[7～9]。 在 求解復雜JSSP的過程中，JSSP的領域知識及專家的經驗知識等對于最終的求解質量和求解效率都起著至關重要的作用。因此，考慮將領域知識和經驗知識集成到蟻群算法中的嘗試，具有重要的理論意義和實踐意義。鑒于此，本文擬提出一種求解作業車間調度問題的改進蟻群算法。該方法將調度知識有效地融入到蟻群算法中，以期使其優化效率得到極大地改進。

1 改進蟻群算法

為了有效地求解JSSP，本文提出了一種改進蟻群算法。該方法將調度知識有效地融入到蟻群算法中，使得優化效率得到極大地改進。該方法的計算流程如圖1所示。

1.1 調度知識表達

圖2 調度知識的表達形式

本文將JSSP的領域知識及專家的經驗知識等統稱為調度知識。為了方便地實現優化過程中調度知識的挖掘、存儲和應用，筆者采用圖2所示的形式完成對調度知識表達。

工序處理優先等級的賦值有兩種情況：(1)概率形式，表示給定屬性的工序在某優先等級下加工的概率；(2)打分形式，表示給定屬性的工序在某優先等級下加工的次數。為了便于后續的處理，筆者采用打分形式對工序處理優先等級進行賦值。圖2中調度知識的含義如下 (采用打分形式，第2條調度知識的含義)：

如果

(工序x的工序加工順序屬性=α21)∧

(工序x的處理時間屬性=α22)∧

(加工工序x的機器負荷屬性=α23)∧

(工序x后續工序累計處理時間屬性=α24)∧

則

(工序x以優先等級1加工的次數為 β21)∧

(工序x以優先等級2加工的次數為 β22)∧

(……)∧

(工序x以優先等級m加工的次數為β2m)。

1.2 狀態轉移規則

在描述狀態轉移規則之前，先定義工序的選擇概率。在這里，筆者定義了兩種工序選擇概率：基于工序處理時間的工序選擇概率和基于調度知識的工序選擇概率。

所謂的妊娠合并糖尿病指的是:妊娠期間發現或發病的由不同程度糖耐量異常及糖尿病引起的不同程度的高血糖,其中有些患者在妊娠前便已經被診斷出患有糖尿病,在妊娠之后則有持續性加重的表現等[1-2]。為了研究妊娠與糖尿病的關系,從而提升臨床治療效果,本文在2015年12月-2016年12月間婦產科收治的80例妊娠合并糖尿病患者參與研究,探究其臨床護理效果,具體研究內容闡述如下:

(1)基于工序處理時間的工序選擇概率。在t次迭代時，螞蟻k選擇工序j的概率公式為：

這里，allowedk表示螞蟻k在當前位置(當前時刻的特定機器)上可處理工序的集合；τj(t)表示t時刻工序j上的信息素水平；ηj=1/tj表示工序加工時間的倒數；a,b分別表示工序j的信息素啟發值和加工時間啟發值的權重。

(2)基于調度知識的工序選擇概率。在t次迭代時，螞蟻k選擇工序j的概率公式為：

這里，γj表示根據當前的調度知識，處理工序j的優先等級的綜合評估值；a,b分別表示工序j的信息素啟發值和調度知識啟發值的權重；βji表示工序 j的第i個處理優先等級的取值；wi表示第i個處理優先等級的權重。

表1 本文的5種不同的實驗方案

表2 本文用到的14個測試實例

表3 本文蟻群算法中的參數設置

本文的狀態轉移規則如下：在t次迭代時，螞蟻k依據以下狀態轉移規則來選擇下一個需要處理的工序

這里的q為[0,1]范圍內服從均勻分布的一個隨機數；q0是一個設計參數，q0=lg(Gen)/lg(Max_Gen)；Gen表示當前的迭代次數，Max_Gen表示用戶設定的最大迭代次數。

1.3 信息素局部更新規則

這里的h表示在第t次迭代的最優可行方案中，工序j在給定機器上的加工次序；H表示所有任務的最大工序數。

1.4 信息素全局更新規則

在蟻群算法中，信息素全局更新規則僅用于更新當前最優可行方案的信息素水平。

這里的hh表示在當前最優可行方案中，工序j在給定機器上的加工次序；HH表示所有任務的最大工序數。

1.5 信息素衰退規則

本文將每個工序上的信息素都控制在范圍[τmin,τmax]內。

這里ρ(0＜ρ＜1)表示信息素衰減因子。

1.6 調度知識的挖掘

為了有效地挖掘、存儲和應用調度知識，筆者對每個工序屬性指標都進行了離散化操作。根據不同的優化需求，每個工序屬性指標都被劃分為若干個不同的水平(將每個工序屬性指標的取值范圍分割成若干個區間)。同時，本文采用多維數組來記錄和存儲調度知識(圖3)。調度知識挖掘的計算流程如圖4所示。

2 仿真實例

表4 采用5種實驗方案求解14個測試實例的優化誤差

為了驗證本文方法的有效性，筆者設計了5種不同的實驗方案(表1)。表1中調度知識 i(1≤i≤4)的含義是：在該調度知識中，工序屬性指標被分為i+1個水平，工序處理優先級被分為2(i+1)個等級。在對經驗知識進行綜合評估時，工序處理優先等級的權重wi=5(mi+1)，1≤i≤m，這里的m表示工序優先處理等級的數目。筆者采用14個典型實例(表2)來驗證各種實驗方案，改進蟻群算法的參數設置見表3。

表4和表5列舉了本文的試驗結果。從表4中可以看出，調度知識表述的越詳細，平均優化誤差越小。這表明：將調度知識融入到蟻群算法中，可以有效提高蟻群算法的優化績效。從表5中可以看出，無論是優化時間還是優化結果，本文提出的改進蟻群算法都要優于現有的標準蟻群算法。

表5 采用5種實驗方案求解14個測試實例的優化時間

3 結束語

本文的主要創新點是：采用一種改進蟻群算法來求解作業車間調度問題。通過將調度知識有效地融入到蟻群算法中，使得改進蟻群算法在優化效率上大大改進。

[1]Tavakkoli-Moghaddam R.,Daneshmand-Mehr M.A Computer Simulation Model for Job Shop Scheduling Problems Minimizing Makespan[J].Computers&Industrial Engineering,2005,48.

[2]王秀宏,喬清理,王正歐.Job-shop調度問題的瞬態混沌神經網絡解法[J].系統工程,2001,19(3).

[3]Watanabe M.,Ida K.,Gen M.A Genetic Algorithm with Modified Crossover Operator and Search Area Adaptation for the Jobshop Scheduling Problem[J].Computers&Industrial Engineering,2005,48.

[4]Goncalves J.F.,De Magalhaes Mendes J.J.,Resende Gcm.A Hy-brid Genetic Algorithm for the Job Shop Scheduling Problem[J].European Journal of Operational Research,2005,167.

[5]楊曉梅,曾建潮.采用多個體交叉的遺傳算法求解作業車間問題[J].計算機集成制造系統,2004,10(9).

[6]姜思杰,徐曉飛,李全龍.基于遺傳優化算法求解作業車間調度問題[J].計算機集成制造系統,2002,8(3).

[7]Pezzella F.,Merelli E.A Tabu Search Method Guided by Shifting Bottleneck for the Job Shop Scheduling Problem[J].European Journal of Operational Research,2000,120.

[8]梁旭,黃明.禁忌-并行遺傳算法在作業車間調度中的應用[J].計算機集成制造系統,2005,11(5).

[9]Huang K.L.,Liao C.J.Ant Colony Optimization Combined with Taboo Search for the Job Shop Scheduling Problem[J].Computers&Operations Research,2008，35（4）.

[10]王常青,操云甫,戴國忠.用雙向收斂蟻群算法解作業車間調度問題[J].計算機集成制造系統,2005,10(7).

[11]Tanev I.T.,Uozumi T.,Morotome Y.Hybrid Evolutionary Algorithm-Based Real-World Flexible Job Shop Scheduling Problem:Application Service Provider Approach[J].Applied Soft Computing,2004,(5).

[12]何霆,劉文煌,梁力平.基于進化算法的一類作業車間調度[J].計算機集成制造系統,2001,7(1).

[13]KoLonko M.Some New Results on Simulated Annealing Applied to the Job Shop Scheduling Problem[J].European Journal of Operational Research,1999,113.

[14]吳大為,陸濤棟,劉曉冰.求解作業車間調度問題的并行模擬退火算法[J].計算機集成制造系統,2005,11(6).

[15]張超勇,饒運清,李培根.求解作業車間調度問題的一種改進遺傳算法[J].計算機集成制造系統,2004,10(8).

[16]馮奇峰,李言.運用帶有記憶庫的遺傳算法求解作業車間調度問題[J].計算機集成制造系統,2005,11(8).

[17]范路橋,常會友,朱旭東.一種改進的作業車間調度算法及其實現[J].計算機集成制造系統,2005,11(5).

[18]Lee D.S.,Vassiliadis V.S.,Park J.M.A Novel Threshold Accepting Meta-Heuristic for the Job-Shop Scheduling Problem[J].Computers&Operations Research,2004,(31).

[19]代勇,付宜利,馬玉林.與啟發式規則相結合的遺傳算法在車間調度問題中的研究[J].現代制造工程,2003,(3).

[20]呂文彥,黨延忠.基于綜合規則與遺傳算法的可重入生產系統調度[J].計算機工程,2005,31(13).