帶懲罰費(fèi)用的多重任務(wù)排序問(wèn)題?

崔倩娜

（云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 昆明 650000）

1 引言

長(zhǎng)期以來(lái)，排序問(wèn)題的近似算法研究都是算法理論領(lǐng)域研究的熱點(diǎn)問(wèn)題之一。受滑雪板租賃問(wèn)題的啟發(fā)，Bartal等［1］提出帶懲罰費(fèi)用的平行機(jī)排序問(wèn)題 P∥Cmax+Σj∈Rwj，其定義如下：給定 m 臺(tái)平行機(jī)和n項(xiàng)任務(wù)，每項(xiàng)任務(wù)的處理時(shí)間為 pj，懲罰費(fèi)用為wj，一項(xiàng)任務(wù)要么被接受并在某臺(tái)機(jī)器上處理，要么被拒絕并產(chǎn)生相應(yīng)的懲罰費(fèi)用。該問(wèn)題的目標(biāo)是尋找一個(gè)排序方案，使得機(jī)器的最大完工時(shí)間與被拒絕任務(wù)的懲罰費(fèi)用之和最小。Bartal等［1］設(shè)計(jì)了一個(gè)運(yùn)行時(shí)間為O(nlogn)的(2-1/m)-近似算法和一個(gè)運(yùn)行時(shí)間為O((n3/ε)■■9ε2)的多項(xiàng)式時(shí)間近似方案（Polynomial Time Approximation Scheme，PTAS），推廣了 Hochbaum和Shmoys［2］的結(jié)果。當(dāng)機(jī)器數(shù)為固定常數(shù)時(shí)，Bartal等［1］還給出了一個(gè)運(yùn)行時(shí)間為O(nm+1/εn)的全多項(xiàng)式時(shí)間近似方案（Fully Polynomial Time Approximation Scheme，F(xiàn)PTAS）。隨后，帶懲罰費(fèi)用的機(jī)器排序問(wèn)題及其變種迅速成為排序領(lǐng)域的熱點(diǎn)問(wèn)題之一。Ou等［3］給出 P∥Cmax+Σj∈Rwj問(wèn)題的一個(gè)運(yùn)行時(shí)間為O(nlogn+n/ε)的 (1.5+ε)-近似算法（這里 ε＞0為任 意 常 數(shù)）。 最 近 ，Ou和 Zhong［4］給 出P∥Cmax+Σj∈Rwj問(wèn)題的一個(gè)運(yùn)行時(shí)間為 O(mn2/ε2)的(4/3+ε)-近似算法。

Zhang和Lu［5］考慮了帶就緒時(shí)間和懲罰費(fèi)用的平行機(jī)排序問(wèn)題 P ||rjCmax+Σj∈Rwj（這里 rj為任務(wù)的就緒時(shí)間），設(shè)計(jì)了一個(gè)運(yùn)行時(shí)間為O(n2)的2-近似算法，當(dāng)機(jī)器數(shù)為固定常數(shù)時(shí)，給出一個(gè)運(yùn)行時(shí)間為 O(n2m+1/εm)的 FPTAS。隨后，Zhong和 Ou［6］提出一個(gè)運(yùn)行時(shí)間為 O(nlogn)的2-近似算法，一個(gè)運(yùn)行時(shí)間為 O(nlogn+mO((log1/ε)/ε2))的 PTAS，和一個(gè)機(jī)器數(shù)為固定常數(shù)時(shí)運(yùn)行時(shí)間為O(nlogn+1/ε3m+6)的 FPTAS，改進(jìn)了 Zhang和 Lu［5］的結(jié)果。Zhong等［7］研究文獻(xiàn)［4］中 m=2 的情況，給出一個(gè)運(yùn)行時(shí)間為O((n/ε)2)的(1.5+ε)-近似算法。Li等［8］研究了懲罰費(fèi)用受限的平行機(jī)排序問(wèn)題 P ||Σj∈RwjCmax，設(shè)計(jì)了一個(gè)運(yùn)行時(shí)間為 O(mn2)的2-近似算法，一個(gè)運(yùn)行時(shí)間為O(nmO(1/ε2)+mn2)的PTAS和機(jī)器數(shù)為固定常數(shù)時(shí)的一個(gè)運(yùn)行時(shí)間為O(1/ε2m+3+mn2)的FPTAS。Shabtay等［9］研究了處理時(shí)間相同時(shí)的帶懲罰費(fèi)用的雙標(biāo)準(zhǔn)同類機(jī)排序問(wèn)題。

