林烈青，鄭 睿

LIN Lie-qing1,ZHENG Rui2

（1. 廣東工業(yè)大學(xué)，廣州 511495；2. 上海市浦東新區(qū)改革與發(fā)展研究院，上海 200127）

0 引言

根據(jù)工件加工類型的不同情況，目前文獻(xiàn)所研究的批處理機(jī)排序方案可分為以下四類：

第一類是只包含一種工件加工類型的批處理機(jī)排序方案[1,2]。第二類稱為compatible job families，是指工件包含多種加工類型，但是不同加工類型的工件可以放在同一個(gè)批次中一起加工，且每一類加工類型的工件所需加工時(shí)間相同[1,3]。第三類稱為incompatible job families，是指工件包含多種加工類型，只有同種加工類型的工件才能放在同一個(gè)批次加工，而且同種加工類型的工件所需的加工時(shí)間是相同的[4,5]。第四類稱為family jobs，是指工件包含多種加工類型，只有同種加工類型的工件才能放在同一個(gè)批次加工，但是同種加工類型的工件所需的加工時(shí)間是不相同的。因此每個(gè)批次的實(shí)際加工時(shí)間取決于該批次工件所需加工時(shí)間的最大者。

本文研究的屬于分批調(diào)度問題中的第四類family jobs，而且工件之間帶有鏈?zhǔn)较群箨P(guān)系約束，文獻(xiàn)[6]對(duì)該類問題進(jìn)行了初步研究。總的來說，國內(nèi)外對(duì)于這類批處理機(jī)排序方案的研究還不夠深入，用于求解排序方案的算法較為少見。為此，本文設(shè)計(jì)并驗(yàn)證兩種批處理機(jī)排序方案的啟發(fā)式算法，以找出綜合效果更好的算法。

1 問題描述

本文中，排序方案的目標(biāo)函數(shù)為最小化加權(quán)完工時(shí)間和，而且批量無限制，描述如下：

有n個(gè)工件要在同一臺(tái)機(jī)器中進(jìn)行加工。這些工件屬于m種不同的加工類型。每個(gè)工件記為Jij，其中下標(biāo)i表示該工件屬于第i種類型，下標(biāo)j表示該工件在第i種類型工件中的編號(hào)。第i種類型工件的數(shù)量記為ni，因此有ni＝n。每個(gè)工件所需要的加工時(shí)間記為pij，權(quán)重記為wij，i＝1，2，…，m，j＝1，2，…，ni。只有屬于同一種類型的工件才能被放入同一批次中，在機(jī)器中同時(shí)被加工。工件可以分成r個(gè)批次，分別記為B1，B2，…，Br。

每批的加工時(shí)間和權(quán)重分別記為P(Bl)和W(Bl)，l＝1，2，…，r。由于同一批的工件同時(shí)被加工,并且同時(shí)被釋放，所以同一批的工件具有相同的完成時(shí)間，同一批的工件的實(shí)際加工時(shí)間等于該批工件中所需加工時(shí)間最大者，即第l批的加工時(shí)間P(Bl)＝maxJij?Bl{pij}。而每批的權(quán)重等于該批所有工件的權(quán)重和，即

另外，工件之間存在著鏈?zhǔn)较群箨P(guān)系約束，存在若干組工件滿足以下形式的約束關(guān)系：

其中符號(hào)A→B表示工件B的加工只有在工件A完工以后才可以開始，因此，這里A稱為B的前驅(qū)工件，B稱為A的后續(xù)工件。并且設(shè)定這些約束關(guān)系鏈的最大長度為k。

記工件Jij的完工時(shí)間為Cij，如果工件Jij屬于生產(chǎn)中的第k個(gè)批次，該批次記為Bk，則工件的完工時(shí)間等于第k個(gè)批次的完成時(shí)間，即Cij＝本文中，問題的目標(biāo)函數(shù)為最小化加權(quán)完工時(shí)間和，就是在符合加工類型約和工件先后關(guān)系約束的情況下，把工件分批并確定批的加工順序,從而使得目標(biāo)函數(shù)加權(quán)完工時(shí)間和的值最小。用三參數(shù)方法表示即為

