2005年上海大学博士学位论文 47 平行机半在线排序问题PDF电子书下载

第一章 绪论 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