當(dāng)機(jī)器數(shù)為1時(shí)，Zhang等［10］證明了帶就緒時(shí)間和懲罰費(fèi)用的單機(jī)排序問(wèn)題1 ||rj,rej Cmax+Σj∈Rwj是NP-難的，設(shè)計(jì)了一個(gè)運(yùn)行時(shí)間為O(n2)的2-近似算法和一個(gè)運(yùn)行時(shí)間為O(n3/ε)的FPTAS。Ou 等［11］提出一個(gè)運(yùn)行時(shí)間為 O(nlogn)的2-近似算法和所有任務(wù)的加工時(shí)間相同時(shí)的一個(gè)運(yùn)行時(shí)間為O(n2logn)的精確算法。Zhang等［12］證明了帶就緒時(shí)間和懲罰費(fèi)用受限的單機(jī)排序問(wèn)題1|rj,Σj∈Rwj≤U |Cmax是 NP-難的，給出一個(gè)運(yùn)行時(shí)間為 O(n3/ε)的FPTAS。Lu和Zhang［13］考慮了帶生產(chǎn)費(fèi)用和懲罰費(fèi)用的單機(jī)排序問(wèn)題。Shabtay等［14］研究了帶懲罰費(fèi)用和位置費(fèi)用的雙標(biāo)準(zhǔn)的單機(jī)排序問(wèn)題，設(shè)計(jì)了多個(gè)最優(yōu)算法或近似算法。He等［15］考慮了帶就緒時(shí)間和懲罰費(fèi)用的雙標(biāo)準(zhǔn)的單機(jī)排序問(wèn)題，對(duì)于最大完工時(shí)間與懲罰費(fèi)用之和最小化問(wèn)題，給出一個(gè)運(yùn)行時(shí)間為O(nlogn)的4/5-近似算法；當(dāng)最大完工時(shí)間受限時(shí)，設(shè)計(jì)了一個(gè)運(yùn)行時(shí)間為O(n2/ε+n2logn)的FPTAS；當(dāng)懲罰費(fèi)用受限時(shí)，設(shè)計(jì)了一個(gè)運(yùn)行時(shí)間為O(n2)的2-近似算法和一個(gè)運(yùn)行時(shí)間為O(n2/ε+n2logn)的FPTAS，推廣了 Gens和 Levner［16］的結(jié)果。

Bartal等［1］還對(duì)帶懲罰費(fèi)用的在線機(jī)器排序問(wèn)題做了研究，所有任務(wù)的加工時(shí)間和懲罰費(fèi)用都是未知的，給出一個(gè)競(jìng)爭(zhēng)比為2.618的最優(yōu)在線算法；當(dāng)機(jī)器數(shù)為2時(shí)，設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)比為1.618的最優(yōu)在線算法。Seiden［17］研究了帶懲罰費(fèi)用的可中斷平行機(jī)在線排序問(wèn)題，給出一個(gè)競(jìng)爭(zhēng)比為(4+)/3的在線算法，并指出任何在線算法的下界為 2.12。Gyorgy和 Imreh［18］提出帶懲罰費(fèi)用和機(jī)器費(fèi)用的在線排序問(wèn)題，設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)比為(3+)/2 的最優(yōu)在線算法。Epstein 和 Haider［19］研究了關(guān)于帶懲罰費(fèi)用的三臺(tái)機(jī)器在線排序問(wèn)題，當(dāng)所有任務(wù)的處理時(shí)間為1，設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)比1.839的最優(yōu)在線算法。

