姚青华，邱本花

(郑州科技学院基础部，河南郑州 450064)

链组约束下部分批处理平行机在线排序

姚青华，邱本花

(郑州科技学院基础部，河南郑州 450064)

研究了一台是批处理机而另一台是正常机器、工件具有链组约束、最小化时间表长的两台恒同机在线排序问题.给出该问题竞争比为+1)/2的最好可能的在线算法.

在线排序;平行分批;链约束;竞争比;下界

0 引言

设有两台恒同机器，机器分别记为M1，M2，其中M1是批处理机且容量无界，M2是正常机器且任意时刻只能加工一个工件.工件信息在排序之初未知，只有在其到达之后工件信息才释放，每个到达时间到来的一组工件之间存在链组约束关系，所有工件的长度都相同(即为p)，目标是最小化时间表长.用Cj表示工件Jj的完工时间.根据文献［1］，该模型用三参数法表示为

链约束可以借助于有向图来描述:设每个工件对应有向图的一个顶点，若每个顶点都至多有一个直接前任和一个直接后继，则此工件之间的序约束称为链组约束.对于一组链组约束下的工件，若该工件有直接后继，则它的层次为直接后继工件的层次加1;若该工件没有直接后继，则该工件的层次为1.记工件Jk所在的链为chainJk，此链的到达时间为rk.用|chainJk|来表示链chainJk中所含工件的个数.

对于两台恒同机或者都是批处理机或者都是正常机器排序问题，文献［2］和文献［3］已经给出了相当丰富的研究成果，而同时考虑一台机器是批处理机，另一台是正常机器的研究很少看到.本文讨论该问题的下界为1+α的情形，并给出了一个最好可能的在线算法，其中，α =－1/2.

1 问题的下界

定理1该问题不存在竞争比小于1+α的在线算法.

证明 首先，ε是一个充分小的正数.假设在r=0时刻到达两个只含一个工件的链，分别为chainJ1，chainJ2.J1，J2的开工时刻分别为s1，s2.

情形1 如果s1，s2至少有一个si≥αp(i=1，2)，那么不再来工件.于是，Cmax(σ)≥si+p，Cmax(π)=p.因此，Cmax(σ)/ Cmax(π)≥(si+p)/p≥1+α.

情形2 如果s1，s2都有si＜αp(i=1，2)，那么考虑下面两种情况:

情形2.1 若J1，J2分别安排在M1，M2上开工，且si≤sj(i，j∈{1，2})，但i≠j，那么在si+ε时刻又来n(n≥2)条只含一个工件的链.于是，Cmax(σ)≥si+2p，Cmax(π)≤si+p+ε.因此，Cmax(σ)/Cmax(π)≥(si+2p)/(si+p+ε)→(si+2p)/(si+p)= 1+p/(si+p)＞1+α.

情形2.2 若J1，J2作为一批安排在M1上开工，则s1=s2=s，那么在s+ε时刻又来n(n≥2)条只含一个工件的链.则Cmax(σ)≥s+2p，Cmax(π)≤s+p+ε.故Cmax(σ)/Cmax(π)≥(s+2p)/(s+p+ε)→(s+2p)/(s+p)＞1+α.

2 问题的一个最好可能的在线算法

2.1 约定及算法描述

约定1对于该问题任意一个实例第一个到达时间都满足r1=0.

约定2在同一时刻不会到达两个或多个完全一样的链.

把已经到达且所有前任都已完工的工件称为可排工件.

算法H

t←当前时刻，k←移动指针，U(t)←当前可排工件的集合.

第1步 令k=0.在t=0时刻，将U(0)中可排工件中层次最高者安排在M2上开工.

第2步 安排工件到机器M1，执行:如果t=(α+k)p，那么将U(t)中可排工件作为一批安排在机器M1上(这里允许某一批为空).否则，M1等待.转第3步.置k=k+1.

第3步 安排工件到机器M2，执行:

第3.1步 当p≤t＜(1+α)p时，若U(t)中存在层次大于等于2的可排工件，则将层次最高者安排在M2上开工.否则，M2等待.返回第2步.

第3.2步 当t≥(1+α)p时，若只有机器M2可用，则将U(t)中层次最高者安排在M2上开工(如果该工件不唯一，选择到达时间最大);若两台机器都可用，优先安排在M1上开工，开工时刻为t=(1+α)p，将U(t)中所有可排工件作为一批在t时刻加工.返回第2步.

第4步 当所有工件已完工时，结束算法.

