基于啟發(fā)式分支定界的單間作業(yè)車間優(yōu)化算法

銀 莉, 王 彬, 汪俊亮, 陳定方

(1 武漢理工大學智能制造與控制研究所， 湖北 武漢 430063； 2 浙江海洋學院船舶海洋工程系， 浙江 舟山 316000)

在離散制造系統(tǒng)中，調度問題種類繁多，其中單件車間調度問題(job-shop scheduling problem，JSP)是最基本、著名的調度問題，也說是NP難問題，不可能找到精確求得最優(yōu)解的多項式時間算法．求解(n/m/J/CMAX)問題，利用分支定界算法、人工智能方法、神經(jīng)網(wǎng)絡方法、遺傳算法等方法均有不同程度的調度效果[1]．本文根據(jù)JSP問題的調度特征，在考慮加工平衡和壓縮空閑時間的基礎上，并采用C#語言編寫程序，進行實驗驗證．

1 單間作業(yè)車間優(yōu)化調度的數(shù)學描述

借助線性不等式來表示調度約束關系，對job-shop調度問題定義如下[2]：

令N={0,1,2,3,…,n,n+1}表示工序的集合，其中n是工序總數(shù)，0和n+1分別表示起始和終止工序；M={0,1,2,3,…,m}表示機器的集合；A表示同一工件的前后關系約束的工序對集合，Ek表示機器K上加工的工序對集合．同時，根據(jù)加工實情，假設對于第i個作業(yè)在第j臺機器上的加工時間pij是一定的，其起始時間tij是優(yōu)化過程中有待確定的變量．且t0=0，p0=pn+1=0．

可以將job-shop調度問題描述如下．目標函數(shù)

MinF，

F表示完成作業(yè)的總時間，優(yōu)化的目的是加工總時間最短．

設定約束條件如下．

1)tik≥tij+pij(i=1,2,…，n)，

其中：tij表示第i個工件在第j臺機器上的開始加工時間；pij表示加工時間．該約束條件表示每個工件在機器上的加工次序．

2)引入變量

該約束保證每一個工序具有相對獨立的加工環(huán)境，在其結束加工之前，下一個加工工序不得提前插入．

3)F≥tij+pij(j=1,2…,n,j=1,2…,m).

該約束表示作業(yè)完成總時間必須大于或等于最后一件作業(yè)的開始時間與加工時間之和．

額外約束如下：1)所有零件都在0時刻到達；2)每個零件在加工流程中經(jīng)過每臺機器，且只經(jīng)過一次[3]．

2 搜索模型建立

在本問題中單件車間的加工問題歸根到底是一個排序問題，根據(jù)機器的工序建立分支樹模型(圖1)[4-5]．分支樹的子節(jié)點代表當前機器j的加工零件序列{i}，i∈(1,2…n)；第0層代表了起始工序表示所有工件都已按時到達；第j層代表了第j臺機器的所有工序排列方案．

圖 1 基于機器工序的分支樹模型

首先按照啟發(fā)函數(shù)的導向原則，根據(jù)計算結果分析出向下搜索最優(yōu)的路徑，得出較優(yōu)解．若無法得到可行的較優(yōu)解，則回溯一層，對剩余的一層進行搜索和求解．

通過對算法的分析不難得知，若搜索全局到最優(yōu)解，算法的時間復雜度為n!m，而若按照啟發(fā)函數(shù)引導搜索得到最優(yōu)解，則其時間復雜度為n!×m．可見，若能較早得到較優(yōu)的解，可以較快得到求解結果．

3 啟發(fā)函數(shù)確定

分支過程中的兩個重要因素：如何劃分問題(分支)和按何種策略選擇子問題進行擴展．而在本問題中設置合理的啟發(fā)函數(shù)對短發(fā)搜索方向進行引導，可以有效提高搜索效率(整數(shù)線性規(guī)劃的改進)[6]．

在確定啟發(fā)函數(shù)的過程中需要分析(n/m/J/CMAX)問題的作業(yè)流程．根據(jù)工程實踐，工件的加工順序往往是確定的，而每個工件的工藝路線也具有獨特性．

k為該工件目前已完成的工序．加工總時間

其加工進度定義為

(i=1,2,…，n,j、k=1,2,…，m)．

調度算法的目標函數(shù)MinF的本質，就是壓縮工序的等待時間，即選擇該工序之前加工時間最短和的工序進行加工．

綜上所述，選用下式作為啟發(fā)函數(shù)：

(i=1,2,…，n,j、k=1,2,…，m)．

4 算法設計

步驟二：判斷剩余集是否為空．若為空，判斷層次j是否等于m，若是取當前最優(yōu)解為最優(yōu)調度方案；若小于m，則將當前層次的調度方案存入Ej．若不為空，則取下一組方案進入步驟三．

步驟四：計算最優(yōu)解決方案的完工時間F，并輸出表示機器的加工工序對集合E．

5 調度實例

采用 Benchmark調度問題對算法進行驗證．

表1 8×4Benchmark調度問題

采用本算法對上述問題在C#環(huán)境下進行編程求解，執(zhí)行計算的硬件環(huán)境為Core(TM)I7-2630處理器、2GB內存，操作系統(tǒng)為Windows 7．算法的求解結果見圖2． 通過對比計算結果，可知本算法的最大完工時間為35，文獻[7]的結果(Makespan=39)相比具有優(yōu)勢．

圖 2 Benchmark調度問題求解甘特圖

上述研究結果證明了算法的可行性、高效性和實用性．本啟發(fā)式算法依靠啟發(fā)函數(shù)指引算法在層次結構中的搜索方向，采用深度優(yōu)先的搜索策略，減少了搜索量．測試證明，本算法在提高速度的同時依然具有較高的求解精度，能較快收斂得到最優(yōu)解．

6 結束語

然而，在實際的生產(chǎn)這種環(huán)境極為復雜，需要考慮的因素較多：如工序相關性、機器之間加工的通用性．雖然以上一些約束的增加使得算法在調度過程中體現(xiàn)出了生產(chǎn)系統(tǒng)的專用性，但是為了進一步完善不同加工情況下的算法，在今后的工作中可考慮以上約束和假設．

[參考文獻]

[1] 熊禾根，李建軍，孔建益,等. 考慮工序相關性的動態(tài)Job-shop調度問題啟發(fā)式算法[J].機械工程學報，2006,42(8):50-55.

[2] 范路橋,常會友,朱旭東. 一種改進的作業(yè)車間調度算法及其實現(xiàn)[J].計算機集成制造系統(tǒng),2005,11(5):673-677.

[3] Edward C. Sewell ,Jason J. Sauppe ,David R. Morrison ,Etc.A BB&R algorithm for minimizing total tardiness on a single machine with sequence dependent setup times[J].J Glob Optim,2012,54:791-812.

[4] Jose M. Framinan. An adaptive branch and bound approach for transforming job shops into flow shops[J].Computers & Industrial Engineering,2007,52:1-10.

[5] 王錫祿，姚偉力，馮恩民. Job-shop調度問題的優(yōu)化模型及算法[J].系統(tǒng)工程理論與實踐，2000(11):84-89.

[6] Christian Artigues, Michel Gendreau, Louis-Martin Rousseau,etc. Solving an integrated employee timetabling and job-shop scheduling problem viahybrid branch-and-bound[J], Computers & Operations Research,2009,36:2 330-2 340.

[7] 張曉東，嚴洪森. 一類job-shop車間生產(chǎn)計劃和調度的集成優(yōu)化[J],控制與決策，2003,18(5)：581-584.