第一章 绪论

1.1 排序问题

1.2 近似算法和竞争比分析

1.3 半在线排序问题

1.4 论文概述

第二章 已知工件最大加工时间的极大化目标问题

2.1 引言

2.2 三台同类机问题

2.2 m台特殊同类机问题

第三章 已知工件最大加工时间的极小化目标问题

3.1 引言

3.2 两台同类机问题

3.3 三台同类机问题

3.4 三台特殊同类机问题

3.5 m台同型机问题

第四章 已知工件总加工时间的半在线问题

4.1 1＜s＜1+？/2时的情形

4.2 s≥1+？/2的情形

4.3 Q2 min算法

第五章 带机器准备时间的已知工件总加工时间的半在线模型

5.1 P2,ri|sum|Cmin问题

5.2 Q2,ri|sum|Cmax问题

第六章 半在线模型的松弛

6.1 P2|Known largest job interval|Cmax问题

6.2 P2|Known largest job interval|Cmin问题

第七章 小结

参考文献

作者在攻读博士学位期间公开发表及完成的论文

致谢