任立莉, 李 娅, 李 阳

(郑州大学数学系 河南郑州450001)

工件可拒绝平行机排序

任立莉, 李 娅, 李 阳

(郑州大学数学系 河南郑州450001)

考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.如果拒绝一个工件,要花费一定的惩罚费用;如果接受这个工件,在m台机器中的一台上分批加工,定义一批的加工时间为这批中所包含的最长工件的加工时间.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.当m是一个给定的数时,给出了这个问题的一个拟多项式时间算法和一个完全多项式时间近似方案.

排序;拒绝费用;完全多项式时间近似算法

0 引言

我们考虑工件有到达时间并且可拒绝的m台无界平行批处理机最小化最大完工时间的排序问题.这个问题的描述如下:有m台无界平行批处理机,n个工件J1,…,Jn,每个工件Jj的长度、到达时间、拒绝费用分别记为pj,rj,wj>0,每一个工件Jj或者被拒绝承担拒绝费用wj>0,或者接受并在m台机器中的一台上分批加工,一般情况下,分批加工有一个批容量b,这意味着每批至多加工b个工件.本文中假定b=∞,即批容量是无界的,定义一批的加工时间为这批中最长的工件的加工时间.在同一批的工件有相同的开工时刻和相同的完工时刻.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和,令V是所有被拒绝工件的拒绝费用之和.用文[1]引入的排序问题一般的记法,这个问题可以记为

在最近10年的文献中,平行批排序得到了广泛的研究.这个问题的基本模型由文[2]引入,其中每批的工件数目由b限定,这个有界模型受到半导体加工启发,文[3]给出了平行批排序无界情况下的推广,这个题目的近期发展可以在网络节点中找到.除此之外,对有到达时刻的平行批排序问题文[4-7]给出了一些新的复杂结论和近似算法.

可以拒绝的机器排序问题首先是由文[8]引入的,他们研究了恒同机的离线和在线情况.目标函数是最小化接受工件的最大完工时间与拒绝工件的费用之和.如果允许工件中断,文[9]给出了一个较好的在线算法.文[10]考虑允许中断、离线、可拒绝的多台处理机问题.文[11]研究可拒绝的单机排序问题,其中目标函数是排在机器上的工件的加权最大完工时间加上所有拒绝工件的费用,使两者之和最小.文[12]研究可拒绝单位工件的在线排序问题,其中目标函数是最小化完工时间之和.

Aj(k,W)是下面排序问题的最优目标函数值:(1)在考虑范围里的工件是J1,…,Jj;(2)Jj接受;(3)在最后一批中,Jk是最小标号的工件;(4)全部的拒绝费用恰好是W.

Rj(k,W)是下面排序问题的最优目标函数值:(1)在考虑范围里的工件是J1,…,Jj;(2)Jj拒绝;(3)在最后一批中,Jk是最小标号的工件;(4)全部的拒绝费用恰好是W.

进一步,设计动态规划递归计算Aj(k,W)和Rj(k,W)的所有值.最后,问题的最优值由min{min(An(k,W),Rn(k,W)):0≤k≤n,0≤W≤给出.因此,这个问题可以在O(n2)时间内解决.

1 动态规划算法

对于排序π,如果对任意两个接受的工件Ji和Jj,pi>pj意味着在π下,Ji的加工时间不比Jj晚,则认为接受的工件在π下是按照LPT规则排序的.

引理1[13]问题Pm p-batch,rjCmax+V,存在一个最优排序,使得接受的工件按LPT原则排在机器上,即,如果Ji和Ji是两个接受工件且pi≥pj,那么Ji的开工时刻不比Jj晚.

在引理1的基础上,只要考虑接受工件按LPT规则排的序列,称这样的序列为LPT序.假设工件按照p1≥…≥pn标号,首先引入一个有用的记号,用Vj(k1,…,km,C(1),…,C(m))表示满足下面条件的被拒绝工件的最小拒绝费用和:

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

(2)工件按LPT规则排在m台机器上:

(3)最后一批排在机器i上,Jki具有最小标号的工件,其中1≤i≤m;

(4)C(i)是在机器i上最后一批的完工时间,其中1≤i≤m.

假定工件J1,…,Jj的LPT排序π满足Vj(k1,…,km,C(1),…,C(m)),S(i)=C(i)-pki是机器i上最后一批的开工时刻,1≤i≤m.在第i台机器没有被加工的批次时,令ki=0,pki=0,且S(i)=C(i)=0.进一步,如果没有LPT序满足条件(1)和(4),令Vj(k1,…,km,C(1),…,C(m))=∞.

如果存在i∈{1,…,m}使得rj≤S(i)且pj≤pki,那么Jj在π下是接受的,因为Jj可以被包含在机器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)).

