工件可拒絕平行機(jī)排序

任立莉, 李 婭, 李 陽(yáng)

(鄭州大學(xué)數(shù)學(xué)系 河南鄭州450001)

工件可拒絕平行機(jī)排序

任立莉, 李 婭, 李 陽(yáng)

(鄭州大學(xué)數(shù)學(xué)系 河南鄭州450001)

考慮工件有到達(dá)時(shí)間并且可拒絕的m臺(tái)無界平行批處理機(jī)最小化最大完工時(shí)間的排序問題.如果拒絕一個(gè)工件,要花費(fèi)一定的懲罰費(fèi)用;如果接受這個(gè)工件,在m臺(tái)機(jī)器中的一臺(tái)上分批加工,定義一批的加工時(shí)間為這批中所包含的最長(zhǎng)工件的加工時(shí)間.目標(biāo)函數(shù)是最小化接受工件的最大完工時(shí)間與拒絕工件的費(fèi)用之和.當(dāng)m是一個(gè)給定的數(shù)時(shí),給出了這個(gè)問題的一個(gè)擬多項(xiàng)式時(shí)間算法和一個(gè)完全多項(xiàng)式時(shí)間近似方案.

排序;拒絕費(fèi)用;完全多項(xiàng)式時(shí)間近似算法

0 引言

我們考慮工件有到達(dá)時(shí)間并且可拒絕的m臺(tái)無界平行批處理機(jī)最小化最大完工時(shí)間的排序問題.這個(gè)問題的描述如下:有m臺(tái)無界平行批處理機(jī),n個(gè)工件J1,…,Jn,每個(gè)工件Jj的長(zhǎng)度、到達(dá)時(shí)間、拒絕費(fèi)用分別記為pj,rj,wj>0,每一個(gè)工件Jj或者被拒絕承擔(dān)拒絕費(fèi)用wj>0,或者接受并在m臺(tái)機(jī)器中的一臺(tái)上分批加工,一般情況下,分批加工有一個(gè)批容量b,這意味著每批至多加工b個(gè)工件.本文中假定b=∞,即批容量是無界的,定義一批的加工時(shí)間為這批中最長(zhǎng)的工件的加工時(shí)間.在同一批的工件有相同的開工時(shí)刻和相同的完工時(shí)刻.目標(biāo)函數(shù)是最小化接受工件的最大完工時(shí)間與拒絕工件的費(fèi)用之和,令V是所有被拒絕工件的拒絕費(fèi)用之和.用文[1]引入的排序問題一般的記法,這個(gè)問題可以記為

在最近10年的文獻(xiàn)中,平行批排序得到了廣泛的研究.這個(gè)問題的基本模型由文[2]引入,其中每批的工件數(shù)目由b限定,這個(gè)有界模型受到半導(dǎo)體加工啟發(fā),文[3]給出了平行批排序無界情況下的推廣,這個(gè)題目的近期發(fā)展可以在網(wǎng)絡(luò)節(jié)點(diǎn)中找到.除此之外,對(duì)有到達(dá)時(shí)刻的平行批排序問題文[4-7]給出了一些新的復(fù)雜結(jié)論和近似算法.

可以拒絕的機(jī)器排序問題首先是由文[8]引入的,他們研究了恒同機(jī)的離線和在線情況.目標(biāo)函數(shù)是最小化接受工件的最大完工時(shí)間與拒絕工件的費(fèi)用之和.如果允許工件中斷,文[9]給出了一個(gè)較好的在線算法.文[10]考慮允許中斷、離線、可拒絕的多臺(tái)處理機(jī)問題.文[11]研究可拒絕的單機(jī)排序問題,其中目標(biāo)函數(shù)是排在機(jī)器上的工件的加權(quán)最大完工時(shí)間加上所有拒絕工件的費(fèi)用,使兩者之和最小.文[12]研究可拒絕單位工件的在線排序問題,其中目標(biāo)函數(shù)是最小化完工時(shí)間之和.

Aj(k,W)是下面排序問題的最優(yōu)目標(biāo)函數(shù)值:(1)在考慮范圍里的工件是J1,…,Jj;(2)Jj接受;(3)在最后一批中,Jk是最小標(biāo)號(hào)的工件;(4)全部的拒絕費(fèi)用恰好是W.