由于在高性能計(jì)算環(huán)境中，用戶提交的任務(wù)通常具有數(shù)量大且處理時(shí)間相同等特征，多重任務(wù)排序引起了學(xué)者的廣泛關(guān)注［20～21］。另一方面，Goemans和 Rothvo?［22］給出多重物品裝箱問(wèn)題的一個(gè)最優(yōu)算法。受文獻(xiàn)［20～22］的啟發(fā)，將任務(wù)或物品的類型視為用戶，本文提出了帶懲罰費(fèi)用的多重任務(wù)排序問(wèn)題（Multi-task Scheduling Problem with Rejection，MTSR），其定義如下：給定 n 個(gè)用戶，每個(gè)用戶 j提交tj項(xiàng)任務(wù)，任務(wù)集記為T(mén)j，Tj中的每個(gè)任務(wù)具有相同的加工時(shí)間 pj和懲罰費(fèi)用wj。每個(gè)用戶提交的任務(wù)要么全部被接受，并被安排在m臺(tái)機(jī)器上處理；要么全部被拒絕，并產(chǎn)生相應(yīng)的懲罰費(fèi)用。本文假定，一旦某項(xiàng)任務(wù)開(kāi)始在某臺(tái)機(jī)器上處理，則中間不被打斷直到完工，而且所有任務(wù)的安排沒(méi)有優(yōu)先權(quán)。目標(biāo)是尋找一個(gè)排序方案，使得機(jī)器的最大完工時(shí)間與所有被拒絕的任務(wù)的懲罰費(fèi)用之和達(dá)到最小。

為更加清晰地描述問(wèn)題，用xij表示被接受的用戶 j提交的任務(wù)被安排在機(jī)器i上的數(shù)量，zj表示用戶 j是否被接受，若被接受，則zj=1，否則，zj=0。MTSR問(wèn)題的數(shù)學(xué)規(guī)劃形式如下：

注意到，當(dāng)每個(gè)用戶提交的任務(wù)數(shù)量tj都為1時(shí) ，MTSR 問(wèn) 題 即 為 Bartal等［1］研 究 的 問(wèn) 題P∥Cmax+Σj∈Rwj。因此，一種直觀的想法是將所有任務(wù)的集合看作問(wèn)題 P∥Cmax+Σj∈Rwj的任務(wù)集，從而使用［1］中的算法進(jìn)行求解。但是，運(yùn)行時(shí)間并不是關(guān)于輸入長(zhǎng)度的多項(xiàng)式函數(shù)。

2 MTSR問(wèn)題的離線算法

2.1 2-近似算法

本節(jié)討論一般情形下的MTSR問(wèn)題，并給出一個(gè)2-近似算法H。算法H的主要思想是將用戶集合U中一部分懲罰費(fèi)用較小的用戶都拒絕，這里 ||U=n；然后，將剩余用戶提交的所有任務(wù)劃分成m個(gè)集合；最后，把劃分后的集合看作一個(gè)整體任務(wù)，并將其安排在m臺(tái)機(jī)器上，接受一些加工時(shí)間較小的用戶。

算法1 H

1）令 B={j|wj≤pj/m}，將集合 B中的所有用戶都拒絕；

2）對(duì)U-B中的用戶，以加工時(shí)間非減順序排列；

3）將U-B中的每一個(gè)用戶 j提交的所有任務(wù)分割成m個(gè)任務(wù)集合，即

這里 k=tj-

即Tj1,…,Tjk的每個(gè)集合中都含有用戶 j所提交的個(gè)任務(wù)，Tj,k+1,…,Tjm中每個(gè)集合都含有用戶 j所提交的個(gè)任務(wù)。計(jì)算每個(gè)被劃分后的集合中總共的加工時(shí)間和懲罰費(fèi)用，即

4）對(duì)每一個(gè)0≤h≤ ||U-B ，從U-B中選取的前h個(gè)用戶，將這h個(gè)用戶中的所有任務(wù)集（每個(gè)任務(wù)集視作一個(gè)任務(wù)，共hm個(gè)任務(wù)）用LS（List Scheduling）算法安排到m臺(tái)機(jī)器上，然后將剩下的所有用戶都拒絕，令這一調(diào)度方案為Sh。

