几类特殊的分批排序问题

论文摘要

平行分批排序和在线排序是两个发展比较迅速的排序模型。平行分批排序是指机器可以同时加工多个工件，每批包含的工件同时开工同时完工，批的加工时间是这批工件中加工时间的最大者。在线排序是指工件信息在其到达之前是一无所知的，并且一旦工件被安排后就不允许再改变。本文主要考虑了几类特殊的分批排序问题。首先研究了工件具有相容约束的带有运输的单机平行分批排序问题。在这里，我们有一台批处理机和充分多的车辆。有n个同工时的工件J1，J2…，Jn，每个工件的加工时间为p，运输时间为qj．这些工件间有的工件可以在同一批中加工，而有的则不能在同一个批中加工。一批完工后并行地运输。这里的目标函数是工件最后运达顾客的时间。我们把这些工件分别对应于一个图G中不同的顶点，如果工件是相容的，则图G中对应的顶点间就可以连边，否则就不连边。通过这一转换，我们就把工件的相容性约束通过图论中具体的团来刻画，从而使解决相容性约束条件下的排序问题显得更加直观。于是我们所考虑的模型可记为1|p-batch；pj=p，qj；G|Dmax，其中，图G就是代表我们所讨论的工件相容约束性，Dmax=max{Dj|Dj=Cj+qj，1≤j≤n}。由张群发的硕士学位论文[8]可知1|p-batch；pj=p；G|Cmax是NP-困难的，从而我们的问题亦是NP-困难的。相容约束图限定为某些特殊图类时，本文给出了多项式时间算法。主要结论如下：（1）相容约束图G限定为分裂图时，文中给出了问题1|p-batch；pj=p，qj；G|Dmax的时间界为O（n2）的最优算法。（2）相容约束图G限定为完全二部图时，文中给出了问题1|p-batch；pj=p，qj；G|Dmax的时间界为O（n log n）的最优算法。（3）相容约束图G限定为完全m部图时，文中给出了问题1|p-batch；pj=p，qj；G|Dmax的时间界为O（n log n）的最优算法。（4）相容约束图G限定为直径不超过4的树时，文中给出了问题1|p-batch；pj=p，qj；G|Dmax的时间界为O（n log n）的最优算法。其次，本文对带有禁用区间的目标为最小化最大完工时间的单机平行分批排序问题进行了研究。在经典排序中，所有机器都是假设在整个加工过程中一直可用。然而，这个假设往往太过理想，在实际生产过程中，情形可能并非如此。由于对机器的预防性维修或机器突然出现故障都会导致机器在某一段时间内不能使用，有时候我们也把机器不能使用的这一段时间叫做机器的禁用区间。我们假设机器的禁用区间是在工件就绪前已经确定的。工件就只能在剩下的时间内加工。文中考虑两种禁用情形：若一个批在禁用区间之前未能完工而它在机器重新可用后可以接续加工，这种情形称为可继续的，用记号r-a来表示；若该批不可接续而只能重启，即从头开始加工，我们称为不可继续的，用记号nr-a表示，这是借文献[10]的用法。本文对离线情形，要么给出了多项式时间算法，要么给出了近似算法；对一般在线情形，给出了其竞争比的下界可任意大的证明，并对特殊情形给出了最好可能的算法。本文最后对带有强制工件的单机在线分批排序问题进行了讨论。这里所有工件都是在线的，但是，其中有一些特殊工件，它们要求单独成批，其它工件不能与其共批，并且一旦到达就要对其立即加工，我们称其为强制工件（master job），其它工件称为自由工件。假设强制工件间不冲突。该模型可记为1|master job；p-batch，b；on-line,rj|Cmax，文中考虑了和强制工件相冲突的批可中断（pmtn）与需要重启（restart）两种情形，主要结果如下：（5）给出了问题1|master job（restart）；p-batch，b=∞；on-line．rj|Cmax的竞争比下界及最好可能算法。（6）给出了问题1|master job（restart）；p-batch，b＜n；on-line，rj|Cmax的竞争比下界及最好可能算法。

论文目录

• 摘要
• Abstract
• 第一章 引言
• §1.1 排序的介绍
• §1.2 在线排序和分批排序
• §1.3 排序的记号
• §1.4 相关结果及本文主要结果
• 第二章 工件具有相容约束的带有运输的单机平行分批排序问题
• §2.1 引言
• §2.2 分裂图情形
• §2.3 完全二部图情形
• §2.4 完全m部图情形
• §2.5 直径不超过4的树的情形
• 第三章 带有禁用区间的单机平行分批在线排序问题
• §3.1 预备知识
• §3.2 离线情形
• §3.3 在线情形
• §3.4 带有强制工件的单机在线分批排序问题
• 后记
• 参考文献
• 致谢