三臺等級機器上帶重排的半在線問題*

趙 姝,肖 滿,李偉東

(云南大學數學與統計學院，云南 昆明 650500)

1 引言

排序問題常用于服務行業中，服務者常根據客戶的等級，如 VIP 客戶和普通客戶，進而提供不同的服務。通常等級越高的客戶能享受的服務也更好。為了區分服務方法，把服務者看作機器，把客戶看作工件，預先給每臺機器和每個工件貼上帶有服務等級的標簽。服務者只為服務等級不低于自己的客戶提供服務。

對于排序問題，若所有工件的信息在其到達之前就獲知，則該問題稱為離線排序問題。若所有工件的信息只能在其到達后獲知，則該問題稱為在線排序問題。若所有工件在到達之前獲知部分工件的信息，則該問題稱為半在線排序問題。對于一個最小化問題，任給工件序列J和一個在線算法A，算法A所得到的輸出值表示為CA(J)(簡記為CA)，離線情形的最優目標值表示為COPT(J)(簡記為COPT)。對于任意一個實例，算法A的競爭比為滿足CA≤r·COPT的最小值r，用來衡量算法A的性能。對于一個在線(半在線)排序問題，若沒有在線(半在線)算法的競爭比小于ρ，則該在線(半在線)排序問題有下界ρ。若該問題的一個在線(半在線)算法A的競爭比等于該問題的下界，則稱算法A是最優的。

對于帶等級約束的排序問題，Hwang等人[1]研究了在m臺機器上最小化最大完工時間的離線排序問題，提出了近似算法LG-LPT(Lowest Grade and Longest Processing Time first)，并證明了LG-LPT算法在m=2時競爭比至多為5/4，在m≥3時競爭比至多為2-1/(m-1)。Wu等人[2]設計了帶2種等級機器上的最優半在線算法。Zhang等人[3]設計了1+(m2-m)/(m2-wm+w2)<7/3的在線算法，對于任意的w和m，其中w是高等級的機器數量，當m=3時，競爭比為1.857。對于帶2種等級機器且工件的加工時間受區間約束的模型，Zhang等人[4]提出了最優的在線算法。Cai等人[5]研究了在m(m≥3)臺同類型機器上帶2種等級的在線排序問題，w是等級為1的機器數量，m-w是等級為2的機器數量。基于貪婪算法的基礎框架，當w=1時，他們提出了競爭比為9/5的在線算法；當1

基于同型機上的在線或離線排序問題，是過去排序與調度研究中最受歡迎的問題之一[6，7]。半在線排序問題是一般在線問題的松弛，它是指在工件到達之前工件的部分信息是已知的[8，9]，或者說包含緩沖區[10，11]、平行機和重排3種形式，更復雜的是多種信息的組合。Kellerer等人[10]研究了2種模型，一種是工件不斷到達，可以利用緩沖區存放一定數量的工件;另一種是存在2個并行處理器，選擇一個更好的結果作為輸出,2個最優算法的競爭比均為4/3。Xiao等人[11]研究了3臺等級機器上最小化最大完工時間，緩沖區大小為1的情形，對于2類等級分配模型，分別給出了競爭比為5/3和12/7的在線算法。

為了進一步闡明不同類型信息的價值，一些文獻研究了2種信息的組合，得到了更好的競爭比。對于最小化最大完工時間的目標，Park等人[12]研究了2臺等級機器的情形，提出了競爭比為5/3的最優在線算法，以及在已知工件加工時間之和的半在線情形下，提出了競爭比為3/2的最優算法。在2臺等級機器上，當已知低等級工件的加工時間之和時，Chen等人[13]提出了競爭比為3/2的最優算法；當已知每個等級的工件加工時間之和時，他們提出了競爭比為4/3的最優算法。在2臺機器上，已知每個工件大小在[p,tp]，其中p>0,t>1，對于1≤t<4/3和t≥2時，Cao 等人[14]分別提出了競爭比為(t+1)/2和4/3的最優算法。肖滿等人[15]針對3臺等級機器上已知工件總加工時間的情形，給出了競爭比為3/2的最優算法。在2臺等級機器上，目標為最大化最小機器的完工時間，針對已知最大工件大小的情形,Wu等人[16]設計了最優算法。

對于帶重排的半在線情形，有2類模型：一類是當有新工件到達時，(任意時刻)都可以重排；另一類是所有工件都被分配后，再進行重排。

