單機(jī)上簡(jiǎn)單線性退化工件的隨機(jī)在線調(diào)度問(wèn)題

劉輝冉,馬 冉

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

0 引言

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

本文重點(diǎn)考慮工件的加工時(shí)間是隨機(jī)變量的排序問(wèn)題，即工件加工時(shí)間的期望是關(guān)于工件的開(kāi)工時(shí)刻和退化率的簡(jiǎn)單線性函數(shù)，我們通常把這類(lèi)問(wèn)題稱(chēng)為簡(jiǎn)單線性退化工件的隨機(jī)調(diào)度問(wèn)題.

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

的1-SEPT算法.顧滿占和魯習(xí)文[19]討論了同類(lèi)機(jī)上的隨機(jī)在線排模型，給出了競(jìng)爭(zhēng)比為

然而，關(guān)于簡(jiǎn)單線性退化工件的隨機(jī)在線調(diào)度問(wèn)題，目前幾乎沒(méi)有任何研究進(jìn)展.本文對(duì)簡(jiǎn)單線性退化工件在單機(jī)上的隨機(jī)在線調(diào)度問(wèn)題進(jìn)行了研究，并對(duì)該問(wèn)題給出了一個(gè)競(jìng)爭(zhēng)比為1+bmax的SHIFT-SDR算法.LIU等[8]所研究的問(wèn)題是我們所研究問(wèn)題的一個(gè)特例，因此本文給出的SHIFT-SDR算法是最好可能的在線算法.

1 問(wèn)題描述

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

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

2 算法及其分析

2.1 SHIFT-SDR算法

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

步驟3：如果沒(méi)有新工件到達(dá)，則算法終止；否則，返回步驟1.

2.2 競(jìng)爭(zhēng)比分析

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

引理3σ序中僅包含一個(gè)單塊，即在第一個(gè)加工工件的開(kāi)工時(shí)刻之后，所有的工件進(jìn)行連續(xù)地?zé)o中斷加工.

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

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

由引理1的結(jié)論，可以得到

又因?yàn)?/p>

由引理3的結(jié)論，我們可以根據(jù)σ序中工件的退化率對(duì)σ進(jìn)行分塊處理(每個(gè)子塊之間沒(méi)有空閑時(shí)間).

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

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

性質(zhì)2 相鄰的兩個(gè)子塊Bi和Bi+1，1≤i

性質(zhì)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(σ)在無(wú)中斷最優(yōu)排序下的總完工時(shí)間的期望，則

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

因此

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

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

證畢.

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

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

那么

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

通過(guò)引理5得出：

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

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

因此定理1成立:

定理1 對(duì)隨機(jī)在線調(diào)度問(wèn)題1|online,rj≥t0,E[Pj]=bjSj|E[∑Cj]，SHIFT-SDR算法是最好可能的在線算法，其競(jìng)爭(zhēng)比為1+bmax.

3 結(jié)語(yǔ)

本文通過(guò)改變就緒工件的釋放時(shí)間，對(duì)簡(jiǎn)單線性退化工件在單機(jī)上的隨機(jī)在線排序問(wèn)題設(shè)計(jì)了一個(gè)競(jìng)爭(zhēng)比為1+bmax的在線算法.這與其在線排序問(wèn)題的下界相匹配，因此，本文所研究的問(wèn)題給工件的加工時(shí)間服從某個(gè)具有概率分布的簡(jiǎn)單線性退化工件的隨機(jī)在線排序問(wèn)題提供了一個(gè)下界.