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

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

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

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

借助線性不等式來表示調(diào)度約束關(guān)系，對job-shop調(diào)度問題定義如下[2]：

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

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

MinF，

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

設(shè)定約束條件如下．

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

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

2)引入變量

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

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

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

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

2 搜索模型建立

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

圖 1 基于機(jī)器工序的分支樹模型

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

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

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

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

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

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

其加工進(jìn)度定義為

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

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

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

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

4 算法設(shè)計(jì)

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

步驟四：計(jì)算最優(yōu)解決方案的完工時(shí)間F，并輸出表示機(jī)器的加工工序?qū)螮．

5 調(diào)度實(shí)例

采用 Benchmark調(diào)度問題對算法進(jìn)行驗(yàn)證．

表1 8×4Benchmark調(diào)度問題

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

圖 2 Benchmark調(diào)度問題求解甘特圖

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

6 結(jié)束語

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

[參考文獻(xiàn)]

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

[2] 范路橋,常會友,朱旭東. 一種改進(jìn)的作業(yè)車間調(diào)度算法及其實(shí)現(xiàn)[J].計(jì)算機(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調(diào)度問題的優(yōu)化模型及算法[J].系統(tǒng)工程理論與實(shí)踐，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] 張曉東，嚴(yán)洪森. 一類job-shop車間生產(chǎn)計(jì)劃和調(diào)度的集成優(yōu)化[J],控制與決策，2003,18(5)：581-584.