2 排序方案的最優(yōu)解性質(zhì)

在求解排序方案最優(yōu)解的算法之前，首先分析最優(yōu)解的性質(zhì)，可作如下定義：

定義1：在某個(gè)時(shí)刻t，如果一個(gè)工件Jij未被排序，而且該工件沒有前驅(qū)工件，或者在該時(shí)刻這個(gè)工件的所有前驅(qū)工件都已經(jīng)完工。那么稱該工件Jij為在時(shí)刻t可以被排序的工件，符合這種條件的工件組成的集合記為JP (t)，因此Jij?JP (t)。

對(duì)于上面排序方案的最優(yōu)解，有引理如下：

引理1：在本方案的最優(yōu)解中，如果某個(gè)批次Bt的加工開始時(shí)間是時(shí)刻t，而批次Bt中含有工件Jij。那么在此最優(yōu)解中，時(shí)刻t可以被排序的工件集合JP (t)中所包含的工件Jij同類型，且所需加工時(shí)間不大于工件pij的工件，都應(yīng)該在批次Bt中，即

該引理可用反證法證明成立，限于篇幅不再詳述。

3 啟發(fā)式算法的設(shè)計(jì)與實(shí)現(xiàn)

文獻(xiàn)[6] 證明了此類排序方案是強(qiáng)NP-hard問題，所以不可能找到多項(xiàng)式時(shí)間的最優(yōu)算法，在可接受的時(shí)間范圍內(nèi)找到一個(gè)和最優(yōu)解結(jié)果相差不大的排序方案即可，也就是在合理的時(shí)間內(nèi)找到一個(gè)滿意解。

文獻(xiàn)[6]給出了一種求解該問題的啟發(fā)式算法，即滿批算法（Full Batch，F(xiàn)B）。為了有更多的算法可供選擇，并尋求更高效率的算法，在這里提出兩種新的啟發(fā)式算法。

第一種啟發(fā)式算法稱為貪婪算法。其工作原理是把加工時(shí)間相近的工件放在同一批中，可以節(jié)省加工時(shí)間，提高工件加工的效率。根據(jù)引理1，如果在一個(gè)批次中加入了一個(gè)未排序的工件Jij，那么在該批次加工開始時(shí)間t可以被排序的所有所需加工時(shí)間不大于pij的屬于加工類型i的工件都應(yīng)該加入到這個(gè)批次中。所以在該算法中，在時(shí)刻t只允許生成包含在可排序工件集合JP (t)內(nèi)，同一類型工件SPT排列中具有從1開始的連續(xù)編號(hào)工件的批次。這里，把時(shí)刻t可能組成的可行的批次記為Bl(t)＝B (Ji1(t)，Jiv(t)) (l＝1，… ，K)，表示批次屬于i型批次，Ji1(t)表示批次的起始工件，即JP (t)內(nèi)i類型工件SPT排列中的第一個(gè)工件；Jiv(t)表示批次的末尾工件，即JP (t)內(nèi)i類型工件SPT排列中的第v個(gè)工件。也就是說一個(gè)可行的批次可以由末尾工件來確定。即B (Ji1(t)，Jiv(t))＝{Ji1(t)，Ji2(t)，… ，Ji,v-1(t)，Ji,v(t)}，其中i＝1,… ，m，v＝1,… ，ni。所以在本算法中每次總共最多會(huì)生成k≤n個(gè)不同的可行批次。貪婪算法流程如下：

3.1 貪婪算法（Greedy Ratio,GR）

步驟1：算法開始，當(dāng)前時(shí)刻記為t，當(dāng)前已排序方案記為S (t)，當(dāng)前已排序方案的最后一個(gè)批次的完工時(shí)間為t，此時(shí)t＝0，S (t)＝0/。

