允许重启的最大化按时完工数的分批在线排序

摘要: 我们考虑允许重启的分批在线排序模型,目标值是最大化按时完工数。就等长工件情形下,当批容量为无限时给出一个竞争比为的在线算法;当批容量有限时给出一个竞争比为的在线算法。

Abstract: We consider on-line batch schedulings to allow restart, the target is to maximize the number of early jobs. We provide an on-line algorithm with a worst-case ratiofor the unbounded model with identical processing times of jobs, and a worst-case ratiofor the bounded model.

关键词:重启;分批;在线;竞争比

Key words: restart;batch;on-line;worst-case radio

中图分类号:TB1;O223文献标识码:A文章编号:1006-4311(2010)14-0141-02

1问题描述

一个算法称为是允许重启的,若一个正在加工的工件(或者批)可以中断在以后重新加工而之前加工过的部分是无效的,即当该工件重新加工时加工时间仍为初始状态。分批排序指机器可以同时加工b个工件,b称为批容量,b=∞和bdj,称t为Jj的误工时刻。本文研究的模型用三参数表示就是:

1│on-line,restarts,p-batch,pj=p│∑Ej

一些相近的结论有:沈灏等人就离线下两台机器情形给出一个近似算法[1];单机无分批时H Hoogeveen等人给出一个1/2的在线算法[2]。邓小铁等人就分批排序模型也给出一些结论[3]。

2主要内容

在线算法A:

第一步:令t=0;

第二步:若Ut=,等待下一个决策时刻,否则转下一步;

第三步:若此时机器空闲,把Ut作为一批开始加工,否则转下一步;

第四步:若│Ut│2│Bt│,中断Bt,把Ut作为一批开始加工,否则继续加工Bt,等待下一个决策时刻转第二步。

我们用I表示一个在线排序实例,令π表示I的一个最优排序,即离线排序。不失一般性,设算法下最终形成的批依次为B1,B2,…,Bm。Si,Ci分别表示Bi的开工和完工时刻,则Si+p=Ci。令B=B1∪B2∪…∪Bm,则A(I)=│B│,记Ki=[Si,Ci),Co表示第一个工件到达时刻,Sm+1=Cm。

观察1:(a):Jj∈I\Bdj

观察2:若Bi是一个正则批,且i2,Sk>Ck-1,则在[Ck-1,Sk)内机器空闲。

引理1:若记Bi是一个推迟批。若i=1,记t0=C0,否则记t0为Ck-1后最早工件的到达时刻。令(t0,Si]内的中断时刻依次为t1,t2,…,tn=Si。则以下结论成立:

(a)tj+1-tj

(c)│U│(1/2n-j)│B│t∈[tj,tj+1),0jn-1

证明:(a),(b)由算法性质可得;由│Q│=│B│及(c)条件下│U│

引理2:令W是实例I的一个子集,W*表示W中的工件在最优排序π下加工的工件集。则OPT(I)OPT(I/W)+│W*│OPT(I/W)+OPT(W)。

证明:最大化问题的任何实例的可行排序都不超过最优排序的目标值,结论自然成立。

引理3:在批容量无限时,不妨假定最优排序π满足不违背最优性原则下每个被接受的工件不能再提前加工,则被π接受的工件在Cm时刻误工。

证明:反证法。首先在π中由观察1知I\B的工件在Cm时刻误工。若B中的工件集B*被π接受在Cm时刻后加工,注意B*中的到达时刻不超过Sm。若π在t∈[Sm,Cm)时刻有新加工批B′,则可把B*与B′合并在t时刻加工,这与最优π的选择矛盾。若π在[Sm,Cm)时段没新加工批,则存在t*∈[Sm,Cm)机器有空闲时段[t*,Cm),故B*可在t*时刻加工,这与最优π的选择矛盾。

定理1:算法A的竞争比为:当批容量无限时,ρ=1/4;当批容量有限时,ρ=1/5。

证明:用反证法。不妨记I是满足A(I)Ck-1。

情形1:Bk是正则批。若k2,令V={Jj:rjSk}。则根据I的选择,A(I\V)ρOPT(I\V),A(V)ρOPT(V)。但A(I)=A(I\V)+A(V),再有引理3,易得A(I)ρOPT(I)与假设矛盾。若k=1,则最早工件在S1到达且I\B中的工件在Ki里最多一批。由观察1得OPT(I\B)

情形2:Bk是推迟批。若k2,令π为I的一个最优排序,t0是Ck-1后最早工件到达时刻,V=U∪{Jj∈I,rj>t0},U*={Jj∈U:rjSk-1或Cj(π)t0},C*是π中工件在t0之前的最后一个完工时刻,I*=I\V∪{Jj∈U*:djC*},V*={Jj∈I:rj>t0}∪{Jj∈U:rj=t0}。算法在[C0,t0]时段内对I和I*中的工件有相同的排序,在t0后对I和V*中的工件有相同的排序,知A(I)=A(I*∪V*)。由I*和V*的构造得OPT(I)OPT(I*)+OPT(V*),A(I*)ρOPT(I*),A(V*)ρOPT(V*)。故A(I)ρOPT(I),与假设矛盾。若k=1,令(t0,S1]内的中断时刻依次为t1,t2,…,tn=S1,令Tj=(tj-1,tj],1jm。

情形2.1:批容量无限时,假定最优排序π满足不违背最优性原则下每个被接受的工件不能再提前加工。由引理1知,π在Tj内最多有一批被接受且个数最多(1/2n-j)│B1│,求和后知在(t0,S1]内加工的工件最多2│B1│2A(I);π在Ki(1im)内最多有一批且个数不超过2│Bi│,求和后知在(S1,Cm]内最多2│B│=2A(I)。故OPT(I)4A(I),与假设矛盾。

情形2.2:批容量有限时。在π下,由引理1知:I\B中的工件在Tj里最多一批被接受个数最多(1/2n-j)│B1│,在Ki(1im)内加工的且个数不超过2│Bi│。由情形2.1知OPT(I\B)4A(I),再由引理2得A(I)(1/5)OPT(I),与假设矛盾。

参考文献:

[1]沈灏,杨启帆.两台机器及时完工工件数最大化问题的近似算法[J].高校应用数学学报A辑,2003,207-212.

[2]H Hoogeveen, CN Potts, GJ Woeginger, On-line scheduling on a single machine: maximizing the number of early jobs, Operations Research Letters 27(2000) 193-197.

[3]X.T. Deng, C.K. Poon and Y.Z. Zhang, Approximation algorithms in batch processing, Journal of Combinatorial Optimization, 7(2003), 247-257.