第1類是任意時刻的重排，針對2臺同類型機器，目標為最小化最大完工時間，當有新工件到達進行分配時，至多d個已經分配的工件可以重排的情形。Dósa等人[17]提出了d=2的最優算法,以及d=1時s≤1.324 7或者s≥1.732時的最優算法，這里s≥1是最快的機器速度。此外，Sanders等人[18]討論了當一個新的工件到達時，允許分配當前的新工件和重排一些已經分配的工件(重排工件大小之和不超過β，β為新工件的大小)到其他的機器上，目標為最小化最大完工時間；并給出了在m臺機器上，當β=4/3時，競爭比為3/2的算法，以及在2臺機器上，當β=1時，競爭比為7/6的算法。

對于2臺等級的同類型機器上帶重排的半在線排序問題，在所有工件都被分配后，算法最后僅重排一個工件。Chen等人[22]研究了目標為最小化最大完工時間，設計了一個競爭比為3/2的最優半在線算法;Qi等人[23]研究了最小化Lp范數問題，給出了最后重排一個工件與緩沖區大小為1時的統一的最優算法；閔嘯[24]針對目標為極大化最小機器負載，設計了一個競爭比為3/2的最優半在線算法。

本文研究了3臺等級機器上帶重排的半在線排序問題，當所有工件都被分配后，在等級約束的限制下，允許重排一臺機器上的最后一個工件，使得3臺機器上的最大完工時間最小。3臺機器處理工件速度相同，但有不同的等級約束，本文討論2種情形：第1種是1臺機器的等級為1，另2臺機器的等級為2，使用三參數法表示為P3(1,2,2)|reassignment|Cmax;第2種是2臺機器的等級為1，另1臺機器的等級為2，表示為P3(1,1,2)|reassignment|Cmax。

本文的結構如下：第2節給出符號定義;第3節討論P3(1,2,2)|reassignment|Cmax，給出了一個競爭比下界為3/2，并提出了一個競爭比至多為5/3的在線算法;第4節討論P3(1,1,2)|reassignment|Cmax，給出了一個競爭比下界為3/2，并提出了一個競爭比至多為12/7的在線算法;最后，對全文做出總結。

2 符號定義

給定3臺同類型機器M1，M2，M3和n個工件的集合J。工件按序到達，定義第j個到達的工件Jj∈J，Jj=(pj,gj)，pj∈R+為Jj的加工時間，gj表示Jj的等級，當gj=k時，稱工件Jj的等級為k，k∈{1,2}。每臺機器Mi有一個等級g(Mi)，且g(Mi)∈{1,2}，i∈{1,2,3}。當且僅當gj≥g(Mi)時，工件Jj才能被分配到機器Mi上加工，加工過程不允許中斷。工件Jj分配之后，下一個工件Jj+1才會到達，后續工件的任何信息都不會提前獲知。機器的完工時間等于分配給它的工件的大小之和，目標是最小化最大完工時間。

一個調度方案的工件J的一個劃分為(S1,S2,S3),其中Si(i=1,2,3)包括分配給Mi的所有工件。機器Mi的負載為分配給它的工件的處理時間之和，表示為Li。調度的目標是使max{L1,L2,L3}最小。

對于j∈{1,2,…,n}，i∈{1,2,3}，k∈{1,2}，給出以下的符號定義：

Li：算法結束后，機器Mi的最終負載；

pmax:等級為1的最大工件的處理時間；

qmax:等級為2的最大工件的處理時間；

3 P3(1,2,2)|reassignment|Cmax

本節討論M1等級為1，M2和M3的等級為2，在等級約束下，僅重排一臺機器上最后一個工件的情形。

3.1 下界

對于j∈{1,2,…,n}，有:

(1)

引理1對于在線問題P3(1,2,2)|reassignment|Cmax，前j個工件被分配后的最優目標值至少為LBj。

□

所有工件分配完后，

故由引理1有式(2):

(2)

定理1對于在線問題P3(1,2,2)|reassignment|Cmax的任意在線算法A，所有工件被分配后，在等級約束下，僅重排一臺機器上的最后一個工件，算法A的競爭比至少為3/2。

證明對于任意在線算法A，工件序列的前2個工件為J1=(1,1)，J2=(1,2)。

情形1J2分配給M1，最后一個工件J3=(1,1)到達。因為J3的等級為1，此時重排不會發生，所以CA=3，COPT=2，有CA/COPT=3/2。

情形2J2分配給M2，J3=(2,2)到達。

情形2.1J3分配給M1，最后一個工件J4=(1,1)到達。所有的工件分配完后，在等級約束下，重排負載最大的機器上的最后一個工件，此時，由于機器M1上的負載為4，且其最后一個工件的等級為1，所以不會發生重排。則CA≥3，COPT=2，CA/COPT≥3/2。