步驟2：記在當(dāng)前時(shí)刻t可以被排序的工件集合為JP (t)，如果該集合為空集，則直接跳到步驟4。否則，按照上述的規(guī)則生成當(dāng)前時(shí)刻t的所有的可行批次，即只包含具有在JP (t)內(nèi)同一類型工件SPT排列中從1開始的連續(xù)編號(hào)工件的批次，記為Bl(t)，l＝1，…，K。因此我們可以得到一個(gè)可行批次的集合Β＝{Bl(t) | l＝1，…，K}。

步驟3：從集合B中選擇一個(gè)具有最小的批次加工時(shí)間/權(quán)重比率，即P (Bl(t)) / W (Bl(t))的批次Bl(t)?B，把它安排進(jìn)入排序方案中，緊挨著已經(jīng)排定的批次之后進(jìn)行加工（如果前面沒有已排定的批次，則安排作為第一個(gè)批次），所包含的工件均已排序。另外，更新當(dāng)前時(shí)刻為t+P (Bl(t))，更新已排序方案為S (P (Bl(t)))＝S (t)∪Bl(t)，然后回到步驟 2。

步驟4：所有工件已排序，得到最終完整的排序方案，算法結(jié)束。

第二種啟發(fā)式算法稱為優(yōu)選算法（BEST）。這是一種混合算法（composite heuristic），整合了前面的兩種啟發(fā)式算法（文獻(xiàn)[6]中的滿批算法和上述的貪婪算法）。該算法的動(dòng)機(jī)在于，不同的啟發(fā)式算法在不同的環(huán)境中的表現(xiàn)各有優(yōu)劣，如果只單獨(dú)使用一種算法，可能會(huì)在某些情況下效果很差。但是如果聯(lián)合使用幾種算法，就能取長補(bǔ)短，達(dá)到優(yōu)選的效果。而且啟發(fā)式算法本身耗時(shí)很少，因此同時(shí)使用多種算法的總耗時(shí)也不會(huì)很多，所以利大于弊。因此本算法的基本思想就是每次對(duì)同樣的問題同時(shí)使用前面的兩種算法，并從中選取最好的排序方案，作為算法的排序方案。優(yōu)選算法流程如下：

3.2 優(yōu)選算法（BEST）

步驟1：應(yīng)用以上的兩種算法（滿批算法和貪婪算法）進(jìn)行求解，得出兩種排序方案。

步驟2：從上一步得出的兩種方案中，選出目標(biāo)函數(shù)值最優(yōu)的一種組合，作為本算法的結(jié)果。

4 計(jì)算機(jī)仿真分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

為了檢驗(yàn)以上算法的結(jié)果和效率，采用計(jì)算機(jī)仿真實(shí)驗(yàn)的方法來對(duì)這些算法進(jìn)行驗(yàn)證。在本實(shí)驗(yàn)中，所有算法均使用Visual Basic 6.0 編譯實(shí)現(xiàn)，計(jì)算機(jī)模擬實(shí)驗(yàn)是在CPU為AMD Athlon XP 2000+，內(nèi)存為1GB，操作系統(tǒng)為Windows XP 環(huán)境下進(jìn)行。

