平行机链约束下单位长度工件的在线排序问题

平行机链约束下单位长度工件的在线排序问题

有序约束的顺序问题是经典的顺序模型，只有在所有现有零件加工好后才能开始加工，链束结构是一种特殊的序列限制。除了头和尾零件，还有后入件和后入件。在线顺序的特点是对零件信息的逐步释放。由于手中的信息不足，决策者只能根据当前的信息进行分类和决策。由于能够掌握的信息不足，许多在线问题无法设计最佳的多项式时间算法。在线附近算法的优势和劣势可以用竞争比来评估。假设i是其前任，表达式参数（）是在线算法的目标值，并且elax（）是最佳目标值，则在线算法的竞争比设置为最佳目标值。两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题可以描述为:给定两台速度完全一样的平行机,每个到达时刻到达的是具有链组约束的工件,工件的加工时间都是1,工件的其它信息是在线的,只有到到达之后,其约束关系等信息才全部释放,只有工件的全部前任工件加工完才称为可用工件,目标函数是最小化最大完工时间的平方和.文中常用的记号有:Jj:第j个工件;chainsi:第i个条链;│chainsi│:第i个条链的工件数;rj,sj,pj,C(Jj):分别表示工件的到达时间、开工时间、加工时间和工件Jj的完工时间;Mi(i=1,2):第1,2台机器;CMi(i=1,2):第1,2台机器的完工时间;emax:两台机器的最大完工时间平方和,即emax=C2M1+C2M2;emax(σ):在线算法排序σ下的完工时间平方和;emax(π):离线最优排序π下的完工时间平方和.文献只研究了一些工件带有序约束关系的最大完工时间、最大工件延误时间等问题,对于目标函数是机器完工时间平方和的排序问题的研究目前还比较少.本文考虑了两台平行机上链约束下单位长度工件完工时间平方和最小的在线排序问题.用三参数法表示为.利用对手法证明任一实例在任意算法下竞争比不小于5/4,而任意稠密算法的竞争比都渐近地趋于2;其次找到一种稠密算法—层次算法,其竞争比为2,从而说明此层次算法为本问题的一个最好可能在线稠密算法.1工件安排开工定理1对于问题,不存在在线算法,使得它对于该问题的所有实例的竞争比都小于5/44证明我们下面利用对手法(AdversaryArgument)给出一组实例,并证明任何一个在线算法都无法使它的竞争比小于5/44考虑下面的链:chains1在r1=0时刻到达,它包含一条只含一个工件的链;r2=1时刻到达两条含一个工件的链chains2,chains3.情形1若在线算法在0时刻没有将0时刻到来的工件安排开工,则chains2,chains3不来.此时工件J1的开工时刻s1≥1,emax(σ)≥(s1+1)2≥4,emax(π)=1.从而有情形2若在线算法在0时刻将0时刻到来的工件安排开工,不妨假设工件J1在机器M1加工,s1=0,则chains2,chains3到达.根据工件J2和J3是否在同一台机器上加工又分为下面几种情况.子情形2-1工件J2和J3在同一台机器上加工.此时又分为以下两种子情形.子情形2-1-1工件J2,J3与J1不在同一台机器上加工.则后面不来工件.此时(如图1),我们有emax(σ)≥1+32=10,emax(π)=22+22=8.从而子情形2-1-2工件J2,J3与J1在同一台机器上加工.则chains4到达(如图2).此时,不管工件J4,J5与J1是否在同一台机器M1,都有emax(σ)≥25,emax(π)=20.从而有(如图3)emax(π)emax(σ)≥2025=45.子情形2-2工件J2和J3不在同一台机器上加工.则第四组链chains4到达(如图4).此时,不管工件J4在机器M1还是在机器M2上加工,都有emax(σ)≥20,emax(π)=16.从而有(如图5)由上述情况可知,任何在线算法都无法使这组实例的竞争比全部小于5/442yarguc算法仿真两台平行机的稠密算法指:两台机器一旦同时空闲,且当前可加工工件集非空,就指派当前可加工工件到其中任一台空闲机器上加工.下面我们构造一组实例来说明任意的稠密算法下此问题的竞争比都渐近地趋于2.定理2对于问题,任何在线的稠密算法的竞争比在渐近的意义下都不会比2小.证明我们下面利用对手法(AdversaryArgument)给出一组实例,并证明任何在线的稠密算法的竞争比在渐近的意义下都不会比2小.考虑下面的实例:J1,J2在r0=M时刻到达;J3,J4在r1=M+1时刻到达;…;J2i+1,J2i+2在ri=M+i时刻到达;…;J2n+1,J2n+2在rn=M+n时刻到达.所有工件的加工时间pj=1,j=1,2,…,2n+2.根据稠密算法,不妨设工件J1放在机器M1上加工.若工件J2在机器M2上加工,后面不来工件.此时若工件J2也在机器M1上加工,则工件J3,J4在r1=M+1到达.若工件J3,J4有一个或两个都放在机器M2上加工,则或者依次下去,若有某一个工件J2i+1或J2i+2放在机器M2上加工,则后面不来工件.此时可取M充分大,则若一直没有工件放在机器M2上加工,后面按照上述方式一直来工件.当工件的个数2n充分大的时候,我们有.由上述情况可知,任何在线的两台平行机的稠密算法的竞争比在渐近意义下不小于2.定理得证.推论1对于问题,任何在线的稠密算法的竞争比在渐近意义下不会比2小.3在线层次算法要证明一个最小化问题的在线算法是最好可能的在线算法,只需证明其竞争比不大于问题的下界.对于问题,我们只需证明在线算法的竞争比不大于2即可.若问题的某个实例I的第一个到达时间r1严格大于0,则对这个实例有.如果我们把I的所有到达时间都减小r1(第一个到达时间变为0)得到一个新实例I′.若一个在线算法对I′的竞争比不大于2,则对I的竞争比也不大于2.故我们在接下来总是作以下约定.约定问题的每一个实例的第一个到达时间都满足r1=0.接下来我们来研究该问题的最优在线算法.在给出我们的在线算法之前,首先给出工件level的定义.定义对于一组链组约束下的工件,若一个工件没有直接后继,则它的层次为1;若一个工件有直接后继,则它的层次为其直接后继的层次加1.记工件Jj的层次为level(Jj).由层次的定义我们知道,一个链的第一个工件的层次等于它所在的链所含的工件个数.在接下来的讨论中,称一个工件在某一时刻t可排,是指它满足以下三个条件:(1)此工件所在的链在t时刻已经到达;(2)此工件的所有前任在t时刻已经完工;(3)此工件在t时刻之前未被安排开工.而机器在t时刻可用是指在这个时刻机器没有加工工件.下面我们给出我们的在线层次算法(On-LineLevelAlgorithm)H.在线层次算法H:t为当前时刻;U(t)为当前时刻t的可排工件集合.1)0时刻,若可排工件集U(0)中可排工件至少有两个,将层次最高的两个工件(若层次最高的工件不止两个,则任选两个)分别安排在M1,M2上开工;若可排工件集U(0)中只有一个工件,安排其在M1上加工;2)当t≥1时,每当有机器可用时,将层次最高的可排工件中的一个安排在空闲机器上加工.若两台机器同时可用,优先安排在M1上开工;3)当所有工件都已完工时,结束算法.在此问题中,我们要求工件在整数时刻到达,在整数时刻开工,当然工件会在整数时刻完工.通过分析算法我们知道,在算法产生的排序Son中满足:无工件可排而产生的机器空闲:在某个时刻t一台机器可用,但此时U(t)中的工件全是另一台机器上正加工工件的后继,这样只有当有新工件到来后才可能有工件可在这台机器上安排.这样的空闲只会出现在某个到达时间ri之前,具有[ri-li,ri)的形式,其中li为空闲的长度一旦有工件可排且机器可用,则向空闲机器安排加工当前最高层次工件,若两台机器同时空闲,优先在机器M1上加工.定理3对于问题,层次算法H的竞争比不超过2.证明假设在层次算法H下机器的最大完工时间CHmax的决定工件为Jn,其所在的链为chainJn∈,这条链的到达时间为rn,用│chainJn∈│表示这条链的工件个数,当然等于链上工件的总的加工时间和,把机器的最小完工时间表示为CHmin,在离线最优排序下机器的最大完工时间和最小完工时间分别为Cmaxopt,Cminopt,那么由算法知,当机器M1空闲时,机器M2在此段上也必然空闲.假设工件Jn前最后一个空闲时间段之后的连续的块(Block)的第一个工件为Jl.将该连续块(Block)记作B(l).若没有这样的空闲时间段,则工件Jl为所在的链chainJl∈的层次最高的工件,即起点工件,其到达时间为rl.那么,由算法可知,工件Jl的开工时间sl=rl,所以CHmax=rl+│B(l)│,其中│B(l)│表示块B(l)中工件个数,当然也为其中工件的总加工时间和.块B(l)中的相邻的工件