兩臺等級平行機上部分處理時間已知的半在線調度?

杜豫菲

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

1 引言

“半在線”是一種所謂特殊的“在線”。一般地，“在線”調度是指工件一個個到達，一旦到達就必須安排加工，而且工件一旦分給某臺機器處理就不允許改變。而半在線是在第一個工件到達前就預先知道工件的部分信息，比如工件的最大處理時間、任務的總處理時間等［1］。設I為某調度問題的一個實例，對于一個在線或者半在線算法A，CA(I)記為算法A對實例I的調度時間，Copt(I)則指算法對相應問題離線情況的最優目標值，我們把CA(I)/Copt(I)稱為算法A的競爭比，將其記為R［2~3］。競爭比是刻畫一個算法優劣的重要參考依據。而等級調度（GoS）在服務行業中較為常見。等級調度將工件劃分為不同等級，對不同等級的工件進行不同的處理。企業通過等級調度，為不同需求或等級的客戶提供差異化服務，不僅可以提高自身的服務效率，也可以提升客戶消費體驗［4］。現實生活中，高速收費站車道被劃分為ETC車道，綠色通道和普通車道就是進行等級調度的一個實例。接下來，我們將分別介紹在半在線調度領域和等級調度領域的一些成果。為了描述方便，本文用三參數表示法來表示問題，如，表示在兩臺機器的工作環境下，si為半在線問題提前已知的信息，目標函數是使總處理時間盡可能小。

關于半在線調度問題的研究十分豐富。在1997年，Kellerer和Kotov等［5］考慮提前已知所有工件的總處理時間的半在線問題，得到已知總處理時間在任何算法下競爭比都大于等于，并得到相應的最優算法競爭比R可到達。Azar和Re?gev［6］于2001年在中指出，一個已知最優處理時間的半在線問題可以等價于一個背包數目確定，背包具有拉升系數的bin-stretching問題。bin-stretch?ing問題在兩臺機器下的拉升系數為。更進一步，對于兩臺或者更多的機器，任何確定的算法的拉升系數大于等于［6］。He和Zhang［7］在1999年證明了兩臺平行機工作環境時最大處理時間已知的情況，該情況下最優的半在線算法為PLS算法，其競爭比與上兩個情況相同，也是。Zhang和Ye［8］在1999年證明了當最后一個工件處理時間最大的情況，算法競爭比可以到達當工件的處理時間是的等比數列時，競爭比一定不超過2k［9］。同樣地，一些已知信息相互搭配的半在線調度問題也已被研究。例如：在2002年Tan和He證明了總處理時間已知和工件最大處理時間已知情況下，有SM算法使得競爭比為；工件集合是一個不遞增的序列，且已知總處理時間在任何算法下的競爭比R大于等于，并有最優的算法——SD算法競爭比為；以上這兩種組合情況Tan和He［10］給出了具體的證明。

在等級調度領域，我們從離線、在線和半在線三個方面來介紹，由于是NP-難問題，我們關注近似算法來解決這一類問題［11］。離線情況下，Hwang等［12］在2004年第一次研究了多臺平行機工作環境下的等級調度問題，并提出了一種近似算法，該算法在兩臺機器時可以使競爭比不超過，當機器數大于兩臺時，競爭比R可達2?1/(m?1)，其中m是機器數。對于在線的問題，Bar-Noy等［13］考慮了一個相似的模型，并給出該模型的一個近似算法，該算法競爭比為e+1。半在線的等級調度問題也有大量的研究。例如：2015年Chen等［15］研究了等級調度和提前已知部分信息組合的情況；當提前已知最優處理時間和工件最長處理時間，無論是在的競爭比都分別是

在前人的研究基礎上，本文主要討論了等級調度情況下的兩臺平行機上的三個半在線調度問題。該問題模型為工作環境為處理速度相同的兩臺平行機M1和M2，工件被劃分為兩個等級gj=1和gj=2。機器M1只能處理等級gj=1的工件，機器M2即能處理等級gj=1的工件，也能處理等級gj=2的工件。三個半在線問題都在等級gj=1工件總處理時間已知的前提下，各自分別還知道：1）算法最優的處理時間，即Copt已知；2）工件中最大的處理時間，即pmax已知；3）算法最優的處理時間和工件中最大的處理時間，即Copt，pmax同時已知。目標是總處理時間盡可能小。

