帶懲罰費用的多重任務排序問題?

崔倩娜

（云南大學數學與統計學院 昆明 650000）

1 引言

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

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

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

Bartal等［1］還對帶懲罰費用的在線機器排序問題做了研究，所有任務的加工時間和懲罰費用都是未知的，給出一個競爭比為2.618的最優在線算法；當機器數為2時，設計了一個競爭比為1.618的最優在線算法。Seiden［17］研究了帶懲罰費用的可中斷平行機在線排序問題，給出一個競爭比為(4+)/3的在線算法，并指出任何在線算法的下界為 2.12。Gyorgy和 Imreh［18］提出帶懲罰費用和機器費用的在線排序問題，設計了一個競爭比為(3+)/2 的最優在線算法。Epstein 和 Haider［19］研究了關于帶懲罰費用的三臺機器在線排序問題，當所有任務的處理時間為1，設計了一個競爭比1.839的最優在線算法。

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

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

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

2 MTSR問題的離線算法

2.1 2-近似算法

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

算法1 H

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

2）對U-B中的用戶，以加工時間非減順序排列；

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

這里 k=tj-

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

4）對每一個0≤h≤ ||U-B ，從U-B中選取的前h個用戶，將這h個用戶中的所有任務集（每個任務集視作一個任務，共hm個任務）用LS（List Scheduling）算法安排到m臺機器上，然后將剩下的所有用戶都拒絕，令這一調度方案為Sh。

5）在 ||U-B+1個可行方案中，選擇目標函數值最小的方案Sh。

定理1 算法H是一個運行時間為O(n2logn)的2-近似算法。

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

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

否則，令l為在最優方案中從用戶集合U-B中接受的最后一個用戶。考慮算法H的輸出解Sl，不失一般性，令 A={1,…,l}表示調度方案Sl所接受的用戶集合，則l為所有被接受的用戶里，任務加工時間最大的用戶。由于用戶集合A中的所有任務集合按LS方法安排在m臺機器上。所以，調度方案Sl的機器的最大完工時間至多為

由于算法H的輸出的目標函數值至多為方案Sl的目標函數值，則

因為集合 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中接受的最后一個用戶，所以A*中不包含用戶集合{l+1,…, ||U-B}中任意一個用戶。從而，可以得到

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

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

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

2.2 機器數為固定常數時的一個FPTAS

當機器數m為固定常數時，在動態規劃的基礎上采用舍入取整技術，設計了一個FPTAS。

定理2 當機器數為固定常數時，MTSR問題可以在多項式時間O(n(tmaxZ*)m)內解決，其中tmax=max{t1,…,tn}，Z*是最優方案的目標函數值。

證明 采用動態規劃方法。

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

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

定理3 對任意ε＞0，MTSR問題存在一個運行時間為O(()m(ntmax)m+1)的FPTAS。

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

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

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

3 關于兩臺機器的在線算法

在離線問題中，所有用戶提交的任務數量，每項任務的加工時間，以及被拒絕后的懲罰費用都是已知的。而要研究的在線問題，在上一個用戶提交的所有任務被安排完之后，才會獲得一個新用戶的信息。當機器數為2時，設計了一個在線算法Aα，算法的設計思想是將懲罰費用較小的用戶都拒絕，再將剩余用戶提交的任務劃分成兩個任務集，把這兩個任務集分別安排在兩臺機器上。

算法2 Aα

1）如果用戶 j提交的所有任務的加工時間和懲罰費用滿足wj≤αpj，則拒絕用戶 j；

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

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

證明 分兩種情況來證明：

1）若算法Aα拒絕了所有用戶，則由算法輸出的目標函數值

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

2）否則，令l為最后一個被接受的用戶，Tl2為Tl中最后一個被安排的任務集合。則所有被接受的用戶提交的所有任務被安排到2臺機器上之后，機器的最大完工時間為

由于算法Aα拒絕的用戶集合R，其中每項任務的加工時間和懲罰費用滿足wj≤αpj，則會有∑j∈Rtjwj≤2α∑j∈Rtjpj/2 ，所以算法輸出的用戶集合R提交的所有任務的懲罰費用之和滿足：

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

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

為證明競爭比，則需要討論算法輸出的被接受的最后一個用戶l是否屬于最優方案中被接受的用戶集合，分成兩種情況來說明：

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

可以將上式轉化為

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

故，當 Aα滿足不等式（6）時，在線算法 Aα的競爭比為。

當用戶提交的任務數量都為1時，Bartal等［1］已證明不存在競爭比小于1.618的在線算法，所以，算法Aα為最優在線算法。證畢。

4 結語

本文提出一個帶懲罰費用的多重任務排序問題，針對離線問題，設計了一個2-近似算法和一個FPTAS。對于在線問題，當機器數為2時，設計了一個競爭比為1.618的最優在線算法。

未來值得研究的問題有：利用Ou等［3］的算法思想設計MTSR問題的一個(1.5+ε)-的近似算法；設計MTSR問題的一個運行時間更低的FPTAS的；利用文獻［22］中的算法思想設計一個用戶數為固定常數時MTSR問題的一個最優算法。