劉輝冉,馬 冉

(河南理工大學 數(shù)學與信息科學學院，河南 焦作 454000)

0 引言

在經(jīng)典的調度問題中，工件的加工時間通常是一個確定的常數(shù).但是，在實際問題中，工件的加工時間可能是一個隨機變量，所以有必要考慮帶有隨機信息的排序問題.帶有隨機信息的調度問題由DANTZIG[1]和BEALE[2]首先提出，他們假設所給實例中的某些數(shù)據(jù)并不是預先給定的確定常數(shù)，而是服從某種概率分布的隨機變量.

本文重點考慮工件的加工時間是隨機變量的排序問題，即工件加工時間的期望是關于工件的開工時刻和退化率的簡單線性函數(shù)，我們通常把這類問題稱為簡單線性退化工件的隨機調度問題.

GUPTA[3]首先提出了具有退化效應工件的調度問題.MOSHEIOV[4]討論了工件的加工時間是開工時刻的簡單線性增加函數(shù)的單機排序問題，其目標函數(shù)是最小化完工時間和，并給出了最好可能的SDR算法.注意到SDR算法也是一個在線列表算法，但是此算法對在線問題來說不是一個最好可能的算法.VESTJENS[5]證明了平行機上的確定性在線問題不存在競爭比小于1.309的算法，并證明了可中斷情形下的在線問題不存在競爭比小于22/21的算法.CHENG等[6]證明了機器可拒絕具有退化效應工件的排序問題是NP-hard的.NG等[7]證明了簡單線性退化工件在單機上進行可中斷排序且目標是最小化工件加權總完工時間和的在線調度問題是NP-hard的.因此，這類問題的不可中斷情形亦是NP-hard的.而LIU等[8] 對可退化工件的確定性在線排序問題1|online,rj≥t0,pj=bjSj|∑Cj給出了競爭比為1+bmax的最好可能的在線D-SGR算法.在2015年，劉其佳和馮琪[9]研究了單機上考慮運輸?shù)耐嘶ぜ脑诰€排序問題，即1→D|online,rj≥t0,pj=ajt,v=1,c=|Dmax，其中表示工件的最大運輸完工時間，給出了最好可能的競爭比為1+α的在線算法D.MA等[10]研究了問題1|online,rj≥t0,pj=αj(A+BSj)|∑wjCj，對LIU等在文獻[8]中探究的問題進行了推廣，并且給出了競爭比為1+λ(A)+αmaxB的最好可能的DSWGR算法.CHEKURI等[11]對同型機上的在線調度問題進行了研究，即并給出了競爭比為3-1/m的在線算法.WAGNER等[12]利用線性規(guī)劃方法給出了競爭比為2.618的算法，MEGOW等[13]對其可中斷情形給出了競爭比為2的在線算法.MA和YUAN[14]對單機上具有拒絕權利的在線調度問題給出了競爭比為2的最好可能的在線算法.隨后，他們[15]將此類問題推廣到了平行機上，并對同型機和同類機上的情形分別給出了競爭比至多是4+ε和8的在線算法.

的1-SEPT算法.顧滿占和魯習文[19]討論了同類機上的隨機在線排模型，給出了競爭比為

然而，關于簡單線性退化工件的隨機在線調度問題，目前幾乎沒有任何研究進展.本文對簡單線性退化工件在單機上的隨機在線調度問題進行了研究，并對該問題給出了一個競爭比為1+bmax的SHIFT-SDR算法.LIU等[8]所研究的問題是我們所研究問題的一個特例，因此本文給出的SHIFT-SDR算法是最好可能的在線算法.

1 問題描述

設有一個工件集J={J1,J2,…,Jn}，其中的n個工件均以時間在線的方式到達，只有工件Jj到達之后，決策者才知道工件的釋放時刻rj≥t0(t0>0)，退化率bj(bj>0)及加工時間的期望E[Pj]，且工件加工時間的期望依賴于工件的開工時間，即E[Pj]=bjSj.由于工件加工時間的期望與其開工時間有關，因此直到工件完工之后排序者才知道隨機變量Pj的一個實現(xiàn)值.目標是最小化工件總完工時間的期望，三參數(shù)法表示為1|online,rj≥t0,E[Pj]=bjSj|E[∑Cj].