5）在 ||U-B+1個(gè)可行方案中，選擇目標(biāo)函數(shù)值最小的方案Sh。

定理1 算法H是一個(gè)運(yùn)行時(shí)間為O(n2logn)的2-近似算法。

證明 令A(yù)*，R*分別表示最優(yōu)方案中被接受的用戶集合和被拒絕的用戶集合，A*T*和R*T*分別表示用戶集合A*和R*對(duì)應(yīng)的任務(wù)集合，Z*為最優(yōu)方案的目標(biāo)函數(shù)值。令UT表示用戶集合U對(duì)應(yīng)的任務(wù)集，A（或R）表示算法H的輸出解中被接受（或被拒絕）的用戶集合，AT（或RT）表示對(duì)應(yīng)的任務(wù)集。令ZH表示算法H的輸出解的目標(biāo)函數(shù)值。對(duì)任意任務(wù)集T，令M(T)=∑j∈Tpjm和W(T)=∑j∈Twj分別表示任務(wù)集T中所有任務(wù)的平均負(fù)載和總懲罰費(fèi)用。對(duì)任意用戶集合X?U，令C(X)表示X中被接受用戶提交的所有任務(wù)按LS算法安排在m臺(tái)機(jī)器上之后，機(jī)器的最大完工時(shí)間。

假設(shè)算法第2）步中，用戶集合U-B排序結(jié)果為1,…, ||U-B。如果最優(yōu)方案拒絕U-B中所有用戶，由B的定義知，拒絕B中所有用戶也是最有的。因此，方案S0拒絕所有用戶是最優(yōu)的，即ZH=Z*。

否則，令l為在最優(yōu)方案中從用戶集合U-B中接受的最后一個(gè)用戶?？紤]算法H的輸出解Sl，不失一般性，令 A={1,…,l}表示調(diào)度方案Sl所接受的用戶集合，則l為所有被接受的用戶里，任務(wù)加工時(shí)間最大的用戶。由于用戶集合A中的所有任務(wù)集合按LS方法安排在m臺(tái)機(jī)器上。所以，調(diào)度方案Sl的機(jī)器的最大完工時(shí)間至多為

由于算法H的輸出的目標(biāo)函數(shù)值至多為方案Sl的目標(biāo)函數(shù)值，則

因?yàn)榧?A不包含B中任何用戶，所以，有M((AT{Tl,m})∩R*T*)≤W((AT{Tl,m})∩R*T*)。由 l的選擇以及B的定義可知，A*∩(U-A)?B。這是由于U-A={l+1,…, ||U-B}∪B，而 l為 A*中從U-B中接受的最后一個(gè)用戶，所以A*中不包含用戶集合{l+1,…, ||U-B}中任意一個(gè)用戶。從而，可以得到

W((UTAT)∩A*T*)≤M((UTAT)∩A*T*) 。 因此，上面的式（3）可以整理為

所以，算法H的近似比為2。

算法H的第一步選出屬于集合B中的用戶需要 O(n)時(shí)間，第二步給用戶排序最多需要O(nlogn)時(shí)間，第三步將集合U-B中每個(gè)用戶提交的所有任務(wù)劃分成m個(gè)任務(wù)集最多需要O(m)時(shí)間，分割所有用戶提交的所有任務(wù)最多需要O(nm)時(shí)間。計(jì)算每個(gè)集合的運(yùn)行總時(shí)間和總懲罰費(fèi)用最多可以在O(nm)內(nèi)完成。第四步和第五步是選取方案Sh，使用了LS算法，所需要時(shí)間為O(nmlogm)。當(dāng)n＞m時(shí)，算法的運(yùn)行時(shí)間不會(huì)超過(guò)O(n2logn)。證畢。

2.2 機(jī)器數(shù)為固定常數(shù)時(shí)的一個(gè)FPTAS

當(dāng)機(jī)器數(shù)m為固定常數(shù)時(shí)，在動(dòng)態(tài)規(guī)劃的基礎(chǔ)上采用舍入取整技術(shù)，設(shè)計(jì)了一個(gè)FPTAS。