2 準備工作

模型中有兩臺平行機M1和M2，兩臺機器處理速度相同。機器M1只能處理等級gj=1的工件，機器M2能處理等級gj=1和gj=2的工件。

處理思路：等級gj=1的工件只能在第一臺機器M1上處理，我們已知等級gj=1工件總處理時間，故在第一臺機器M1上預留出等級gj=1的工件的總處理時間，這樣無論等級gj=1的工件何時到達，都不影響機器M1對它的處理，也平衡了資源的利用。在后兩個模型中，我們默認最大處理時間的工件為等級gj=2的工件，因為等級gj=1的工件自然分配到第一臺機器M1上，機器M1也為其留出了處理時間，所有等級gj=1的工件有多少或者有多大及到來順序對問題本身沒有實質的影響。故本文只考慮最大處理時間的等級gj=2的情況。

文章討論的三種半在線問題均在等級gj=1的工件的總處理時間已知的前提下進行，其中，每個半在線問題分別還知道的信息：1）最優處理時間，即已知Copt；2）工件的最大處理時間，即已知pmax；3）以上兩種搭配組合的情況，即已知Copt和pmax。

Mi：當前狀態下第i臺機器的負載；

T1：等級gj=1的工件的處理時間之和；

Sj：當第j項工件被處理時，第二臺機器上等級gj=2的工件的總處理時間；

pmax：工件中最大的處理時間；：工件中處理時間最大的第一個工件；工件中等級gj=2的最后一個工件的處理時間。

以下算法在后面的算法中應用到。

算法LS［17］

步驟1若gj=1，則將該工件分配給M1；否則，執行第二步；

步驟2如果Sj?1+T1≤M2，則將工件pj分配給M1；否則分配給M2；

步驟3若j

3 P2| opt&T1 |Cmax

定理3.1問題的競爭比R大于等于

證明

假設等級gi=1的總處理時間T1=1，Copt=3。默認將等級gi=1的工件安排到機器M1上。第一個工件集為；第二個工件集為以上兩個工件集都能通過離線算法達到最優，且最優處理時間為3。假設一個確定算法接受到了兩個工件的處理時間為1。

1）第一個工件默認分配到機器M1，第二個工件分配到機器M2，第三個工件為（3，2）時，無論將其分配到任何一臺機器，該算法的競爭比都是

2）將前兩個工件（1，1）（1，2）都安排到機器M1上，剩下的兩個工件可以安排到同一臺機器或者不同的機器，但無論哪種情況下算法的競爭比為

我們將bin-stretching問題中的算法［6］進行簡單的推廣，并證明該算法的競爭比小于等于為了方便敘述，稱該算法為OT算法。

算法1 OT

步驟1如果gj=1，將該工件分配給機器

M1；

步驟2如果T1=Copt，將所有的gj=2的工件安排給機器M2，結束；否則執行步驟3；

步驟3如果Sj?1+T1≥Copt，將j及之后所有gj=2的工件分配給機器M2；

定理3.2算法OT的競爭比小于等于

證明

分以下兩種情況進行討論：

1）如果T1=Copt，則最優。

2）如果T1

4 P2| max&T1 |Cmax

這一部分，我們討論等級gj=1的總處理時間和工件中最大處理時間已知的半在線問題。當最大處理時間的工件的等級gj=1時，可以將該問題考慮為只知道等級gj=1的總處理時間的半在線問題，其競爭比R大于等于故，以下只考慮最大處理時間的工件等級gj=2的情況。

定理4.1問題在任何算法下的競爭比R大于等于

證明

假設pmax=2，T1=1。

1）算法將前兩個工件（1，1）（1，2）分配到兩臺機器上，工件（2，2）無論分配到哪里臺機器上，競爭比R都是

2）算法是將前兩個工件（1，1）（1，2），安排在機器M1上，緊接著的兩個工件具有相同的處理時間2，即為工件（2，2）（2，2），無論將這兩個工件安排到哪一臺機器上進行處理，算法的競爭比R為

算法2 MT

步驟1若gj=1，則將該工件分配給M1；否則，執行步驟2；

