荣建华 张玲玲 王瑞霞

摘 要：该文对两种机器有使用限制的三台同类机排序问题进行了研究，已知有三台机器和，其中的加工速度为1，的加工速度为s（0

关键词：排序 同类机 使用限制 在线算法 竞争比

中图分类号：G64 文献标识码：A 文章编号：1674-098X（2015）07（a）-0052-02

在经典排序问题的研究文献中大都给出了如下假设条件：机器在任何时间都可以加工工件。但是这种假设条件在实际情况中并不总是存在。例如，在机器损坏或维修的一段时间内，机器不能加工工件。因此，关于机器有使用限制的排序问题的研究得到了越来越多的关注。在此条件下，研究人员进一步考虑了以下两类问题。一类是工件可以中断的情况，另一类是工件不可以中断的情况。在考虑上述假设条件的前提下，研究人员对平行机和流水作业等相关问题作了研究。

在考虑机器有使用限制的条件下，研究人员主要对同型机的平行机排序问题进行了研究。假定有一台机器始终可用，而其它机器上都只有一个时间段不可用的条件下，证明了对于可中断的平行机排序问题，LPT算法的性能比为，其中为机器数，且界是紧的；而对于不可中断的平行机排序问题，LS算法和LPT算法的性能比分别为和。而和证明了在最大的同时不可用机器数不超过的条件下，LPT算法的性能比为2。

1 相关定义及符号

三台同类机排序问题可以描述如下：

给定三台机器和，其中的加工速度为1，的加工速度为）。给定待加工的工件集，的加工时间为，每个工件只需在一台机器上加工，工件在机器上加工需要的实际时间为）。该文主要研究了两种机器有使用限制的三台同类机排序问题。第一种是机器在时段不可用，而机器始终可用，目标函数为工件的最大完工时间，将此问题用三参数法表示为，其中表示机器上有使用限制；第二种情况是机器在时段不可用而机器始终可用。此类问题可以表示为。对于上有使用限制的情形和第一种情况完全一样。

该文分析了和问题的LS算法。LS算法描述如下：

将当前待加工的工件安排在可以最早完成加工的机器上。如果出现两台或三台机器同时加工的情况，则优先安排在速度快的机器上加工。

2 主要结论及证明

在对LS算法的性能比进行分析以前，我们先给出由LS算法的排序所得到的对问题。最优排序的最大完工时间的一个估计。

引理2.1：设对问题，由LS算法所得到的排序为设中最后完工的工件为，其开始加工时刻为。令的最优排序的最大完工时间为，则必有。

证明：设实例共有个工件。记排序中机器上工件的最后完工时间分别为。以下分情况讨论：

情形1：此时，时刻前三台机器上的可用加工时间之和为。

情形1.1：在机器上完工。此时。

情形1.1.1：即机器在时刻前已完工。由算法可知：机器在时刻B前剩余的时间不能完成工件的加工，即。所以故。

因为

所以

=

。

情形1.1.2：由算法可知：不会大于时刻，即。

因为

所以

=。

因而有。

情形1.2：在机器上完工。仿情形1.1，同理可证。

情形1.3：在机器上完工。此时。

因为

所以

=。

因而有。

情形2：令表示时刻以前机器上空闲时间段。

情形2.1：在机器上完工。此时。

情形2.1.1：。由算法可知故。

因为

又因为时刻之前三台机器上的可用加工时间之和为

所以

从而得到。

情形2.1.2：。此时且。

因为，

又因为时刻之前三台机器上的可用加工时间之和为，所以

从而得到。

情形2.2：在机器上完工。仿情形2.1，同理可证。

情形2.3：在机器上完工。此时。且。

因为

又因为时刻之前三台机器上的可用加工时间之和为，

所以。

从而得到。

定理2.1：问题的算法的竞争比为。

证明：设在中最后一个完工工件为，开工时间为，进一步设中的完工时间为。

情形1：在上完工。此时，且。

又因为

所以

情形2：在上完工。则且。

又因为

所以

情形3：在上完工。此时且。

又因为

所以。

定理2.1：问题的算法的竞争比为。

证明：设在中最后一个完工工件为，其开工时间为，又设在中的完工时间为。

情形1：工件在或上加工。由和的对称性，不妨设在上加工。此时，且。

因为

所以

情形2：如果工件在上加工。则。

情形2.1：此时有

。

注意以下两个不等式成立

（1）。

（2）。

故

情形2.1.1：。此时有。

情形2.1.2：此时有

情形2.2：令表示时刻以前机器上的空闲时间段，则。且。由引理2.1可知：

下面分三种情况讨论：

情形2.2.1：由于我们有

情形2.2.2：。由于我们有

情形2.2.3：因为

所以

综上可知：对任意实例总有。

3 结语

该文讨论了机器有使用限制的三台同类机排序问题，证明了LS算法的竞争比分别为和。下一步将致力于研究以下两个问题：（1）讨论该问题的下界；（2）将机器台数推广到m，设计在线算法并分析算法的竞争比。

参考文献

[1] C.Y.Lee，Machine scheduling with an availability constraint[J].Journal of Global Optimization，1996，9（3）：395-416.

[2] H.C.Hwang and S.C.Chang，Parallel machines machines scheduling with machine shutdowns[J].Computers and Mathematics With Applications，1998，36（3）：21-31.