定理2 當(dāng)機(jī)器數(shù)為固定常數(shù)時(shí)，MTSR問(wèn)題可以在多項(xiàng)式時(shí)間O(n(tmaxZ*)m)內(nèi)解決，其中tmax=max{t1,…,tn}，Z*是最優(yōu)方案的目標(biāo)函數(shù)值。

證明 采用動(dòng)態(tài)規(guī)劃方法。

令Li(i=1,2，…,m)為機(jī)器i的當(dāng)前負(fù)載，對(duì)于每個(gè)L1,L2,…,Lm≤Z*，計(jì)算在這些負(fù)載下可以獲得的總懲罰費(fèi)用的最小值。在第 j個(gè)用戶被安排或拒絕后，用Ej(L1,L2,…,Lm)來(lái)定義當(dāng)前負(fù)載下可以獲得的總懲罰費(fèi)用的最小值。令aij為將用戶 j提交的任務(wù)被安排在機(jī)器i上的數(shù)量。當(dāng)Li＜0時(shí)，定義懲罰費(fèi)用的最小值為∞。同時(shí)，可以在具有機(jī)器負(fù)載L1,L2,…,Lm的情況下可以計(jì)算出最后總花費(fèi) Z(L1,…,Lm)。對(duì)于L1,…,Lm≥0，這些值的計(jì)算可以用以下方式得出：

初始化：E0(0,…,0)=0；

定理3 對(duì)任意ε＞0，MTSR問(wèn)題存在一個(gè)運(yùn)行時(shí)間為O(()m(ntmax)m+1)的FPTAS。

證明 將所研究的實(shí)例I，通過(guò)舍入取整技術(shù)構(gòu)造一個(gè)新的實(shí)例I′。每個(gè)用戶 j提交tj個(gè)任務(wù)，這tj個(gè)任務(wù)有相同的加工時(shí)間pj′=和懲罰費(fèi)用wj′=，其中，δ=εZH/2n(tmax)，這里ZH為通過(guò)算法H獲得的目標(biāo)函數(shù)值。采用定理2中的動(dòng)態(tài)規(guī)劃獲得實(shí)例I'的一個(gè)最優(yōu)排序方案，將此方案用在實(shí)例I上，獲得實(shí)例I的一個(gè)近似方案。

通過(guò)上述方式獲得的實(shí)例I的近似函數(shù)值Z(I)與最優(yōu)函數(shù)值最多相差δntmax=εZH/2。由已經(jīng)獲得的最優(yōu)函數(shù)值的下界Z*≥ZH/2，可以得到

