具有特殊工件的平行机在线排序问题

摘要

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

目录

文摘

英文文摘

第一章绪言

§1.1排序的介绍

§1.2在线排序、平行机排序和特殊工件

§1.3排序的记号

§1.4已知结果及本文主要结果

第二章具有特殊工件的平行机在线排序问题

§2.1引言

§2.2两台机器的情形

§2.3三台机器的情形

§2.4 m(m≥4)台机器的情形

后记

参考文献

致谢