Rj(k,W)是下面排序問題的最優(yōu)目標(biāo)函數(shù)值:(1)在考慮范圍里的工件是J1,…,Jj;(2)Jj拒絕;(3)在最后一批中,Jk是最小標(biāo)號(hào)的工件;(4)全部的拒絕費(fèi)用恰好是W.

進(jìn)一步,設(shè)計(jì)動(dòng)態(tài)規(guī)劃遞歸計(jì)算Aj(k,W)和Rj(k,W)的所有值.最后,問題的最優(yōu)值由min{min(An(k,W),Rn(k,W)):0≤k≤n,0≤W≤給出.因此,這個(gè)問題可以在O(n2)時(shí)間內(nèi)解決.

1 動(dòng)態(tài)規(guī)劃算法

對(duì)于排序π,如果對(duì)任意兩個(gè)接受的工件Ji和Jj,pi>pj意味著在π下,Ji的加工時(shí)間不比Jj晚,則認(rèn)為接受的工件在π下是按照LPT規(guī)則排序的.

引理1[13]問題Pm p-batch,rjCmax+V,存在一個(gè)最優(yōu)排序,使得接受的工件按LPT原則排在機(jī)器上,即,如果Ji和Ji是兩個(gè)接受工件且pi≥pj,那么Ji的開工時(shí)刻不比Jj晚.

在引理1的基礎(chǔ)上,只要考慮接受工件按LPT規(guī)則排的序列,稱這樣的序列為L(zhǎng)PT序.假設(shè)工件按照p1≥…≥pn標(biāo)號(hào),首先引入一個(gè)有用的記號(hào),用Vj(k1,…,km,C(1),…,C(m))表示滿足下面條件的被拒絕工件的最小拒絕費(fèi)用和:

(1)考慮的工件是J1,…,Jj;

(2)工件按LPT規(guī)則排在m臺(tái)機(jī)器上:

(3)最后一批排在機(jī)器i上,Jki具有最小標(biāo)號(hào)的工件,其中1≤i≤m;

(4)C(i)是在機(jī)器i上最后一批的完工時(shí)間,其中1≤i≤m.

假定工件J1,…,Jj的LPT排序π滿足Vj(k1,…,km,C(1),…,C(m)),S(i)=C(i)-pki是機(jī)器i上最后一批的開工時(shí)刻,1≤i≤m.在第i臺(tái)機(jī)器沒有被加工的批次時(shí),令ki=0,pki=0,且S(i)=C(i)=0.進(jìn)一步,如果沒有LPT序滿足條件(1)和(4),令Vj(k1,…,km,C(1),…,C(m))=∞.

如果存在i∈{1,…,m}使得rj≤S(i)且pj≤pki,那么Jj在π下是接受的,因?yàn)镴j可以被包含在機(jī)器i的最后一批中.于是,如果ki≤j-1,有Vj(k1,…,km,C(1),…,C(m))=Vj-1(k1,…,km,C(1),…,C(m)).

如果ki=j,則

這里,(k1,…,h,…,km)=(k1,…,ki-1,h,ki+1,…,km),且(C(1),…,D,…,C(m))=(C(1),…,C(i-1),D,Ci+1,…,C(m)).

如果對(duì)任意i∈{1,…,m),有rj>S(i)或pj>pki,那么Jj一定被拒絕,因?yàn)镴j不能在任意一臺(tái)機(jī)器中的最后一批中加工.在這種情況下,有Vj(k1,…,km,C(1),…,C(m))=Vj-1(k1,…,km,C(1),…,C(m))+wj.

根據(jù)以上的討論,計(jì)算Vj(k1,…,km,C(1),…,C(m))的動(dòng)態(tài)規(guī)劃算法,這里稱為DPA(m),可以描述為:邊界條件:

這里,假定J0是一個(gè)虛擬工件,其中,r0=p0=0.

遞歸函數(shù):

這里,

且

定理1的動(dòng)態(tài)規(guī)劃算法DPA(m)的時(shí)間界是,這里且

證明在表達(dá)式中,每個(gè)C(i)由界定.因此,至多有種情況.除了特殊循環(huán)ki=j對(duì)某個(gè)i∈{1,…,m},每個(gè)循環(huán)的計(jì)算都可以在常數(shù)時(shí)間內(nèi)完成.這種特殊循環(huán)至多有個(gè),且每個(gè)循環(huán)需要的時(shí)間界至多是O(n(rmax+pmax)).總之,動(dòng)態(tài)規(guī)劃算法的計(jì)算復(fù)雜性是