假设Bl为σ中M1上的最后一批完工工件，这里的Jl是Bl中所在链最长的工件(如果该工件不唯一，那么选择rl最大的一个)其中rl是链chainJl的到达时间.工件Jc是机器M2在σ下最后一个加工工件，其到达时间为rc，开工时刻为sc.现在假设Bl之前的一批为B*(如果有的话)，其开工时刻为S*.

由算法的第3.2步可知，不会出现CM1(σ)=CM2(σ)的情况.现在我们讨论σ中两台机器的完工时间(σ)(σ)之间的关系，就CM1(σ)＞CM2(σ)和CM1(σ)＜CM2(σ)两种情况分别证明，算法H的竞争比为1+α.

2.2CM1(σ)＞CM2(σ)的情形

定理2 若CM1(σ)＞CM2(σ)，则在线算法H的竞争比不超过1+α.

证明 如果批B*不存在，那么M1上只有一批Bl.根据算法H可知，Cmax(σ)/Cmax(π)≤1+α.下面我们假设B*存在.

情形1B*与Bl之间有空闲时间.由算法H及题设可设CB*=(i+α)p(i≥1).

情形1.1rl＜CB*.

断言1 批B*内不含链chainJl中任意一个工件.

断言2 由算法H及题设条件可知，链|chainJl|≥2.

断言3 在CB*时刻，机器M2正在加工链chainJl中的工件Jl|chainJl|－1.

断言4 链chainJl的第一个工件Jl1一定安排在M2上开工，并且工件Jl1，Jl2，…，Jl|chainJl|－1在M2上连续加工.

断言5 链chainJl的第一个工件Jl1的开工时刻满足sl1＜rl+p.

由断言5可知Cmax(σ)≤sl+|chainJl|p+p≤rl+(|chainJl|+2)p，Cmax(π)≥rl+|chainJl|p.

(1)rl=0.由题设可知|chainJl|≥3.由断言4及题设可设B*的完工时间为(i+α)p.于是Cmax(σ)=(i+α)p+2p＜(|chainJl|+1)p，Cmax(π)≥rl+|chainJl|p=|chainJl|p.故

(2)αp＜rl＜(1+α)p.由断言4、断言2及题设可知，在rl时刻必须安排工件Jl1在M2上开工.Cmax(σ)/Cmax(π)≤1+α.

(3)rl＞(1+α)p.注意|chainJl|≥2，则有Cmax(σ)/Cmax(π)≤(rl+|chainJl|p+2p)/(rl+|chainJl|p)≤1+α.

情形1.2rl＞CB*.则链chainJl只含有一个工件.于是Cmax(σ)=(i+1+α+1)p，而Cmax(π)≥rl+p＞(i+α+1)p.故，Cmax(σ)/Cmax(π)≤(i+α+2)/(i+α+1)≤1+α.

情形2B*与Bl之间没有空闲时间.

情形2.1 假设|chainJl|=1，则rl＞sB*≥αp.若B*为M1上第一批，则αp＜rl≤(1+α)p.于是，Cmax(σ)=(2+α)p，而Cmax(π)≥rl+p≥(1+α)p.故Cmax(σ)/Cmax(π)≤1+α;若B*为M1上第i批(1＜i＜m)，则rl＞(1+α)p.在rl时刻，若M1可用(或者M1，M2同时可用)并且工件Jl被安排在M1上，则Cmax(σ)/Cmax(π)≤1+α.在rl时刻，若M1不可用，则M2也不可用.于是，(i+α)p＜rl≤(i+1+α)p(1≤i≤m－1)，则Cmax(σ)=(i+2+α)p，而Cmax(π)≥rl+p≥(i+1+α)p.故，Cmax(σ)/ Cmax(π)≤1+α.

情形2.2 假设|chainJl|=2.如果工件Jl1在M1上加工，显然工件Jl也在M1上加工.由断言5可知Cmax(σ)=sl+2p＜rl+3p，而Cmax(π)≥rl+2p，于是，Cmax(σ)/Cmax(π)≤1+α;如果工件Jl1在M2上加工，由题设条件可知工件Jl在M1上加工.若批B*的开工时刻sB*=αp，则rl=0.于是，Cmax(σ)≤(2+α)p.而Cmax(π)≥rl+2p=2p.故，Cmax(σ)/Cmax(π)≤1+α;若批B*的开工时刻sB*≥(1+α)p，设批B*的完工时间为(i+α)p(i≥2)，由算法H及题设条件可知rl＞(i－2+α)p，且Cmax(σ)≤(i+α)p+p，而Cmax(π)≥rl+2p≥(i+α－2)p+2p=(i+α)p.于是Cmax(σ)/Cmax(π)≤1+α.

