| 摘要 | 第1-5页 |
| ABSTRACT | 第5-10页 |
| 第一章 绪论 | 第10-21页 |
| §1.1 排序问题 | 第10-13页 |
| §1.2 现代排序 | 第13-17页 |
| §1.2.1 分批排序 | 第13-15页 |
| §1.2.2 具有恶化效应的排序 | 第15-16页 |
| §1.2.3 工件可拒绝的排序 | 第16页 |
| §1.2.4 工件可外包的排序 | 第16-17页 |
| §1.3 算法与复杂性 | 第17-19页 |
| §1.4 本文的结果 | 第19-21页 |
| 第二章 工件加工时间可退化的同类机排序问题 | 第21-32页 |
| §2.1 引言 | 第21-22页 |
| §2.2 问题描述 | 第22-23页 |
| §2.3 极小化总完工时间和极小化机器上的总负载 | 第23-29页 |
| §2.3.1 多项式时间算法 | 第23-24页 |
| §2.3.2 一个全多项式时间近似方案 | 第24-29页 |
| §2.4 极小化所有工件被送到目的地的时间 | 第29-31页 |
| §2.4.1 NP -困难的证明 | 第29页 |
| §2.4.2 一个全多项式时间近似方案 | 第29-31页 |
| §2.5 结论 | 第31-32页 |
| 第三章 工件可拒绝的继列分批排序 | 第32-42页 |
| §3.1 引言 | 第32-33页 |
| §3.2 问题描述和符号 | 第33页 |
| §3.3 模型1|s batch, rej|F1+ F2 | 第33-38页 |
| §3.3.1 极小化总完工时间和拒绝费用之和 | 第34-35页 |
| §3.3.2 极小化最大完工时间和拒绝费用之和 | 第35-36页 |
| §3.3 .3 极小化最大延迟和拒绝费用之和 | 第36-37页 |
| §3.3.4 极小化加权误工工件数和拒绝费用之和 | 第37-38页 |
| §3.4 问题1|rej, s-batch, b < n|e(C_(max)((?))/∑Re_j) | 第38-40页 |
| §3.5 结论 | 第40-42页 |
| 第四章 工件恶化和可拒绝的排序问题 | 第42-51页 |
| §4.1 引言 | 第42-43页 |
| §4.2 模型描述 | 第43页 |
| §4.3 单机问题 | 第43-47页 |
| §4.3.1 NP -困难的证明 | 第43-44页 |
| §4.3.2 特殊情形的全多项式时间近似方案 | 第44-47页 |
| §4.4 平行机问题 | 第47-50页 |
| §4.4.1 一个全多项式时间近似方案 | 第47-49页 |
| §4.4.2 特殊情况的启发式算法 | 第49-50页 |
| §4.5 结论 | 第50-51页 |
| 第五章 具有就绪时间的恶化工件及可拒绝的平行分批排序问题 | 第51-60页 |
| §5.1 引言 | 第51-52页 |
| §5.2 问题描述 | 第52页 |
| §5.3 NP -困难的证明 | 第52-54页 |
| §5.4 伪多项式时间动态规划算法 | 第54-57页 |
| §5.5 一个全多项式时间近似方案 | 第57-58页 |
| §5.6 一种特殊情况的最优算法 | 第58页 |
| §5.7 结论 | 第58-60页 |
| 第六章 工件可外包的单机继列批排序问题 | 第60-69页 |
| §6.1 引言 | 第60-61页 |
| §6.2 问题描述与符号 | 第61-62页 |
| §6.3 主要结果 | 第62-68页 |
| §6.3.1 极小化总完工时间与外包总费用的加权和 | 第62-65页 |
| §6.3.2 极小化最大延迟和外包总费用的加权和 | 第65-67页 |
| §6.3.3 极小化加权总误工工件数和外包总费用的加权和 | 第67-68页 |
| §6.4 结论 | 第68-69页 |
| 参考文献 | 第69-76页 |
| 攻读博士期间发表和完成的论文 | 第76-77页 |
| 致谢 | 第77页 |