證畢.

注意,在算法DPA(m)的運(yùn)行中,(rmax+pmax)的值可以由最優(yōu)排序中接受工件的完工時(shí)刻的上界代替.

2 近似算法

近似算法A[13]的步驟如下:

步驟1對(duì)任意的t∈{rj:j=1,…,n}和p∈{pj:j=1,…,n},把工件劃分為兩個(gè)集合,使得S1(t,p)= {Jj:rj≤t,pj≤p}且S2(t)={Jj:rj>t或pj>p}.

步驟2接受集合S1(t,p)中的所有工件,并且拒絕集合S2(t,p)中的所有工件,將S1(t,p)中的工件安排在其中一臺(tái)機(jī)器上,并在t時(shí)刻以一批加工,這樣得到的排序記為π(t,p).

步驟3設(shè)Z(t,p)是每個(gè)π(t,p)的目標(biāo)函數(shù)值,在上面得到的所有排序中,選Z(t,p)值最小的排序.

設(shè)π是由上面的近似算法得到的排序.設(shè)Z和Z＊分別是排序π和最優(yōu)排序π＊的目標(biāo)函數(shù)值.

定理2Z≤2Z＊.

證明設(shè)A＊和R＊分別是π＊下的接受工件集和拒絕工件集.設(shè)r＊=max{rj:Jj∈A＊},p＊=max{pj: Jj∈A＊}.由r＊和p＊的定義,有S2(r＊,p＊)={Jj:rj>r＊或pj>p＊}?R＊.那么有Z＊≥max{r＊,p＊}+ w(S2(r＊,p＊)).因此,得到Z≤Z(r＊,p＊)=r＊+p＊+w(S2(r＊,p＊))≤2Z＊.

證畢.

設(shè)Z是上面近似算法的目標(biāo)函數(shù)值,Z＊是最優(yōu)值.由[13]定理3.1,有Z＊≤Z≤2Z＊.對(duì)任意工件Jj且wj>Z,易得Jj∈A＊.否則,得到Z＊≥wj>Z≥Z＊,矛盾.如果修改工件Jj的拒絕費(fèi)用,重新設(shè)定wi=Z,最優(yōu)目標(biāo)值不會(huì)改變.因此,不失一般性,假定wj≤Z,其中,j=1,…,n.現(xiàn)在,對(duì)于上面考慮的問題,將介紹一個(gè)完全多項(xiàng)式時(shí)間近似方案Aε(m).

完全多項(xiàng)式時(shí)間近似方案Aε(m)步驟如下:

步驟1對(duì)任意ε>0,設(shè)對(duì)給定的實(shí)例I,定義一個(gè)新的實(shí)例I′,新實(shí)例通過舍入實(shí)例I中工件的到達(dá)時(shí)刻和加工時(shí)間,使得,其中,j=1,…,n.

步驟2對(duì)實(shí)例I′應(yīng)用動(dòng)態(tài)規(guī)劃算法DPA(m),從而得到實(shí)例I′的最優(yōu)序π＊(I′).

步驟3對(duì)每一個(gè)j=1,…,n,用初始到達(dá)時(shí)刻rj和初始加工時(shí)間pj分別代替π＊(I′)中修改的到達(dá)時(shí)刻和加工時(shí)間,從而得到實(shí)例Ι的可行解π.

設(shè)Zε是排序π的目標(biāo)值,有定理3.

定理3Zε≤(1+ε)Z＊且Aε(m)的運(yùn)行時(shí)間是

證明 Z＊(I′)是排序π＊(I′)的最優(yōu)目標(biāo)值.由Aε的步驟1,對(duì)每一個(gè)Jj,有且,因此Z＊(I′)≤Z＊.用rj和pj分別代替和,這里j=1,…,n.我們得到

這里,不等式由以下事實(shí)得到,每臺(tái)機(jī)器至多加工n-1批,且由修改到達(dá)時(shí)刻和加工時(shí)間而引起的完工時(shí)刻的推遲至多為M+(n-1)M.