情形2.3 假设|chainJl|≥3.如果0＜rl≤αp，根据算法 H可知将工件Jl1在t=αp时刻安排在M1上开工.于是，Cmax(σ)=(|chainJl|+α)p.而Cmax(π)≥rl+|chainJl|p＞|chainJl|p.所以Cmax(σ)/Cmax(π)≤1+α.如果rl＞αp，由断言5可知Cmax(σ)≤sl+(|chainJl|+1)p≤rl+(|chainJl|+2)p.而Cmax(π)≥rl+|chainJlp|.故Cmax(σ)/Cmax(π)≤1+α.

2.3CM1(σ)＜CM2(σ)的情形

考察M2上最后一个关键工件Jc，假设Jc所在的链为chainJc，该链的到达时间和开工时间分别为rc，sc.并且设链chainJc的第i个工件为Jci(1≤i≤c).

观察1 (1)链chainJc的第一个工件Jc1必定在M2上开工;(2)当rc＞αp，且工件Jc1一旦在机器M2上开工时，则工件从sc开始一直连续加工到Cmax(σ).

观察2 根据算法H可知，链chainJc的到达时间rc满足rc=0或者rc＞αp且rc≠(α+k)p(k为非负整数).观察3 当rc=0时，链chainJc所含的工件个数|chainJc|≠2.

定理3 若CM1(σ)＜CM2(σ)，则在线算法H的竞争比不会超过1+α.

证明 情形1rc=0.由观察3可知，仅需考虑|chainJc|≥3或|chainJc|=1.由算法H可得Cmax(σ)=Cmax(π).

情形2 αp＜rc＜(1+α)p.如果|chainJc|=2，根据算法H及观察1可知，在rc时刻机器M1正在加工工件，于是，Cmax(σ)=sc1+2p＜(1+α)p+2p=(3+α)p.而Cmax(π)≥rc+2p＞(2+α)p.所以Cmax(σ)/Cmax(π)≤1+α.如果|chainJc|≥3.根据算法H及观察1可知，在rc时刻机器M1正在加工工件.

于是Cmax(σ)=sc1+|chainJc|p＜(1+α)p+|chainJc|p=(|chainJc|+1+α)p.而Cmax(π)≥rc+|chainJl|p＞(|chainJc|+ α)p.所以Cmax(σ)/Cmax(π)≤1+α.

情形3rc＞(1+α)p.根据算法H及观察1和观察2可知，在rc时刻机器M1必定在加工某一批B.假设(i+α)p＜rc≤(i+ 1+α)p(1≤i≤n).由算法H及题设条件可知必定有CM1(rc)＞(rc)，于是Cmax(σ)=+|p≤(i+1+||+ α)p，而Cmax(π)≥rc+||p.所以Cmax(σ)/Cmax(π)≤1+α.

综上，有以下结论.

定理4 对排序问题P2|on－line，p－batch，chains，pj=p，B1=∞，B2=1|Cmax所有实例，在线算法H的竞争比不会超过1+α.

［1］ GRAHAM R L，LAWLER E L，LENSTRA J K，et al.Optimization and approximation in deterministic sequencing and scheduling:a survey［J］.Annals of Discrete Mathematics，1979(5):287－326.

［2］ DU J，LEUNG J Y T，YOUNG G H.Scheduling chain-structured tasks to minimize makespan and mean flow time［J］.Inform and Comput，1991，92(2):219－236.

［3］ NONG Q Q，CHENG T C E，C T NG.An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines［J］.Operat Res Lett，2008，36(5):584－588.

On-Line Scheduling on Partial Batch Parallel Machine with Chains Precedence Constraints

YAO Qing-hua，QIU Ben-hua

(Department of Basic Courses，Zhengzhou College of Science＆Technology，Zhengzhou450064，China)

Studied on-line scheduling of two identical parallel machines，one of which is processing machine and the other is normal.The jobs are chains-precedence constraints;the goal is to minimize the makespan.Provided a best possible on-line algorithm for the problem with competitive ration(+1)/2.

on-line scheduling;parallel batch;chains-precedence constraint;competitive ration;lower bound

O224

A

1007－0834(2011)02－0037－03

10.3969/j.issn.1007－0834.2011.02.013

2011－02－23

河南省基础与前沿技术研究计划资助项目(082300410070)

姚青华(1982—)，男，河南驻马店人，郑州科技学院基础部教师.