帶等級約束的多重工件在線（半在線）排序問題*

代兵飛 夏玉霞

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

1 引言

排序問題是一類具有廣泛應用的組合最優化問題，其目標是尋找一個使機器的最大完工時間最小的調度。等級約束常常發生在服務業，服務者將客戶劃分成不同的等級。等級越高的客戶享受越好的服務，區分不同服務的方法是給服務者（如：機器）和客戶（如：工件）貼上帶有服務等級的標簽，并且服務者只為服務等級不低于自己的客戶提供服務。

對于經典的在線排序問題，最早由Bar-Noy 等人提出并研究。當機器臺數m=2 時，Xu 和Liu 在文獻［1］中對工件帶準備時間的調度問題給出了一個競爭比為1.555 的在線算法。Jiang 等和Park 等人在文獻［2］和［3］中設計了競爭比都為5/3的最優在線算法。Zhang 和Tan 在文獻［4］中對工件可在機器間任意分割且可并行加工的在線排序問題設計了基于線性規劃解的在線算法，證明了當m≥2時，此算法的競爭比為γm，這里γm是線性規劃目標函數的最優值。當機器臺數m＞2 且為固定常數時，文獻［5］、文獻［6］中所給在線算法的競爭比都大于2。

當機器臺數m=2 時，存在多個半在線算法［7～9］。當已知工件加工時間總和而且每個工件的加工時間被界定于[1，α](1 ≤α＜2)時，Luo和Xu在文獻［7］中證明了半在線算法的競爭比：當 1 ≤α＜ 2 時，競爭比為 (1+α)/2 ；當α≥2 時，競爭比為3/2。當已知工件的加工時間總和時，Park 等在文獻［3］中也設計了一個競爭比為3/2的最優半在線算法。在文獻［8］中，當已知離線最優值和工件的最大加工時間時，Wu 等分別設計了一個競爭比為3/2 的半在線算法和一個競爭比為( 5+1)/2 的半在線算法。

在經典的在線和半在線排序中，工件總是一個接一個地到達。但在許多環境中，例如高性能計算（請參閱文獻［9～10］），每個用戶總是提交一些要處理的相同任務。對于不同物品類型的裝箱問題，每個物品類型都有一些物品，Goemans 等在文獻［11］設計了一個最優算法。這些工作激勵我們研究帶等級約束的多重工件調度問題（為了簡便，我們把這個問題簡記為HSBT 問題），其中每個客戶提交一些相同的工件。在本文，對于兩臺平行機上的HSBT 問題，我們設計了一個在線算法和一個半在線算法。

2 預備知識

在經典的帶等級約束的平行機排序問題中引入客戶概念。兩臺平行機上的HSBT 問題描述如下：給定問題實例I=(M，N，J，a) ，其中機器集M={M1，M2}有兩臺機器，客戶集N={1，2，…，n}有n個客戶。客戶i有ai個相同的工件，客戶i的工 件 集Ji={Ji，1，…，Ji，ai} 。所有客戶的工件集為了方便敘述，令p表示客戶i的每

i一個工件的加工時間。在這里，客戶被分為金卡客戶和銀卡客戶，金卡客戶的工件等級較高，銀卡客戶的工件等級較低。對于i=1，2，…，n，若客戶i為銀卡客戶，則客戶i的每一個工件只能在機器M1上加工；若客戶i為金卡客戶，則客戶i的每一個工件可以在兩臺機器中的任意一臺加工。n個客戶的工件被分配給這兩臺機器，我們可以得到一個調度 (S1，S2)，其中Sk(k=1，2)表示分配給機器Mk的工件集。t(Sk)表示機器Mk的完工時間。目標是尋找一個調度方案，使得機器的最大完工時間最小。G1表示銀卡客戶的工件構成的集合，G2表示金卡客戶的工件構成的集合。t(Gk) (k=1，2)表示工件集Gk中所有工件的加工時間總和。

3 在線算法

當客戶i到達時，更新Pi為已到達工件的最大加工時間，更新Ti為已到達工件的加工時間總和的一半，更新Di為已到達銀卡客戶的工件的加工時間總和。表示在調度客戶i的工件后，機器Mj加工的工件集。明顯地，。在這里，我們用COPT表示用最優離線算法求解實例得到的目標值 。令Li=max{Pi，Ti，Di} ，顯 然COPT≥Li。在本文的在線算法中，當客戶i到達時，如果客戶i為銀卡客戶，則客戶i的所有工件被分配給機器M1加工。若客戶i為金卡客戶，則客戶i的qi個工件被分配給機器M2加工，剩下的工件被分配給機器M1加工，其中。