實(shí)驗(yàn)的流程分為三步，第一步是要隨機(jī)生成一些算例；第二步是用上述的算法來求解這些算例；第三步就是要把這些算法求解的結(jié)果進(jìn)行匯總和分析。算例涉及到的參數(shù)有以下幾個(gè)：工件個(gè)數(shù)n，工件類型數(shù)m，平行鏈長度k，工件所需加工時(shí)間pij和權(quán)重wij。在本實(shí)驗(yàn)中，工件數(shù)量n的取值是n＝20，工件類型數(shù)m的取值是m＝4。在實(shí)驗(yàn)中，采取服從一定分布下的數(shù)據(jù)隨機(jī)生成的辦法來生成每個(gè)算例的參數(shù)。其中，每個(gè)工件的加工類型i將服從區(qū)間為U [1,4]的均勻分布；而對(duì)于工件的加工時(shí)間pij和權(quán)重wij，為了能夠出現(xiàn)更多的不同的情況，在隨機(jī)生成工件數(shù)據(jù)的時(shí)候，采用方差較大的均勻分布。加工時(shí)間pij采用兩種情況的均勻分布U [1,10]和U [1,20]，分別代表了范圍較小和范圍較大的情況；工件權(quán)重wij采用了兩種情況的均勻分布U [1,10]和U [1,20]，也分別代表了范圍較小和范圍較大的情況（注：其中U [a,b]表示上限為b，下限為a的均勻分布）。因此，一共會(huì)有2×2＝4種不同的加工時(shí)間和權(quán)重的組合。每種組合隨機(jī)生成20個(gè)算例進(jìn)行計(jì)算，總共要計(jì)算4×20＝80個(gè)算例。

加工先后約束關(guān)系應(yīng)該是多條長度相等的平行鏈，取平行鏈的長度為4，即k＝4。所以對(duì)于20個(gè)工件的問題，應(yīng)該有5條平行鏈。在這5條平行鏈，就會(huì)有20個(gè)對(duì)應(yīng)的位置，記為PO (i)，i＝1，…，20。也就是說，這20個(gè)位置滿足這樣的先后關(guān)系約束：PO (l－1)×4＋1)→PO (l－1)×4＋2)→PO (l－1)×4＋3)→PO (l－1)×4＋4)，l＝1，…，5 。每個(gè)工件隨機(jī)生成一個(gè)0到1之間的數(shù)，稱為該工件對(duì)應(yīng)的隨機(jī)鍵，按每個(gè)工件對(duì)應(yīng)的這個(gè)隨機(jī)鍵的升序?qū)@些工件進(jìn)行排列，在這個(gè)排列中位于第1位的工件，則進(jìn)入位置PO (1)，在這個(gè)排列中位于第2位的工件，則進(jìn)入位置PO (2)，以此類推，這樣所有20個(gè)工件就會(huì)在平行鏈中有對(duì)應(yīng)的位置。這樣，就生成了每個(gè)算例中的工件的加工先后關(guān)系約束。

對(duì)于每一個(gè)算例都會(huì)用本文提出啟發(fā)式算法和文獻(xiàn)[6]中的滿批算法來求解，并用分支定界算法求得每個(gè)算例的最優(yōu)解。本實(shí)驗(yàn)用分支定界算法求得的最優(yōu)解作為標(biāo)桿，檢驗(yàn)啟發(fā)式算法求得的結(jié)果和最優(yōu)解之間的比率。對(duì)每個(gè)隨機(jī)生成的算例，先用分支定界算法求得最優(yōu)解，并計(jì)算該最優(yōu)解的目標(biāo)函數(shù)值。然后用上述的啟發(fā)式算法求得近似解，并計(jì)算這些近似解的目標(biāo)函數(shù)值，最后用后者除以前者，得到一個(gè)比率。顯然這個(gè)比率是一個(gè)不小于1的數(shù)，而這個(gè)比率越接近1，就表示啟發(fā)式算法求得的解越接近最優(yōu)解。

4.2 實(shí)驗(yàn)結(jié)果分析

下列圖1～圖4分別表示了工件加工時(shí)間和權(quán)重的取值區(qū)間為[1,10]和[1,10]， [1,10]和[1,20]，[1,20]和[1,10]，[1,20]和[1,20]時(shí)算法結(jié)果和最優(yōu)解比率的波動(dòng)情況。其中橫坐標(biāo)表示每種參數(shù)組合中實(shí)驗(yàn)的序數(shù)，即表示這是第幾次的實(shí)驗(yàn)結(jié)果，而縱坐標(biāo)表示的是各算法結(jié)果與最優(yōu)解的比率值。

