带有强制工件的单机在线分批排序问题

金世国，张巧利

（1.郑州信息科技职业学院，河南 郑州 450046；2.河南广播电视大学，河南 郑州 450008）

带有强制工件的单机在线分批排序问题

金世国1，张巧利2

（1.郑州信息科技职业学院，河南 郑州 450046；2.河南广播电视大学，河南 郑州 450008）

本文研究了带有强制工件的单机在线分批排序问题, 目标函数为最小化最大完工时间。考虑了和强制工件冲突的批可以中断(pmtn )和需要重启(restart)两种情形。对于每一种情形，给出了问题的下界及相应的近似算法或最好可能的近似算法。

强制工件；单机；在线；平行分批

在经典排序论中，一般假定实例的所有相关信息在开始排序前是事先知道的，如工件的个数、到达时间及加工时间等，这样的情况称为是离线的。但是现实生活中很多情况不是这样，有时工件的信息是逐个释放的，在任一时刻只知道已经到达的工件信息，这种情况称为在线(on-line)。在分批排序中，机器可以同时加工多个工件，构成一批，并且批的加工时间是该批所有工件加工时间中的最大者。如何来分批是问题的关键，批确定后，可将其看做一工件来寻求最优算法或近似算法。这里考虑带有强制工件，目标函数为最小化最大完工时间的在线分批排序，所有工件都是在线的，但有1一| p些 −特ba殊工件要求单独成批，且一旦到达了就要立刻加工，这类工件称为强制工件(master job)，其余称为自由工件。在这里强制工件间不相互冲突。1此|m 模ast型er记jo为b(： pmtn) ; p −ba

1|m asterjob; p −batch,b; on −line,rj|Cmax，

考虑仅和强制工件冲突的批可中断(pmtn)与需要重启(restart)等情形。批允许重启指可打断正在加工的批，其已加工部分作废，该批中的工件重新被释放，变为未加工工件，可与其它已达未加工工件重新组合成新批，再被加工。

用竞争比来衡量一个在线算法的优良程度。记CH(L)，C*(L)表示对任意的工件序列L，在线算法H对应的最大完工时间值及离线状况下最优值。算法H的竞争比定义为R =sup{CH(L)/C*(L )}，竞争比越小，对H∀L应算法越好。这里，我们把CH(L)和C*(L)简记为CH和C*。1|m asterjob(p mtn) ; p − b Zhang G．C．等人对问题1|o n −line,rj;p −batch,b| |Cmax进行了系列研究，也证明了该模型在线算法的下界为1+α，这里α= (5 −1)/2，且批容量无界时，给出了与这一下界相吻合的最好可能算法H∞；当批容量有界（b ＜n）时，又给出了一竞争比不超过2的算法HB，猜想HB为最好可能。

算法FBLPT：

Step1：按加工时间不增的顺序对工件重新标号使p1≥ p2≥…pn。

Step2：第ib+1个工件至第(i + 1)b个工件构成一批，这里i = 0,… ,[n/b]，[x] 表示小于x的最大整数。

Step 3：这些批按任意的序来排列。

1 可中断（pmtn）情形

1.1 批容量无界情形

算法MH∞：

Step 0：当强制工件到来时，立即对其加工，同时把加工区间收缩为一点，修改一下时间轴。当强制工件完工时，继续原来中断的批。

Step 1：执行算法H∞。强制工件到来时就返回Step 0。

定理3：对于问题1|m asterjob( pmtn) ; p − batch,b =∞; o n −line,rj|Cmax，算法MH∞竞争比不超过1+α。证明：对任意的实例L，H∞在修改时间轴下目标值和最优值用C1和C1*表示，MH∞对应目标值和最优值用C和C*表示，记强制工件总长度为 ∆L。 有C*= C1*+∆L ；C= C1+∆L 。 对 于C1和C1*， 由 Zhang G．C． [1]知，C1/C1*≤1+α， 故C/C*= (C1+∆L )/(C1*+∆L ) ≤ C1/C1*≤1+α。由定理2和定理3可知，算法MH∞是最好可能。

1.2 批容量有界情形

