| 摘要 | 第1-7页 |
| Abstract | 第7-9页 |
| 1 导论 | 第9-18页 |
| ·前言 | 第9-11页 |
| ·排序概述 | 第9-10页 |
| ·排序问题基础术语 | 第10-11页 |
| ·排序问题的算法与复杂性 | 第11-13页 |
| ·排序问题的求解 | 第11页 |
| ·P类和NP类 | 第11-12页 |
| ·计算复杂性 | 第12-13页 |
| ·近似算法 | 第13页 |
| ·本文研究的问题以及实际背景 | 第13-18页 |
| ·问题的定义 | 第13-15页 |
| ·问题的模型表示 | 第15-16页 |
| ·问题的实际应用背景 | 第16-17页 |
| ·本文结构 | 第17-18页 |
| 2 文献综述 | 第18-25页 |
| ·β=pmtn的平行机排序 | 第18-19页 |
| ·β=Batch setup & pmtn平行机排序 | 第19-20页 |
| ·可拆分工作平行机排序 | 第20-25页 |
| ·没有准备时间的可拆分工作平行机排序 | 第21-22页 |
| ·有独立准备时间的可拆分工作平行机排序 | 第22-23页 |
| ·有非独立准备时间的可拆分工作平行机排序 | 第23-24页 |
| ·其他类型的可拆分平行机排序 | 第24-25页 |
| 3 可拆分工作有独立准备时间的平行机排序问题Pm|s_j&splitting|Cmax | 第25-73页 |
| ·Small Batch问题的解法 | 第25-46页 |
| ·Small Batch问题的定义及已有算法 | 第25-26页 |
| ·新算法N的提出及分析 | 第26-33页 |
| ·算法N对LSU算法的改进分析 | 第33-38页 |
| ·算法N对LBT算法的改进分析 | 第38-42页 |
| ·一类特殊情况:M=2 | 第42-46页 |
| ·Large Batch问题的解法 | 第46-73页 |
| ·Large Batch问题的定义及已有算法 | 第46-48页 |
| ·一类特殊情况:M=2 | 第48-51页 |
| ·算法1:改进后的Small Batch算法(1-Optimal) | 第51-56页 |
| ·算法2:改进后的L算法(2-Optimal) | 第56-59页 |
| ·算法3:LSLSU算法(2-Optimal) | 第59-69页 |
| ·ML算法的补充证明(M-Optimal) | 第69-73页 |
| 4 可拆分工作有非独立准备时间的平行机排序问题Pm|s_(ij)&splitting|C_(max) | 第73-80页 |
| ·问题定义及已有成果 | 第73-74页 |
| ·最坏情况比的上界分析1 | 第74-77页 |
| ·最坏情况比的上界分析2 | 第77-80页 |
| 5 总结与展望 | 第80-83页 |
| ·本文的研究成果和结论 | 第80-81页 |
| ·有待进一步研究的问题 | 第81-83页 |
| 附录 | 第83-84页 |
| 参考文献 | 第84-87页 |
| 致谢 | 第87-88页 |