情形2.2J3分配給M2，下一個工件J4=(1,1)到達，最后一個工件J5=(1,2)到達，工件序列結束。所有的工件分配完后，在等級的約束下，無論是否重排，均有CA≥3，COPT=2，CA/COPT≥3/2。

情形2.3J3分配給M3，最后一個工件J4=(2,2)到達。所有的工件分配完后，在等級約束的限制下，無論是否重排，CA≥3，COPT=2，CA/COPT≥3/2。

情形3J2分配給M2,J3=(2,2)到達。(類似于情形2)

因此，有CA/COPT≥3/2，定理1成立。

證畢。

□

3.2 算法A1

(1)迭代階段：

步驟3否則gj=2，

步驟4若還有新工件到達，令j=j+1，返回步驟2。

(2)重排階段：

定理2對于問題P3(1,2,2)|reassignment|Cmax的在線算法A1，所有工件都被分配后，在等級約束的限制下，僅重排機器M3上的最后一個工件，算法A1的競爭比至多為5/3。

證明對于M3上最后一個工件Jx，處理時間為px，且等級為2。

根據算法A1有:

與Tt≤3LBt矛盾，所以L2≤(5/3)LBn。

情形2若重排會發生，即在迭代階段所有工件都被分配后有：

(3)

先分析M1的負載。

與Tt≤3LBt矛盾。所以,L2≤(5/3)LBn成立。

再分析M2的負載。

所以，CA1/COPT≤max{L1,L2,L3}/LB≤(5/3)。

證畢。

□

4 P3(1,1,2)|reassignment|Cmax

本節討論M1和M2等級為1，M3的等級為2，在等級約束下，僅重排一臺機器上的最后一個工件。

4.1 下界

對于j∈{1,2,…,n}，有:

(4)

引理2對于在線問題P3(1,1,2)|reassignment|Cmax，分配前j個工件后的最優目標值至少為LBj。

□

所有工件分配完后，

根據引理2有式(5):

(5)

定理3對于在線問題P3(1,1,2)|reassignment|Cmax的任意在線算法A，所有的工件都被分配后，在等級約束下，僅重排一臺機器上的最后一個工件，算法A的競爭比至少為3/2。

證明對于任意在線算法A，工件序列的初始2個工件為J1=(1,2)和J2=(2,1)。

情形1J1=(1,2)被分配給M1。

情形1.1J2=(2,1)被分配給M1。工件J3=(1,1)到達，工件序列結束。所有工件都被分配后，在等級約束的限制下，無論是否重排，都有CA≥3，COPT=2，CA/COPT≥3/2。

情形1.2J2=(2,1)被分配給M2。接著工件J3=(1,2)和J4=(2,1)到達，工件序列結束。所有工件都被分配后，在等級約束下，無論是否重排，都有CA≥3，COPT=2，CA/COPT≥3/2。

情形2J1被分配給M2，與情形1類似。

情形3J1=(1,2)被分配給M3。

情形3.1J2=(2,1)被分配給M1。工件J3=(1,1)和J4=(2,2)到達，工件序列結束。所有工件都被分配后，在等級約束下，無論是否重排，都有CA≥3，COPT=2，CA/COPT≥3/2。

情形3.2J2=(2,1)被分配給M2，與情形3.1類似。

因此，有CA/COPT≥3/2，定理3成立。

證畢。

□

4.2 算法A2

(1)迭代階段：

步驟3否則gj=2,

步驟4若還有新工件到達，令j=j+1，返回步驟2。

(2)重排階段：

定理4對于在線問題P3(1,1,2)|reassignment|Cmax的在線算法A2，所有工件都被分配后，在等級約束的限制下，僅重排機器M3上的最后一個工件，算法A2的競爭比至多為12/7。

證明對于M3上最后一個工件Jy，處理時間為py，等級為2。分配給Mi的等級為k的工件大小之和表示為Li(k)，i∈{1,2}，k∈{1,2}。

另有L1(1)+L2(1)=T1。由算法A2可知，M1和M2的負載之差不會超過max{pmax,qmax}。因此有：

根據式(5)，得CA2/COPT≤12/7。

情形2若重排會發生，即在迭代階段所有工件都被分配之后有:

(6)

先分析M1的負載。

先分析M1的負載:

再分析M2的負載:

證畢。

□

5 結束語

對于3臺等級機器上帶重排的半在線排序問題，本文研究了帶重排的2種等級情形：第1種是P3(1,2,2)|reassignment|Cmax，給出了一個競爭比下界為3/2，并提出了一個競爭比至多為5/3的在線算法;第2種是P3(1,1,2)|reassignment|Cmax，給出了一個競爭比下界為3/2，提出了一個競爭比至多為12/7的在線算法。未來將致力于設計最優算法。