第一章 绪论 1
1.1 排序问题 1
1.2 近似算法和竞争比分析 3
1.3 半在线排序问题 6
1.4 论文概述 15
第二章 已知工件最大加工时间的极大化目标问题 18
2.1 引言 18
2.2 三台同类机问题 20
2.2 m台特殊同类机问题 28
第三章 已知工件最大加工时间的极小化目标问题 42
3.1 引言 42
3.2 两台同类机问题 44
3.3 三台同类机问题 55
3.4 三台特殊同类机问题 68
3.5 m台同型机问题 76
第四章 已知工件总加工时间的半在线问题 83
4.1 1＜s＜1+？/2时的情形 84
4.2 s≥1+？/2的情形 87
4.3 Q2 min算法 90
第五章 带机器准备时间的已知工件总加工时间的半在线模型 93
5.1 P2,ri|sum|Cmin问题 94
5.2 Q2,ri|sum|Cmax问题 97
第六章 半在线模型的松弛 111
6.1 P2|Known largest job interval|Cmax问题 113
6.2 P2|Known largest job interval|Cmin问题 118
第七章 小结 123
参考文献 125
作者在攻读博士学位期间公开发表及完成的论文 132
致谢 134