| 摘要 | 第1-4页 |
| ABSTRACT | 第4-7页 |
| 第一章 绪论 | 第7-19页 |
| ·排序和安排时间表 | 第7-9页 |
| ·排序问题的分类和特点 | 第9-11页 |
| ·排序问题的分类(三参数表示法) | 第9-11页 |
| ·排序问题的特点 | 第11页 |
| ·近似算法和竞争比分析 | 第11-14页 |
| ·在线和半在线排序 | 第14-15页 |
| ·工件有任意到达时间的(半)在线排序 | 第15-16页 |
| ·本文的特点和主要工作 | 第16-19页 |
| 第二章 工件有任意到达时间的在线排序分析 | 第19-43页 |
| ·定义及算法 | 第19-20页 |
| ·单台机模型的LS算法 | 第20-21页 |
| ·多台机模型的LS算法 | 第21页 |
| ·LS的改进算法——MLS算法 | 第21-41页 |
| ·MLS法的界的分析 | 第21-24页 |
| ·MLS算法的分析 | 第24-41页 |
| ·第一部分:估算U(L) | 第25-38页 |
| ·第二部分:定理2的证明 | 第38-41页 |
| ·总结 | 第41-43页 |
| 第三章 工件有任意到达时间的半在线排序分析 | 第43-51页 |
| ·引言及已知的一些结果 | 第43-44页 |
| ·工件有任意到达时间的P1|non-increasing|C_(max)问题 | 第44-47页 |
| ·工件有任意到达时间的P1|buffer|C_(max)问题 | 第47-51页 |
| 总结与展望 | 第51-53页 |
| 参考文献 | 第53-55页 |
| 附录 | 第55-57页 |
| 致谢 | 第57-59页 |