李小襯

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

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

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

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

1 有關符號

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

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

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

2 Cmax和∑Cj的組合函數(shù)

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

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

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

用三參數(shù)法表示為：

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

3 批排序的最優(yōu)化

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

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

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

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

下面利用DP算法（動態(tài)規(guī)劃算法）找到1｜p－batch b≥m｜∑Cj中任務C2的最優(yōu)批排序。假設C2中任務已按SPT標號，即p1≤p2≤…≤pm2。假設C2中包含最后m2－j＋1個任務Xj，Xj＋1，…，Xm2的SPT－分批序的最小總完工時間為Gj，并且第一批是從0時刻開始加工。求任務C2最優(yōu)序的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就是最后的最優(yōu)值。

為了求得模型（2）的最優(yōu)序σ＊，由性質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）。則極化目標函數(shù)：

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

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

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

其中，在最優(yōu)批排序σ＝（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.