基于啟發式分支定界的單間作業車間優化算法

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

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

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

1 單間作業車間優化調度的數學描述

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

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

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

MinF，

F表示完成作業的總時間，優化的目的是加工總時間最短．

設定約束條件如下．

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

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

2)引入變量

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

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

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

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

2 搜索模型建立

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

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

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

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

3 啟發函數確定

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

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

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

其加工進度定義為

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

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

綜上所述，選用下式作為啟發函數：

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

4 算法設計

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

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

5 調度實例

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

表1 8×4Benchmark調度問題

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

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

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

6 結束語

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

[參考文獻]

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

[2] 范路橋,常會友,朱旭東. 一種改進的作業車間調度算法及其實現[J].計算機集成制造系統,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調度問題的優化模型及算法[J].系統工程理論與實踐，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車間生產計劃和調度的集成優化[J],控制與決策，2003,18(5)：581-584.