1|m asterjob(p mtn) ; p − batch,b ＜n;o n −line,rj|Cmax

算法MHB：

Step 0：当强制工件来到时，立即对其加工，同时把加工区间收缩为一点，修改一下时间轴。当强制工件完工时，继续原来中断的批。

Step 1：执行算法HB。强制工件来到时就 返回Step 0。

定理4：对于问题1|m as1te|mr ajosbte(r pmjotbn() r;e ps t−a rbta)t;cph −,b b ＜atnc;h n;o n −line,rj|Cmax，算法MHB竞争比不超过2。

证明：对于任意的实例L，算法HB在修改时间轴下目标值和最优值用C1和C1*表示，MHB对应目标值和最优值用C和C*表示，记强制工件总长度为∆L。有

2 重启(restart )情形1

证明：构造实例，J1是第一个工件同时也是自由工件于零时刻到达，长度是1。对任一算法H，

Case 1：若算法在时刻1前还未加工J1，则就不来工件。此时有CH≥2；C*=1．故CH/C*≥2．

Case 2：若算法在时刻0已经开始加工J1，则于ε时刻来到另一自由工件J2，长度也为1。此时CH≥2；C*=1+ε，于是CH/C*≥ 2/(1 +ε) → 2(ε →0)。

Case 3：若算法在l 时刻开始加工J1，这里0 ＜ l＜1，则一强制工件J2于1时刻到来，长度为 ε。 此 时CH≥1 + ε+ 1= 2+ε；C*=1+ε， 故CH/C*≥(2 + ε) /(1 +ε) → 2(ε →0)．

综上可知，RH≥2。

2.1 批容量无界情形

算法H：

Step 0：当机器可用时，一旦有可用的自由工件，就把其放在同一批立即加工。

Step 1：当有强制工件到来时，对其立即加工。返回Step 0。

定理6：问题1|m asterjob(r estart); p − batch,b =∞;o o n −line,rj|Cmax的算法H竞争比不会超过2。

证明：对任一实例L，L中最大工件的长度我们记为pmax。根据算法知，CH和C*至多相差了某批的长度，从而即。

由定理5和6知，算法H 是最好可能的。

2.2 批容量有界情形

算法HH：

Step 0：每当机器可用时，若有可用的自由工件，则对当前所有自有工件按FBLPT 进行分批，按批的LPT 进行加工。

Step 1：强制工件到来时，对其立即进行加工。同时返回Step 0。

以下仅考虑最后到达工件集中不含强制工件的情形，记它是在批B0加工过程中到达的。在B0加工的过程到达的新工件中最早到达时间记为r′．按照下面方法来处理：B0加工过程中所有到达的新工件都看成是时刻到达的，如果批B0是强制工件，仿上可以证明。不是强制工件，把其加工区间记为[s,t]，N表示s 时刻可用工件集，N′表示r′时刻到达的新工件集，算法中t 后加工的批我们记为

用F(D)来表示对工件集D运用FBLPT得到批的加工时间之和。处理后的实例的目标值和最优值分别用Cmax与C*′表示。我们有

而C*′ ≥max{F(N),r ′+F(N ′)}，因此C /C*′≤2．

max容易得知，处理过的实例与原来的相比较，目标值不变，最优值也不会增加，所以对原实例也有CHH/C*≤2．综上，定理成立。 由定理5和定理7可知，在线算法HH 是最好可能的。

3 结语

本文研究的带强制工件的单机在线分批排序问题,对可中断(pmtn )与需重启(restart)两种情形，均给出了问题的下界及近似算法或最好可能的近似算法。

[1]Zhang G．C．,Cai X．Q． and Wong C．K． On-Line Algorithms for Minimizing Makespan on Batch Processing Machines[J] ．Naval Research Logistics, 2001, 48: 241-258．

[2]Poon C．K． and Zhang P．Minimizing makespan in batch machine scheduling[J]． Algorithms, 2004, 39:155-174．

[3]Poon C．K． and Yu W．C．On-Line Scheduling Algorithms for a Batch Machine with Finite

O223

A

1671-0711（2017）08（下）-0216-02

河南省教育厅科学技术研究重点项目(15A110003)。