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

杜豫菲

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

1 引言

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

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

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

在前人的研究基礎上，本文主要討論了等級調(diào)度情況下的兩臺平行機上的三個半在線調(diào)度問題。該問題模型為工作環(huán)境為處理速度相同的兩臺平行機M1和M2，工件被劃分為兩個等級gj=1和gj=2。機器M1只能處理等級gj=1的工件，機器M2即能處理等級gj=1的工件，也能處理等級gj=2的工件。三個半在線問題都在等級gj=1工件總處理時間已知的前提下，各自分別還知道：1）算法最優(yōu)的處理時間，即Copt已知；2）工件中最大的處理時間，即pmax已知；3）算法最優(yōu)的處理時間和工件中最大的處理時間，即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的工件有多少或者有多大及到來順序?qū)栴}本身沒有實質(zhì)的影響。故本文只考慮最大處理時間的等級gj=2的情況。

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

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

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

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

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

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

算法LS［17］

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

步驟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上。第一個工件集為；第二個工件集為以上兩個工件集都能通過離線算法達到最優(yōu)，且最優(yōu)處理時間為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，結(jié)束；否則執(zhí)行步驟3；

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

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

證明

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

1）如果T1=Copt，則最優(yōu)。

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；否則，執(zhí)行步驟2；

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

步驟3若j

步驟4用具有服務等級的LS算法［14］進行調(diào)度；結(jié)束。

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

證明

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

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

（1）若M1≤pmax，那么CPLS=pmax，此時最優(yōu)。

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

2）0

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

（2）當M2≥pmax時，有即

即

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

（2）M2?M1≤pmax。結(jié) 合得

5 P2| opt&max&T1 |Cmax

前兩節(jié)已經(jīng)對最優(yōu)處理時間和最大處理時間分別已知的半在線問題進行了討論。這一節(jié)，對以上兩種已知條件組合在一起的半在線問題進行討論。對于的半在線問題。已知信息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）?？傻酶偁幈萊大于等于

（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；結(jié)束。

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

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

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

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

步驟10若j

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

證明

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

（1）有工件pj滿足

或

和

6 結(jié)語