单机在线分批排序和平行机半在线排序问题

论文摘要

排序论又称时间表理论,其作为运筹学的一个分支,作为一门应用科学,有着深刻的实际背景和广阔的应用前景。而其中的在线分批排序以及带机器准备时间的半在线问题,因其明显的实际意义,吸引了国内外许多学者。本文主要研究了这两类问题。 论文分三章来叙述。 第一章是引言,主要介绍了排序的生产背景发展、及其一些相关的基本知识。 第二章主要研究了工件有尺寸的单机在线分批排序(三元素表示法表示为1|rj,B,sj|Cmax)及同类机在线分批排序(Qm|rj,B|Cmax)。对于这两类问题,目前很少有人涉及。工件有尺寸的单机在线分批排序是指工件不但有不同的加工时间而且有不同的尺寸。假定机器的尺寸为B,若工件Jj的尺寸（sj）大于B/2则称此工件为大工件否则称为小工件。若每一大工件的加工时间不小于任何一小工件的加工时间则称此问题为工件加工时间和工件尺寸一致的排序问题,简称一致性排序。 本章第一部分我们将分批时只考虑工件个数的单机在线分批排序问题（[25]）推广到工件有尺寸且所有工件有两个到达时间的一致性单机在线分批排序问题,并且给出了一个竞争比不超过33/14的算法。 第二部分讨论了工件有尺寸的一般情形的单机在线分批排序问题并给出了一个竞争比不超过161/60的算法。 本章最后对于分批时只考虑工件个数的单机在线分批排序问题（[25]）推广到m台同类机的情形,设计了一个在线算法并证明了此算法的竞争比为1+sum from i=1 to m-1 bi/bm。 第三章讨论了两台机器上知道工件的最大加工时间和工件加工时间总和两种半在线模型,此时目标函数是极小工件完工时间。用三元素法可表示为P2,aj|Pmax|

论文目录

• 第一章 引言
• §1.1 排序的概念与符号
• §1.2 计算复杂性
• §1.3 分批排序
• §1.4 在线与半在线排序
• 第二章 一类在线分批排序
• §2.1 引言
• §2.2 在线的一致性分批排序问题
• §2.3 一般情形的在线排序问题
• §2.4 同类机的在线分批排序问题
• §2.5 结论
• 第三章 带机器准备时间的半在线排序
• §3.1 引言
• 2，a_j|sum|C_min的半在线算法分析'>§3.2 Q₂，a_j|sum|C_min的半在线算法分析
• 2，a_j|P_max|C_min的半在线算法分析'>§3.3 P₂，a_j|P_max|C_min的半在线算法分析
• §3.4 结论
• 参考文献
• 硕士生期间撰写的论文
• 致谢