两类特殊的在线分批排序问题

论文摘要

本文主要考虑了两类特殊的在线分批排序问题.所谓在线,本文指的是按时在线.工件信息在其到达之前是一无所知的,并且一旦工件被安排后就不允许再改变.所谓平行分批排序是指机器可以同时成批加工多个工件.每批包含的工件同时开工同时完工,批的加工时间是这批中加工时间的最大者.首先研究了批容量为3的单机平行分批排序.主要结果如下:（1）对排序问题1|p - batch,b = 3;pj = 1; on - line;ri;limited restarts|Cmax,我们给出了竞争比为（?）的最好可能的在线算法.（2）对排序问题1|p - batch, b = 3; on - line, ri; limited restarts|Cmax,我们证明了竞争比下界为（?）,并给出了竞争比为（?）的在线算法.其次,对带有特殊工件的平行分批排序问题进行了研究.这里所有工件都是在线的,但是,其中有一些工件,它们要求单独成批,其它工件不能与其共批,并且一旦到达就要对其立即加工。我们称其为特殊工件,其它工件称为普通工件.假设特殊工件间不冲突.主要结果如下:（1）对排序问题1|special job（restart）;pj = 1; on - line, ri, D|Σfj,我们给出了竞争比为（?）的最好可能的在线算法.（2）对排序问题P2|special job（pmtn）;p - batch, b =∞; on - line, ri|Cmax,我们证明了竞争比下界为（?）,并给出了竞争比为（?）的在线算法.（3）对排序问题P2|special job（restart）;p - batch, b =∞; on -line, ri|Cmax,我们给出了竞争比为2的最好可能的在线算法.

论文目录

• 摘要
• Abstract
• 第一章 绪言
• 1.1 排序的介绍
• 1.2 在线排序、平行机排序和特殊工件
• 1.3 排序的记号
• 1.4 已知结果及本文主要结果
• 第二章 批容量为3的单机有限重启问题
• 2.1 引言
• 2.2 标准工件的情形
• 2.3 任意工件的情形
• 第三章 带有特殊工件的在线排序问题
• 3.1 引言
• 3.2 目标函数为利润最大的情形
• 3.3 目标函数为最小化最大完工时间的情形
• 后记
• 参考文献
• 致谢