單機不相容雙目標最優批排序研究

李小襯

（武漢生物工程學院計算機與信息工程系，湖北 武漢430415）

2個代理在同一臺機器上加工，每個代理都有各自的目標，即顧客的任務不同，就會有不同的目標，總目標是盡可能使每個顧客滿意。

平行分批不相容排序是指把任務分成幾個子集，每個子集作為一批，不相容的任務不能放在同一批中加工，每批的完工時間就是這批中最后一個任務的完工時間，并且該批中每個任務的完工時間是相同的。常用“p－batch”表示平行分批處理機。

目前關于多目標多代理排序的文獻不斷涌現。文獻［1］討論的是為了實現顧客的目標要求，如何通過有效的方法找到相應的非支配序；文獻［2］討論的是2個客戶類的雙目標排序問題：第1類客戶的目標函數是在假設其他客戶的目標函數有界的情況下尋找最優排序；文獻［3］討論的是一個多代理排序問題，3個共同的目標函數是：極小化任務的完工時間、極小化最大延遲、極小化加權總完工時間，并且以最大延遲和加權總完工時間為目標函數的排序模型是NP－完全的。

1 有關符號

設有m個無關的工件X1，X2，…，Xm，并假設處理機的容量是無限的，設工件Xj的加工時間為pj（j＝1，2，…，m）。一個批序列記為σ＝（A1，A2，…，Ar），其中，Ak（k＝1，2，…，r）是一個工件集合。記批Ak的完工時間，易知，在一個序σ中，對每一個工件

用∑Cj表示所有工件的加工總完工時間，Cmax為所有工件的時間表長。用三參數法：

表示以F為目標函數的雙代理單機無界平行分批不相容排序問題。其中，b≥m表示每批的容量是無限的，IG表示任務集的不相容，mul－cuts表示雙代理。

2 Cmax和∑Cj的組合函數

在一臺無界平行分批處理機上，要加工2個任務集C1和C2，其中任務集C1的目標函數為R1，任務集C2的目標函數為R2，這2個任務集是不相容的。用：

Y＝R1＋θR2（θ＞0，θ代表R1和R2這2個不同目標函數之間的權因子）代表這個模型總的目標函數。筆者研究的目標是極小化組合函數Y。

該模型可描述為：在一臺無界平行分批處理機上，加工2類不相容的任務集，目標是極小化Cmax和∑Cj的組合函數：________

用三參數法表示為：

式中，F就是組合函數Y＝R1＋θR2（θ＞0），F關于分量R1和R2是正則的。下面設m1為C1中工件數，m2為C2中工件數，m1＋m2＝m。

3 批排序的最優化

下面給出在最優化Y的過程中要用到的幾個性質。

性質1［4］模型（2）的所有批排序中，C1中的任務一定是放在同一批是最優的。

性質2［4］1｜p－batch b≥m｜∑Cj的最優批排序一定是按SPT－分批序排列。

性質3［4］1｜p－batch b≥m｜∑Cj的最優序為（A1，A2，…，Ar）的充要條件是：

下面利用DP算法（動態規劃算法）找到1｜p－batch b≥m｜∑Cj中任務C2的最優批排序。假設C2中任務已按SPT標號，即p1≤p2≤…≤pm2。假設C2中包含最后m2－j＋1個任務Xj，Xj＋1，…，Xm2的SPT－分批序的最小總完工時間為Gj，并且第一批是從0時刻開始加工。求任務C2最優序的DP算法如下：

步驟1 在當前序的前面放入新的一批。不妨設在當前序｛Xk，…，Xm2｝的前面放入新的一批｛Xj，…，Xk－1｝（其中pk－1是｛Xj，…，Xk－1｝的加工時間），則∑Cj增加了pk－1（m2－j）。

步驟2 求出這個算法的遞歸方程。設Gm2＋1＝0為遞歸的初始條件，對j＝m2，m2－1，…，1，則遞歸方程為：

G1就是最后的最優值。

為了求得模型（2）的最優序σ＊，由性質1知，只須在任務集C2的批之間找到放批Atotal的最好位置即可。用r個大任務X1，X2，…，Xr代表C2中的r個批，其中P（Xi）＝P（Ai）；把Atotal當作任務X0，其中P（X0）＝P。在求∑Cj時，X0的權重為W0＝1，Xi的權重是Wi＝｜Ai｜（1≤i≤r）。則極化目標函數：

等價于極小化r＋1個任務X0，X1，X2，…，Xr的加權總完工時間：

式中，序σ＊中任務Xi的完工時間為C（Xi），X0的權為1，Xi的權轉化為θ｜Ai｜（1≤i≤r）。

由性質3及 WSPT規則［5］有：如果就在C2的批Ak與Ak＋1之間安插批是模型（2）的最優序，并且：

其中，在最優批排序σ＝（A1，A2，…，Ar）中，批Ai的完工時間為C（Ai）。

4 計算復雜性分析

由上面的求解過程可以得到下面2個定理：

［1］Agnetis A，Mirchandani P B，Pacciarelli D，et al.Nondominated schedules for a job－shop with t wo competing users［J］.Computational ＆Mathematical Organization Theory，2000，6（2）：191－217.

［2］Agnetis A，Mirchandani P B，Pacciarelli D.Scheduling pr oblems wit h t wo co mpeting agents［J］.Oper Res，2004，52（2）：229－242.

［3］Lee C Y，Uzsoy R.Mini mizing makespan on a single batch processing machine wit h dynamic job arrivals［J］.Inter national Jour nal of Production Research，1999，37：219－236.

［4］Baker K R，Smit h J C.A multiple－criterion model f or machine scheduling［J］.Jour nal of scheduling，2003，6：7－16.

［5］Yaalzdani Sabouni M T，Jola i F.Opti mal methods for batch processing problem with makespan and maxi mum lateness objectives［J］.Applied Mathematical Modelling，2010，34：314－324.