引理1根據在線算法，如果客戶i為金卡客戶且qi＜ai，則 (ai-qi)pi≤Li。

證明：如果客戶i只有一個工件，即ai=1。根據 引 理 條 件 ，則qi=0 ，有 (ai-qi)pi≤Li。若ai≥2，根據ai-qi的值，分兩種情況討論。

情況1：ai-qi≥2

根據在線算法、Ti和Li的定義有

根據式（2）和式（1）有

因為ai-qi≥2 ，所以ai-qi-1 ≥1，再結合式（3）有

結合式（3）和式（4）有

情況2：ai-qi=1

根據此時ai≥ 2 有

綜上可知，引理1成立。

引理2根據在線算法，如果客戶i為金卡客戶且qi＜ai，則成立。

證明：根據在線算法和引理1有

根據式（5）和式（6）有

根據Li和Ti的定義有

根據式（7）和式（8）有

因此引理2成立。

定理3表示在線算法求解實例得到的目標值。

證明：假設定理不成立，則存在極小反例（極小反例是指最少客戶個數的反例）。對于極小反例，機器的最大完工時間在加工完最后一個客戶（客戶n）的工件后才能被確定，因此

根據客戶n是金卡客戶還是銀卡客戶，分兩種情況討論：

情況1：客戶n是金卡客戶。

如果客戶n的工件都被分配給機器M2加工，根據在線算法有

這與式（9）矛盾，因此客戶n的工件至少有一個被分配給機器M1加工。因此有

根據式（8）和式（10）有

又由引理1可知 (an-qn)pn≤Ln≤COPT有

這與極小反例矛盾。

情況2：客戶n是銀卡客戶。

根據極小反例的定義有

由引理2可知

根據式（8）、式（12）和Ln≤COPT有

因此

這與極小反例矛盾。因此，定理3成立。

4 半在線算法

在這一部分，我們研究在調度開始前已知所有工件的加工時間總和為的半在線排序。令顯然C≥HT。在這里，OPT CSEMI表示半在線算法求解實例得到的目標值。在半在線算法中，當客戶i到達時，如果客戶i為銀卡客戶，則客戶i的所有工件被分配給機器M1加工。如果客戶i為金卡客戶，則客戶i的qi個工件被分配給機器M2加工，剩下的工件被分配給機器M1加工，其中。

引理4在半在線算法中，如果客戶i為金卡客戶且qi＜ai，則 (ai-qi)pi≤HT。

證明：引理4的證明與引理1類似。

引理5G1至多含有一個銀卡客戶的工件。

證明：假設引理5 不成立。G1包含兩個不同的銀卡客戶的工件，不妨設這兩個客戶為i，j。如果刪除客戶j而且重新定義客戶i的工件大小令pi=(ai pi+aj pj)/ai，我們將得到一個客戶數更少的反例。這與極小反例矛盾。

引理6。

引理7S1∩G2只含有一個金卡客戶的部分工件。

證明：根據極小反例的定義有

引理6 表明S1一定含有金卡客戶的部分工件。假定S1包含兩個不同的金卡客戶的部分工件，設這兩個客戶分別為i，j(i＜j)。

根據半在線算法和客戶i的定義有。

對于客戶j有 (aj-qj)pj＞HT。

根據客戶i，j的定義有qj)pj＞ 2HT。

這與HT的定義矛盾，因此引理7成立。

定理8。

證明：假設定理不成立。對于極小反例，機器的最大完工時間在加工完最后一個客戶（客戶n）的工件后被確定，因此

根據客戶n是金卡客戶還是銀卡客戶，分兩種情況討論。

情況1：客戶n是金卡客戶。

如果客戶n的所有工件分配給機器M2加工，則有根據極小反例，則有又因為這與式（14）矛盾。

因此，客戶n的部分工件一定被分配給機器M1加工。

這與引理4矛盾。

情況2：客戶n是銀卡客戶。

根據極小反例有CSEMI=t(S1)。由引理5 和引理 7，有S1={Ji，qi+1，…，Ji，ai，Jn} ，其 中 {Ji，qi+1，…，Ji，ai}=S1∩G2。

然后，我們有

但是根據引理5 和引理6 有an pn=t(G1)＜結合式（15）有 (a-q)p＞C≥iiiOPT HT，這與引理4矛盾。

綜上可知，定理8成立。

5 結語

對于兩臺平行機上的HSBT 問題，本文設計了一個競爭比為5/3 的在線算法和一個競爭比為3/2的半在線算法。接下來，當機器臺數m為固定常數時，我們希望給出該問題的一個近似算法和一個FPTAS。