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

允许重启的最大化按时完工数的分批在线排序 　　摘要: 我们考虑允许重启的分批在线排序模型,目标值是最大化按时完工数。就等长工件情形下,当批容量为无限时给出一个竞争比为的在线算法;当批容量有限时给出一个竞争比为的在线算法。 　　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\BdjCm+p;(b):t∈[Si,Ci)│Ut│2│Bi│ 　　观察2:若Bi是一个正则批,且i2,SkCk-1,则在[Ck-1,Sk)内机器空闲。 　　引理1:若记Bi是一个推迟批。若i=1,记t0=C0,否则记t0为Ck-1后最早工件的到达时刻。令(t0,Si]内的中断时刻依次为t1,t2,…,tn=Si。则以下结论成立: 　　(a)tj+1-tjp,0jn-1;(b)│U│(1/2)│U│,0jn-1; 　　(c)│U│(1/2n-j)│B│t∈[tj,tj+1),0jn-1 　　证明:(a),(b)由算法性质可得;由│Q│=│B│及(c)条件下│U│2│U│,故结合(b)递推可得(c)成立。 　　引理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