| 摘要 | 第1-5页 |
| ABSTRACT | 第5-8页 |
| 第一章 绪论 | 第8-15页 |
| §1.1 排序问题的背景及描述 | 第8-12页 |
| §1.1.1 排序问题的背景 | 第8页 |
| §1.1.2 排序问题的定义 | 第8-9页 |
| §1.1.3 经典排序与现代排序 | 第9-10页 |
| §1.1.4 排序问题的三参数表示 | 第10-12页 |
| §1.2 算法复杂性和NP-理论 | 第12-14页 |
| §1.2.1 算法复杂性 | 第12-13页 |
| §1.2.2 NP-理论 | 第13-14页 |
| §1.3 本文主要结果及创新点 | 第14-15页 |
| 第二章 极小化总加权完工时间及拒绝费用的批容量无界的分批排序问题 | 第15-27页 |
| §2.1 引言 | 第15-17页 |
| §2.2 问题的复杂性分析 | 第17-22页 |
| §2.3 伪多项式时间算法 | 第22-24页 |
| §2.4 问题1|B≥n|∑_(j∈s)ω_jC_j+∑_(j∈s)e_j的FPTAS | 第24-27页 |
| 第三章 两类特殊情况下的可拒绝分批排序问题 | 第27-31页 |
| §3.1 问题的描述及预备知识 | 第27页 |
| §3.2 极小化加权总完工时的有界批量可拒绝分批排序问题 | 第27-29页 |
| §3.3 极小化最大延迟的无界批量可拒绝分批排序问题 | 第29-31页 |
| 参考文献 | 第31-34页 |
| 附录一 攻读硕士期间撰写的论文 | 第34-35页 |
| 附录二 致谢 | 第35页 |
