| 摘要 | 第4-5页 |
| Abstract | 第5页 |
| 第一章 引言 | 第8-15页 |
| 1.1 排序的介绍 | 第8-9页 |
| 1.2 在线排序和分批排序 | 第9-11页 |
| 1.3 算法和计算复杂性 | 第11-13页 |
| 1.4 相关结果及本文主要结果 | 第13-15页 |
| 第二章 最小化加权完工时间平方和的在线分批排序问题 | 第15-24页 |
| 2.1 准备工作 | 第15-16页 |
| 2.2 有界批模型的一个常数上界 | 第16-18页 |
| 2.3 无界批模型的一个在线算法 | 第18-24页 |
| 第三章 最小化加权完工时间常数次幂和的分批排序问题 | 第24-30页 |
| 3.1 准备工作 | 第24页 |
| 3.2 几个重要引理 | 第24-27页 |
| 3.3 一个全多项式时间近似方案 | 第27-30页 |
| 后记 | 第30-31页 |
| 参考文献 | 第31-34页 |
| 致谢 | 第34页 |