單機(jī)不相容雙目標(biāo)最優(yōu)批排序研究

李小襯

（武漢生物工程學(xué)院計(jì)算機(jī)與信息工程系，湖北 武漢430415）

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

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

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

1 有關(guān)符號

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

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

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

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

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

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

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

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

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

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

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

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

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

性質(zhì)3［4］1｜p－batch b≥m｜∑Cj的最優(yōu)序?yàn)椋ˋ1，A2，…，Ar）的充要條件是：

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

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

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

G1就是最后的最優(yōu)值。

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

等價(jià)于極小化r＋1個任務(wù)X0，X1，X2，…，Xr的加權(quán)總完工時間：

式中，序σ＊中任務(wù)Xi的完工時間為C（Xi），X0的權(quán)為1，Xi的權(quán)轉(zhuǎn)化為θ｜Ai｜（1≤i≤r）。

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

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

4 計(jì)算復(fù)雜性分析

由上面的求解過程可以得到下面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.