注意到,每個(gè)工件的到達(dá)時(shí)刻和加工時(shí)間是M的倍數(shù).因?yàn)閆是實(shí)例I的最優(yōu)值的上界,所以它也是實(shí)例I′的最優(yōu)值的上界.特別的,Z是實(shí)例I′在最優(yōu)排序中接受工件的完工時(shí)刻的上界.因此,當(dāng)對(duì)實(shí)例I′運(yùn)行算法DPA(m)時(shí),可以用Z=(2n/ε)M做每個(gè)狀態(tài)變量C(i)的上界.所以每個(gè)狀態(tài)變量C(i)有至多(1+2n/ε)個(gè)選擇,分別是0,M,2M,…,(2n/ε)M.總之,Aε(m)運(yùn)行時(shí)間的上界是

證畢.

由上面的討論,我們建立了問題Pm p-batch,rjCmax+V的一個(gè)完全多項(xiàng)式時(shí)間近似方案.所以,問題Pmp-batch,rjCmax+V有完全多項(xiàng)式時(shí)間近似方案.到現(xiàn)在為止,問題Pm p-batch,rjCmax+V的復(fù)雜性仍然是有待解決的.

[1] Graham R L,Lawer E L,Lenstra J K,et al.Op timization and app roximation in deterministic sequencing and scheduling:a survey[J].Annalsof Discrete Mathematics,1979,5:1-15.

[2] Lee C Y,Uzsoy R,Martin-Vega L A.Efficient algo rithm s fo r scheduling semiconductor burn-in operations[J].Operations Research,1992,40(4),764-775.

[3] Brucker P,Gladky A,Hoogeveen H,et al.Scheduling a batching machine[J].Journal of Scheduling,1998,1(1): 31-54.

[4] Cheng T C E,Liu Z H,Yu W C.Scheduling jobsw ith release dates and deadlineson a batching p rocessing machine[J]. IIE Transactions,2001,33(8):685-690.

[5] Deng X T,Zhang Y Z.M inimizing mean response time in batch p rocessing system s[J].Lecture Noteson Computer Science,1999,(1627):231-240.

[6] Lee C Y,Uzsoy R.M inimizingmakespan on a single batch p rocessingmachine w ith dynamic job arrivals[J].International Journal of Production Research,1999,37(1):219-236.

[7] Liu Z H,Yuan Jinjiang,Cheng T C E.On scheduling an unbounded batch machine[J].Operations Research Letters, 2003,31(1):42-48.

[8] Bartal Y,Leonardi S,Spaccamela A M,et al.M ultip rocessor scheduling w ith rejection[J].SIAM Journal on Discrete Mathematics,2003,13(1):64-78.

[9] Seiden SS.Preemp tivemultip rocessor scheduling w ith rejection[J].Theoretical Computer Science,2001,262(1/2):437-458.

[10] Hoogeveen H,Skutella M,Woeginger GJ.Preemp tive scheduling w ith rejection[J].Mathematics Programming,2003, 94(2/3):361-374.

[11] Engels D W,Karger D R,Kolliopoulos S G,et al.Techniques fo r scheduling w ith rejection[J].Journal of Algorithm s, 2003,49(1):175-191.

[12] Epstein L,Noga J,Woeginger GJ.On-line scheduling of unit time jobs with rejection:minimizing the total completion time[J].Operations Research Letters,2002,30(6):415-420.

[13] Lu Lingfa,Zhang Liqi,Yuan Jinjiang.The unbounbed parallel batch scheduling w ith release dates and rejection to minimizemakespan[J].Theoretical Computer Science,2008,396(1/2/3),283-289.

The Scheduling on Parallel Batch with Job-rejection

REN Li-li1, L I Ya1, L I Yang
(Department of M athem atics,Zhengzhou University,Zhengzhou 450001,China)

It is considered the scheduling on m unbounded parallel batch matchines w ith release dates and rejections of jobs.A job is either rejected w ith a certain penalty having to be paid,or accep ted and p rocessed in batcheson one of the m machines.The p rocessing time of a batch is defined as the longest p rocessing time of the jobs contained in it.The objective is to minimize the sum of the makespan of the accep ted jobs and the total rejection penalty of the rejected jobs. When m is a fixed number,a pseudo-polynomial-time algorithm and a fully polynomial-time app roximation scheme are p rovided fo r the p roblem.

scheduling;rejection penalty;fully polynomial-time app roximation scheme

O 223

A

1671-6841(2010)03-0015-04

2009-12-01

任立莉(1984-),女,碩士研究生,主要從事在線多臺(tái)機(jī)器的分批排序問題研究,E-mail:lily8461@126.com.