步驟2若pj≠pmax或pj+Sj?1+T1≤2pmax時將pj分配給M1，接著執行步驟3；否則將pj分配給M2，接著執行步驟4；

步驟3若j

步驟4用具有服務等級的LS算法［14］進行調度；結束。

定理4.2MT算法的競爭比R小于等于

證明

我們將證明對于任何實例PLS算法的競爭比R小于等于假設pn是實例的最后一個工件，兩臺機器的負載分別為M1和M2。我們討論一下幾種情況。

1）M2=0，即當p0max到達時，還沒有工件分配給M2。pn=pmax。

（1）若M1≤pmax，那么CPLS=pmax，此時最優。

（2）若M1>pmax，則CPLS=M1。又因為算法設計知M1<2pmax，另有因此，可得出

2）0

（1）當M22pmax，有Sl?1+T1>pmax且M2+Sl?1+T1>2pmax。之 后 由 具 有 等 級 的LS算 法進行調度工件到來之前，機器M2的負載一直比機器M1負載與為等級為1的工件預留出的處理時間之和小，并且沒有較大工件到來。因此，算法將安排給機器M2。第一臺機器在pl之后沒有接受任何gj=2的工件。所以，Sl?1+T1≤2pmax且M2+pmax<2pmax。所以有我們結合以上條件可以得到由式（1）和（2）得出

（2）當M2≥pmax時，有即

即

3）M2>M1。在這一情況中我們把分配機器M1。M2≥pmax必然成立，否則Sn?1+T1>pmax。此時第二種情況類似，與假設M2>Sn?1+T1產生矛盾。當Sn?1+T1

（2）M2?M1≤pmax。結 合得

5 P2| opt&max&T1 |Cmax

前兩節已經對最優處理時間和最大處理時間分別已知的半在線問題進行了討論。這一節，對以上兩種已知條件組合在一起的半在線問題進行討論。對于的半在線問題。已知信息s1的情況下的競爭比為c1，已知信息s2的情況下的競爭比為c2，則已知問題s1和s2的同時，競爭比R一定小于等于；若已知信息s1或s2在算法a的情況下的競爭比為ca，則算法a競爭比小于等于為ca［10］。由 此，半在線問題的競爭比一定大于等于

定理5.1P2|opt&max&T1|Cmax問題的競爭比大于等于

證明

假設Copt=5，pmax=3，T1=1。

1）前兩個工件（1，1），（3，2）安排到機器M1上，則令之后工件為（2，2）（2，2，）（2，2），無論之后三個工件如何分配，都可以得到競爭比大于等于

2）若前兩個工件沒有分配到同一臺機器上，即（1，1）安排給第一臺機器，（3，2）安排給機器M2，則討論以下幾種情況：

（1）若第三個工件安排在機器M1上，第四個工件也安排到第機器M1，則第三到最后一個工件依次 是（1，2）、（1，2）、（3，2）、（1，2）。可得競爭比R大于等于

（2）若第三個工件（1，2）依舊安排給機器M1，而第四個工件（1，2）安排給機器M2，則最后兩個工件（2，2）、（2，2），同樣可得競爭比大于等于

（3）若將第三個工件（1，2）安排到機器M2，之后兩個工件為（3，2）、（2，2），無論之后工件怎么分配，都可使得競爭比大于等于

將SM算法［10］進行推廣，得到以下算法，我們將其稱之為OMT算法。

算法3OMT

步驟1若Copt=T1，則將gj=2的工件分配給M2，gj=1的工件分配給M1；結束。

步驟4當gj=1時，將工件給M1，若

步驟5當gj=1時，將工件給M1，若則pj分配給Mi，其余工件分配到另一臺機器上；結束。

步驟6若p0max還沒有到達，和pj分配給Mi，其余的配給令一臺機器，結束。

步驟7若pj≤2Copt?T1或pj=pmax，則將其分配到M1；

步驟10若j

定理5.2P2|opt&max&T1|Cmax問題在算法OMT下的競爭比R小于等于

證明

當Copt=T1和Copt≤pmax≤2Copt時，算法最優。我們討論以下幾種情況。

（1）有工件pj滿足

或

和

6 結語