圖1 啟發(fā)式算法結(jié)果與最優(yōu)值的比率（p：[1,10],w：[1,10]）

圖2 啟發(fā)式算法結(jié)果與最優(yōu)值的比率（p：[1,20],w：[1,10]）

圖3 啟發(fā)式算法結(jié)果與最優(yōu)值的比率（p：[1,20],w：[1,20]）

圖4 啟發(fā)式算法結(jié)果與最優(yōu)值的比率（p：[1,10],w：[1,20]）

實(shí)驗(yàn)結(jié)果如表1和表2所示，表中的數(shù)據(jù)主要是啟發(fā)式算法求出目標(biāo)函數(shù)值與分支定界算法求出的最優(yōu)目標(biāo)函數(shù)值之間的比率。例如FB表示滿批算法（FB）求出的解的目標(biāo)函數(shù)值與分支定界算法求出的最優(yōu)目標(biāo)函數(shù)值之間的比率。

表1 啟發(fā)式算法結(jié)果與最優(yōu)值的比率匯總（平均情況）

表1表示的是平均情況，即比率的平均值；而表2表示的則是比率值最差的情況，即比率的最大值。下面將分別從算法結(jié)果和算法耗時(shí)兩個(gè)角度來分析本實(shí)驗(yàn)的結(jié)果。

表2 啟發(fā)式算法結(jié)果與最優(yōu)值的比率匯總（最差情況）

從算法所得解的目標(biāo)函數(shù)值的比率來看，表1和表2的數(shù)據(jù)表明無論是平均情況還是最差情況，結(jié)果最好的都是優(yōu)選法（BEST），而且無論工件參數(shù)如何變化，優(yōu)選法的結(jié)果都非常穩(wěn)定。從耗時(shí)的角度來看，滿批算法和貪婪算法的耗時(shí)都非常小，均不超過0.1秒，優(yōu)選法的耗時(shí)為兩者之和，也幾乎可以忽略不計(jì)。因此，優(yōu)選法的綜合效率最高。

5 結(jié)論

工件帶有鏈?zhǔn)较群箨P(guān)系約束的family jobs類型的批處理機(jī)作業(yè)排序調(diào)度問題是一個(gè)非常復(fù)雜的問題，它屬于強(qiáng)NP-hard問題。本文分析了作業(yè)排序方案的目標(biāo)函數(shù)為最小化加權(quán)完工時(shí)間和，并且得出了最優(yōu)解的性質(zhì)。根據(jù)最優(yōu)解的性質(zhì)設(shè)計(jì)了求解排序方案的兩種啟發(fā)式算法---貪婪算法和優(yōu)選算法，通過計(jì)算機(jī)仿真實(shí)驗(yàn)結(jié)果表明，優(yōu)選算法比現(xiàn)有文獻(xiàn)的啟發(fā)式算法綜合效率更好，可作為實(shí)際應(yīng)用中的首選。

[1] Brucker P,Gladky A,Hoogeveen H,et al. Scheduling a batching machine[J]. Journal of Scheduling,1998,1：31-54.

[2] 馮大光,唐立新. 單臺(tái)批處理機(jī)總加權(quán)完成時(shí)間最小化的啟發(fā)式算法[J].控制與決策,2006,21 (11)： 1293-1297.

[3] Chandru V,Lee C and Uzsoy R. Minimizing total completion time on a batch processing machine with job families [J]. Operations Research Letters,1993,13： 61-65.

[4] Uzsoy R. Scheduling batch processing machines with incompatible job families [J]. International Journal of Production Research,1995,33： 2685-2708.

[5] Jolai F. Minimizing number of tardy jobs on a batch processing machine with incompatible job families [J]. European Journal of Operational Research,2005,162：184-190.

[6] Zheng R,Li H.Y. Minimizing total weighted completion time on a batch-processing machine with re-entrance[C].Proceedings of the IEEE International Conference on Automation and Logistics,Shenyang,China,August 2009：1791-1794.