含有双重在线限制的排序问题

论文摘要

排序论是运筹学的一个非常活跃的分支，具有广泛而又直接的应用前景。排序问题是组合最优化领域中的一类重要问题。而在线排序因其研究的内容非常具有实际意义，从而更加引人关注。在线排序一般分为两种；列表在线排序和时间在线排序。在前一种模型里，工件是排列成一个表逐个出现的，一个工件只有当表中排在其前面的工件都安排以后才知道这个工件的有关信息。在后一种模型中，工件随着时间进行安排，在任何时刻只知道当前已到达的工件信息。在二种模型中，工件一旦被安排就不允许改变。本文研究的模型是同型机在线排序问题，其中工件的到达方式是on-line overtime，并且工件之间具有序约束（precedence constraints），目标函数是最小化最大完工时间。所以从某种意义上说，本文的排序模型是两种在线排序模型的复合（即使n个工件同时到达，它们的信息也是逐个释放的）。在第一章中，我们主要向大家介绍了排序问题产生的背景和一些相关基础知识。在第二章中，我们研究了同型机条件下双重在线复合排序问题，并证明了Greedy算法是最优的，其竞争比是2-1／m．在第三章中，我们研究了工件带有机器限制的上述模型的两种特殊情况，证明了Greedy算法仍然是这两种特殊问题的最好算法，竞争比分别是O（log m）和m（其中m为机器台数）。

论文目录

• 摘要
• Abstract
• 第一章 引言
• §1.1 排序问题
• §1.2 排序问题的复杂性刻画
• §1.3 在线排序
• 第二章 同型机上的双重复合在线排序问题
• §2.1 引言
• §2.2 相关定义及符号
• §2.3 问题描述、假设与主要结论
• 第三章 其他特殊类型的双重复合在线排序问题
• §3.1 引言
• §3.2 相关定义及符号
• §3.3 主要结论的证明
• 参考文献
• 后记