如果对任意i∈{1,…,m),有rj>S(i)或pj>pki,那么Jj一定被拒绝,因为Jj不能在任意一台机器中的最后一批中加工.在这种情况下,有Vj(k1,…,km,C(1),…,C(m))=Vj-1(k1,…,km,C(1),…,C(m))+wj.

根据以上的讨论,计算Vj(k1,…,km,C(1),…,C(m))的动态规划算法,这里称为DPA(m),可以描述为:边界条件:

这里,假定J0是一个虚拟工件,其中,r0=p0=0.

递归函数:

这里,

且

定理1的动态规划算法DPA(m)的时间界是,这里且

证明在表达式中,每个C(i)由界定.因此,至多有种情况.除了特殊循环ki=j对某个i∈{1,…,m},每个循环的计算都可以在常数时间内完成.这种特殊循环至多有个,且每个循环需要的时间界至多是O(n(rmax+pmax)).总之,动态规划算法的计算复杂性是

证毕.

注意,在算法DPA(m)的运行中,(rmax+pmax)的值可以由最优排序中接受工件的完工时刻的上界代替.

2 近似算法

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

步骤1对任意的t∈{rj:j=1,…,n}和p∈{pj:j=1,…,n},把工件划分为两个集合,使得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时刻以一批加工,这样得到的排序记为π(t,p).

步骤3设Z(t,p)是每个π(t,p)的目标函数值,在上面得到的所有排序中,选Z(t,p)值最小的排序.

设π是由上面的近似算法得到的排序.设Z和Z＊分别是排序π和最优排序π＊的目标函数值.

定理2Z≤2Z＊.

证明设A＊和R＊分别是π＊下的接受工件集和拒绝工件集.设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＊.

证毕.

设Z是上面近似算法的目标函数值,Z＊是最优值.由[13]定理3.1,有Z＊≤Z≤2Z＊.对任意工件Jj且wj>Z,易得Jj∈A＊.否则,得到Z＊≥wj>Z≥Z＊,矛盾.如果修改工件Jj的拒绝费用,重新设定wi=Z,最优目标值不会改变.因此,不失一般性,假定wj≤Z,其中,j=1,…,n.现在,对于上面考虑的问题,将介绍一个完全多项式时间近似方案Aε(m).

完全多项式时间近似方案Aε(m)步骤如下:

步骤1对任意ε>0,设对给定的实例I,定义一个新的实例I′,新实例通过舍入实例I中工件的到达时刻和加工时间,使得,其中,j=1,…,n.

步骤2对实例I′应用动态规划算法DPA(m),从而得到实例I′的最优序π＊(I′).

步骤3对每一个j=1,…,n,用初始到达时刻rj和初始加工时间pj分别代替π＊(I′)中修改的到达时刻和加工时间,从而得到实例Ι的可行解π.

设Zε是排序π的目标值,有定理3.

定理3Zε≤(1+ε)Z＊且Aε(m)的运行时间是

证明 Z＊(I′)是排序π＊(I′)的最优目标值.由Aε的步骤1,对每一个Jj,有且,因此Z＊(I′)≤Z＊.用rj和pj分别代替和,这里j=1,…,n.我们得到

这里,不等式由以下事实得到,每台机器至多加工n-1批,且由修改到达时刻和加工时间而引起的完工时刻的推迟至多为M+(n-1)M.

注意到,每个工件的到达时刻和加工时间是M的倍数.因为Z是实例I的最优值的上界,所以它也是实例I′的最优值的上界.特别的,Z是实例I′在最优排序中接受工件的完工时刻的上界.因此,当对实例I′运行算法DPA(m)时,可以用Z=(2n/ε)M做每个状态变量C(i)的上界.所以每个状态变量C(i)有至多(1+2n/ε)个选择,分别是0,M,2M,…,(2n/ε)M.总之,Aε(m)运行时间的上界是

证毕.

由上面的讨论,我们建立了问题Pm p-batch,rjCmax+V的一个完全多项式时间近似方案.所以,问题Pmp-batch,rjCmax+V有完全多项式时间近似方案.到现在为止,问题Pm p-batch,rjCmax+V的复杂性仍然是有待解决的.

[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-),女,硕士研究生,主要从事在线多台机器的分批排序问题研究,E-mail:lily8461@126.com.