由于實(shí)例I′的最優(yōu)函數(shù)值與實(shí)例I的最優(yōu)函數(shù)值滿足 Z*≤Z*(I)/δ≤2ZH/δ，所以 Z*≤4ntmax/ε。定理2指出，實(shí)例I的最優(yōu)解可以在時(shí)間O(n(tmaxZ*)m)內(nèi)得到，故實(shí)例I′的最優(yōu)解可以在多項(xiàng)式時(shí)間O((m(ntmax)m+1)內(nèi)得到。證畢。

3 關(guān)于兩臺(tái)機(jī)器的在線算法

在離線問(wèn)題中，所有用戶提交的任務(wù)數(shù)量，每項(xiàng)任務(wù)的加工時(shí)間，以及被拒絕后的懲罰費(fèi)用都是已知的。而要研究的在線問(wèn)題，在上一個(gè)用戶提交的所有任務(wù)被安排完之后，才會(huì)獲得一個(gè)新用戶的信息。當(dāng)機(jī)器數(shù)為2時(shí)，設(shè)計(jì)了一個(gè)在線算法Aα，算法的設(shè)計(jì)思想是將懲罰費(fèi)用較小的用戶都拒絕，再將剩余用戶提交的任務(wù)劃分成兩個(gè)任務(wù)集，把這兩個(gè)任務(wù)集分別安排在兩臺(tái)機(jī)器上。

算法2 Aα

1）如果用戶 j提交的所有任務(wù)的加工時(shí)間和懲罰費(fèi)用滿足wj≤αpj，則拒絕用戶 j；

2）否則，將用戶 j提交的所有任務(wù)分割成2個(gè)任 務(wù) 集 ，Tj=Tj1∪Tj2，其 中，而，計(jì)算兩個(gè)被劃分后的任務(wù)集中總共的加工時(shí)間和懲罰費(fèi)用，即，且將兩個(gè)集合依次安排在當(dāng)前機(jī)器負(fù)載最小的機(jī)器上。

定理4 如果α滿足不等式（6），則在線算法Aα的競(jìng)爭(zhēng)比為1.618。

證明 分兩種情況來(lái)證明：

1）若算法Aα拒絕了所有用戶，則由算法輸出的目標(biāo)函數(shù)值

由于所有屬于A*的用戶都被算法拒絕，所以，對(duì)于每一個(gè) j∈A*滿足wj≤αpj。則A*提交的所有任務(wù)的懲罰費(fèi)用之和滿足W(A*T*)≤2αM(A*T*)。由條件（6）可將式（7）經(jīng)整理得

2）否則，令l為最后一個(gè)被接受的用戶，Tl2為T(mén)l中最后一個(gè)被安排的任務(wù)集合。則所有被接受的用戶提交的所有任務(wù)被安排到2臺(tái)機(jī)器上之后，機(jī)器的最大完工時(shí)間為

由于算法Aα拒絕的用戶集合R，其中每項(xiàng)任務(wù)的加工時(shí)間和懲罰費(fèi)用滿足wj≤αpj，則會(huì)有∑j∈Rtjwj≤2α∑j∈Rtjpj/2 ，所以算法輸出的用戶集合R提交的所有任務(wù)的懲罰費(fèi)用之和滿足：

由條件（6）可知，算法Aα輸出的被接受的用戶集合 A提交的任務(wù)滿足w≥αp≥p，則集合 Ajjj提交的所有任務(wù)的平均負(fù)載小于總懲罰費(fèi)用。從而會(huì)有

由條件（6）和（9）、（10）、（11）可以得到算法 Aα輸出的目標(biāo)函數(shù)值為

為證明競(jìng)爭(zhēng)比，則需要討論算法輸出的被接受的最后一個(gè)用戶l是否屬于最優(yōu)方案中被接受的用戶集合，分成兩種情況來(lái)說(shuō)明：

1）如果用戶l∈A*，由不等式（6）和等式

可以將上式轉(zhuǎn)化為

2）如果用戶l∈R*，但是算法輸出用戶l被接受，所以 w＞αp≥p，由條件（6），可將上面式lll（12）整理后可得

故，當(dāng) Aα滿足不等式（6）時(shí)，在線算法 Aα的競(jìng)爭(zhēng)比為。

當(dāng)用戶提交的任務(wù)數(shù)量都為1時(shí)，Bartal等［1］已證明不存在競(jìng)爭(zhēng)比小于1.618的在線算法，所以，算法Aα為最優(yōu)在線算法。證畢。

4 結(jié)語(yǔ)

本文提出一個(gè)帶懲罰費(fèi)用的多重任務(wù)排序問(wèn)題，針對(duì)離線問(wèn)題，設(shè)計(jì)了一個(gè)2-近似算法和一個(gè)FPTAS。對(duì)于在線問(wèn)題，當(dāng)機(jī)器數(shù)為2時(shí)，設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)比為1.618的最優(yōu)在線算法。

未來(lái)值得研究的問(wèn)題有：利用Ou等［3］的算法思想設(shè)計(jì)MTSR問(wèn)題的一個(gè)(1.5+ε)-的近似算法；設(shè)計(jì)MTSR問(wèn)題的一個(gè)運(yùn)行時(shí)間更低的FPTAS的；利用文獻(xiàn)［22］中的算法思想設(shè)計(jì)一個(gè)用戶數(shù)為固定常數(shù)時(shí)MTSR問(wèn)題的一個(gè)最優(yōu)算法。