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

代兵飛 夏玉霞

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

1 引言

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

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

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

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

2 預(yù)備知識

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

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

3 在線算法

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

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

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

情況1：ai-qi≥2

根據(jù)在線算法、Ti和Li的定義有

根據(jù)式（2）和式（1）有

因?yàn)閍i-qi≥2 ，所以ai-qi-1 ≥1，再結(jié)合式（3）有

結(jié)合式（3）和式（4）有

情況2：ai-qi=1

根據(jù)此時ai≥ 2 有

綜上可知，引理1成立。

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

證明：根據(jù)在線算法和引理1有

根據(jù)式（5）和式（6）有

根據(jù)Li和Ti的定義有

根據(jù)式（7）和式（8）有

因此引理2成立。

定理3表示在線算法求解實(shí)例得到的目標(biāo)值。

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

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

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

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

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

根據(jù)式（8）和式（10）有

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

這與極小反例矛盾。

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

根據(jù)極小反例的定義有

由引理2可知

根據(jù)式（8）、式（12）和Ln≤COPT有

因此

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

4 半在線算法

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

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

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

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

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

引理6。

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

證明：根據(jù)極小反例的定義有

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

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

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

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

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

定理8。

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

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

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

如果客戶n的所有工件分配給機(jī)器M2加工，則有根據(jù)極小反例，則有又因?yàn)檫@與式（14）矛盾。

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

這與引理4矛盾。

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

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

然后，我們有

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

綜上可知，定理8成立。

5 結(jié)語

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