引理1[8]對于問題1|online,rj≥t0,Pj=bjSj|∑Cj，任意確定性在線算法的下界不會好于1+bmax.

2 算法及其分析

2.1 SHIFT-SDR算法

步驟2：根據(jù)修正后的釋放時刻，在任意時刻，如果機器是空閑的，從所有的就緒工件中選擇退化率最小的工件進行加工；

步驟3：如果沒有新工件到達，則算法終止；否則，返回步驟1.

2.2 競爭比分析

給定實例I，I中的工件集為J={J1,J2,…,Jn}，運用SHIFT-SDR算法對實例中的工件進行排序加工，并把得到的排序記為σ.

引理3σ序中僅包含一個單塊，即在第一個加工工件的開工時刻之后，所有的工件進行連續(xù)地無中斷加工.

證明(最小反例法)假設σ序中包含兩個子塊σ1和σ2，顯然σ1和σ2是互不影響的.此時可將實例I劃分為兩個相互獨立的更小的實例I1和I2，即I=I1+I2.假定實例I、I1和I2的最優(yōu)排序分別為π、π1和π2，那么I1和I2中的工件在π中的排序是一個可行排序.記σ、σ1、σ2、π、π1和π2所對應的目標函數(shù)值分別為：C(σ)、C(σ1)、C(σ2)、C*(π)、C*(π1)和C*(π2).通過上述分析，可以得到：

C*(π1)+C*(π2)≤C*(π)，

由引理1的結論，可以得到

又因為

由引理3的結論，我們可以根據(jù)σ序中工件的退化率對σ進行分塊處理(每個子塊之間沒有空閑時間).

假定σ序可分成k(k≥1)個子塊B1,B2,…,Bk，子塊具有以下幾個性質：

性質1 每個子塊中工件以SDR規(guī)則排序，即在每個子塊中，工件根據(jù)退化率進行從小到大的排序；

性質2 相鄰的兩個子塊Bi和Bi+1，1≤i

性質3 令b(i)=min{j>b(i-1)|bj>bj+1}，b0=0，則

Bi={Jb(i-1)+1,Jb(i-1)+2,…,Jb(i)}；

引理4 令E[C*(I)]和E[C*(I(σ))]分別是I和I(σ)在無中斷最優(yōu)排序下的總完工時間的期望，則

E[C*(I(σ))]≤(1+bmax)E[C*(I)].

因此

E[C*(I(σ))]≤(1+bm(i))E[C*(I)]≤

(1+bmax)E[C*(I)].

證畢.

對于實例I，如果中斷被允許，由引理2可知，SRDR是I的最優(yōu)中斷排序.下面就利用此最優(yōu)中斷排序來證明SHIFT-SDR算法的競爭比是1+bmax.

引理5 實例I在SHIFT-SDR算法下得到的排序σ，是實例I(σ)在SRDR算法下的一個排序.

那么

綜合上述兩種情形可知，任意兩個連續(xù)子塊之間也滿足SRDR規(guī)則.因此σ是I(σ)在SRDR算法下的一個排序.證畢.

通過引理5得出：

E[CSHIFT-SDR(I)]=E[CSRDR(I(σ))]≤

E[C*(I(σ))]≤E[C*(I)].

因此定理1成立:

定理1 對隨機在線調度問題1|online,rj≥t0,E[Pj]=bjSj|E[∑Cj]，SHIFT-SDR算法是最好可能的在線算法，其競爭比為1+bmax.

3 結語

本文通過改變就緒工件的釋放時間，對簡單線性退化工件在單機上的隨機在線排序問題設計了一個競爭比為1+bmax的在線算法.這與其在線排序問題的下界相匹配，因此，本文所研究的問題給工件的加工時間服從某個具有概率分布的簡單線性退化工件的隨機在線排序問題提供了一個下界.