论文摘要
本文研究一类具有特殊工件的平行机在线排序问题，目标是最小化最大完工时间。用Graham等人[12]提出的三参数法，我们的问题可以表示为：Pm|on-line-list；special jobs（M1）|Cmax，其中M1表示特殊工件要在第一台机器上加工。当工件集中没有特殊工件时，问题就退化成了经典的平行机在线排序Pm|on-line-list|Cmax．所谓在线，本文指的是列表在线：工件被排成一个队列，然后逐个释放。一旦某个工件被释放，必须马上决定在哪台机器上加工它。工件被释放之前，我们不知道它的任何信息。只有当前面一个工件被安排之后，后一个工件的信息才知道。一旦工件被安排到机器上，我们不允许再移动它到另一台机器上。在本文考虑的排序问题中，有两种类型的工件：正常工件和特殊工件。正常工件能够在平行机的任何一台机器上加工，而特殊工件仅仅能够在它被指定的机器上加工，并且每个特殊工件的指定机器是唯一的。在本文讨论的模型中，所有的特殊工件都被指定到机器M1上去加工。在生产实践中，特殊工件是普遍存在的。它们有一些特殊的性能使得它们必须到指定的机器上去处理。这样，就伊得我们的生产安排变得复杂化。本文的主要结果如下：（1）两台机器的情形：P2|on-line-list；special jobs（M1）|Cmax．证明了任意在线算法的竞争比不小于5／3，并提供了一个最好可能的在线算法。（2）三台机器的情形：P3|on-line-list；special jobs（M1）|Cmax．证明了任意在线算法的竞争比不小于1.686，并提供了一个竞争比不超过1.857的在线算法。（3）m（m≥4）台机器的情形：Pm|on-line-list；special jobs（M1）|Cmax．此时的下界至少是Pm|on-line-list|Cmax的下界，并提供了一个竞争比不超过（2m2-2m+1）／（m2-m+1）的在线算法。