| 摘要 | 第5-6页 |
| ABSTRACT | 第6页 |
| 1 绪论 | 第8-15页 |
| 1.1 排序问题 | 第8-9页 |
| 1.2 近似算法与计算复杂性 | 第9-11页 |
| 1.2.1 算法的时间复杂度 | 第9-10页 |
| 1.2.2 P，NP问题 | 第10页 |
| 1.2.3 近似算法 | 第10-11页 |
| 1.3 经典排序问题 | 第11-13页 |
| 1.4 两类排序问题 | 第13-14页 |
| 1.4.1 带时间窗口约束的排序问题 | 第13页 |
| 1.4.2 带外包选择的排序问题 | 第13-14页 |
| 1.5 论文结构 | 第14-15页 |
| 2 带时间窗口约束的单机排序问题 | 第15-24页 |
| 2.1 引言 | 第15-16页 |
| 2.2 问题在B=2的情况 | 第16-19页 |
| 2.3 问题在B≥3时的情况 | 第19-24页 |
| 3 带时间窗口约束的两台平行机排序问题 | 第24-32页 |
| 3.1 引言 | 第24-25页 |
| 3.2 B=2时LS算法的最坏情况分析 | 第25-27页 |
| 3.3 B=2时LPT算法的最坏情况分析 | 第27-28页 |
| 3.4 B≥3时的LS算法的最坏情况分析 | 第28-32页 |
| 4 一类带外包选择的单机排序问题 | 第32-35页 |
| 4.1 引言 | 第32页 |
| 4.2 ∑_IU_j+∑_Oq_j的动态规划算法 | 第32-33页 |
| 4.3 ∑_IU_j+∑_Oxp_j问题的近似算法 | 第33-35页 |
| 5 总结与展望 | 第35-36页 |
| 致谢 | 第36-37页 |
| 参考文献 | 第37-40页 |
| 附录 | 第40页 |