優化批處理機排序方案的啟發式算法研究

林烈青，鄭 睿

LIN Lie-qing1,ZHENG Rui2

（1. 廣東工業大學，廣州 511495；2. 上海市浦東新區改革與發展研究院，上海 200127）

0 引言

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

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

本文研究的屬于分批調度問題中的第四類family jobs，而且工件之間帶有鏈式先后關系約束，文獻[6]對該類問題進行了初步研究。總的來說，國內外對于這類批處理機排序方案的研究還不夠深入，用于求解排序方案的算法較為少見。為此，本文設計并驗證兩種批處理機排序方案的啟發式算法，以找出綜合效果更好的算法。

1 問題描述

本文中，排序方案的目標函數為最小化加權完工時間和，而且批量無限制，描述如下：

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

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

另外，工件之間存在著鏈式先后關系約束，存在若干組工件滿足以下形式的約束關系：

其中符號A→B表示工件B的加工只有在工件A完工以后才可以開始，因此，這里A稱為B的前驅工件，B稱為A的后續工件。并且設定這些約束關系鏈的最大長度為k。

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

2 排序方案的最優解性質

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

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

對于上面排序方案的最優解，有引理如下：

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

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

3 啟發式算法的設計與實現

文獻[6] 證明了此類排序方案是強NP-hard問題，所以不可能找到多項式時間的最優算法，在可接受的時間范圍內找到一個和最優解結果相差不大的排序方案即可，也就是在合理的時間內找到一個滿意解。

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

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

3.1 貪婪算法（Greedy Ratio,GR）

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

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

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

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

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

3.2 優選算法（BEST）

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

步驟2：從上一步得出的兩種方案中，選出目標函數值最優的一種組合，作為本算法的結果。

4 計算機仿真分析

4.1 實驗設計

為了檢驗以上算法的結果和效率，采用計算機仿真實驗的方法來對這些算法進行驗證。在本實驗中，所有算法均使用Visual Basic 6.0 編譯實現，計算機模擬實驗是在CPU為AMD Athlon XP 2000+，內存為1GB，操作系統為Windows XP 環境下進行。

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

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

對于每一個算例都會用本文提出啟發式算法和文獻[6]中的滿批算法來求解，并用分支定界算法求得每個算例的最優解。本實驗用分支定界算法求得的最優解作為標桿，檢驗啟發式算法求得的結果和最優解之間的比率。對每個隨機生成的算例，先用分支定界算法求得最優解，并計算該最優解的目標函數值。然后用上述的啟發式算法求得近似解，并計算這些近似解的目標函數值，最后用后者除以前者，得到一個比率。顯然這個比率是一個不小于1的數，而這個比率越接近1，就表示啟發式算法求得的解越接近最優解。

4.2 實驗結果分析

下列圖1～圖4分別表示了工件加工時間和權重的取值區間為[1,10]和[1,10]， [1,10]和[1,20]，[1,20]和[1,10]，[1,20]和[1,20]時算法結果和最優解比率的波動情況。其中橫坐標表示每種參數組合中實驗的序數，即表示這是第幾次的實驗結果，而縱坐標表示的是各算法結果與最優解的比率值。

圖1 啟發式算法結果與最優值的比率（p：[1,10],w：[1,10]）

圖2 啟發式算法結果與最優值的比率（p：[1,20],w：[1,10]）

圖3 啟發式算法結果與最優值的比率（p：[1,20],w：[1,20]）

圖4 啟發式算法結果與最優值的比率（p：[1,10],w：[1,20]）

實驗結果如表1和表2所示，表中的數據主要是啟發式算法求出目標函數值與分支定界算法求出的最優目標函數值之間的比率。例如FB表示滿批算法（FB）求出的解的目標函數值與分支定界算法求出的最優目標函數值之間的比率。

表1 啟發式算法結果與最優值的比率匯總（平均情況）

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

表2 啟發式算法結果與最優值的比率匯總（最差情況）

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

5 結論

工件帶有鏈式先后關系約束的family jobs類型的批處理機作業排序調度問題是一個非常復雜的問題，它屬于強NP-hard問題。本文分析了作業排序方案的目標函數為最小化加權完工時間和，并且得出了最優解的性質。根據最優解的性質設計了求解排序方案的兩種啟發式算法---貪婪算法和優選算法，通過計算機仿真實驗結果表明，優選算法比現有文獻的啟發式算法綜合效率更好，可作為實際應用中的首選。

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

[2] 馮大光,唐立新. 單臺批處理機總加權完成時間最小化的啟發式算法[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.