工件有任意到达时间的在线与半在线排序问题

论文摘要

排序问题是组合优化领域中的一类重要问题，它是利用一些处理机、机器或者资源最优地完成一批给定的任务或作业。本文研究了在线排序的一种新的模型——工件有任意到达时间的（半）在线排序，又称之为订单排序模型。该模型是由李荣珩教授在新加坡国立大学做访问学者期间（2000-2004）提出的，并给出了一个近似比不超过2.9392的启发式算法。美国《Math．Rev．》评论认为该排序模型将会引起所有排序研究工件者的兴趣。本文首先简单地介绍了排序问题的相关定义、记号及相关知识，描述了（半）在线排序和工件有任意到达时间的在线排序模型的一些特性。第二部分研究了工件有任意到达时间的在线排序模型，讨论了单台机上有最小的最坏性能比为2的LS算法。对在线模型的MLS算法的性能比的上界由2.939201推进到了2.924191第三部分研究了工件有任意到达时间的半在线排序模型。对于工件按加工时间非增的顺序到达的单台机半在线排序给出了任意算法下界和LS算法为3／2的紧界，另外对带缓冲区的半在线模型给出了一个BLS算法。文章末，对工件有任意到达时间的排序问题做出总结和研究展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 排序和安排时间表
• 1.2 排序问题的分类和特点
• 1.2.1 排序问题的分类（三参数表示法）
• 1.2.2 排序问题的特点
• 1.3 近似算法和竞争比分析
• 1.4 在线和半在线排序
• 1.5 工件有任意到达时间的（半）在线排序
• 1.6 本文的特点和主要工作
• 第二章 工件有任意到达时间的在线排序分析
• 2.1 定义及算法
• 2.2 单台机模型的LS算法
• 2.3 多台机模型的LS算法
• 2.4 LS的改进算法——MLS算法
• 2.4.1 MLS法的界的分析
• 2.4.2 MLS算法的分析
• 2.4.2.1 第一部分:估算U（L）
• 2.4.2.2 第二部分:定理2的证明
• 2.5 总结
• 第三章 工件有任意到达时间的半在线排序分析
• 3.1 引言及已知的一些结果
• max问题'>3.2 工件有任意到达时间的P1|non-increasing|C_max问题
• max问题'>3.3 工件有任意到达时间的P1|buffer|C_max问题
• 总结与展望
• 参考文献
• 附录
• 致谢