第一章 引言 1
1.1排序问题及复杂性理论简介 1
1.1.1排序 1
1.1.2复杂性理论简介 4
1.2本文所研究的问题 6
1.2.1背景和综述 6
1.2.2本文所研究的问题 13
1.2.3复杂性 14
1.2.4记号和定义 16
1.3本文所获得的结论 17
第二章 问题F2 （m， B） | unfixed， BI | Cmax 27
2.1问题F2（m， B）|unfiuxed，BI，aj≡a|Cmax的最优算法 27
2.2问题F2 （m， B）|unfixed， BI， bj≡bC 31
2.2.1 b≤a1，m≤B＜n （Case 1） 40
2.2.2 b≤a1，B＜m＜n （Case 2） 43
2.2.3 b≤a1，B≥n （Case 3） 46
2.2.4 b≥an，m＜B＜n （Case 4） 47
2.2.5 b≥an，B≤m＜n （Case 5） 51
2.2.6 b≥an，B≥n （Case 6） 53
2.2.7 a1≤b≤an，m=B＜n （Case 7） 54
2.2.8 a1≤b≤an，m＜B＜n （Case 8） 58
2.2.9 a1≤b≤an，B＜m＜n （Case 9） 62
2.2.10 a1≤b≤an，B≥n （Case 10） 65
2.3问题F2（m， B） | unfixed，BI | Cmax 66
2.3.1 m=B=2 66
2.3.2 max｛m，B｝＜n 88
2.3.3 B≥n 93
第三章 问题F2 （m， B） | fixed， BI |Cmax 96
3.1问题F2 （m， B）|fixed，BI，bij ≡ b|Cmax的最优算法 96
3.1.1 bij ≡ b， B≥n 96
3.1.2bij≡b， B＜n 97
3.2问题F2 （m， B）|fixed， BI | Cmax 101
3.2.1算法 101
3.2.2定理 103
第四章 问题F2 （B， m）|BI， unfixed |C 106
4.1问题F2 （B， m） | BI ， unfixed | Cmax的对称模型及其性质 106
4.2问题F2 （B， m） | BI，unfixed，aj≡a | Cmax的最优算法 108
4.3问题F2（B，m） | BI，unfixed，bj≡bC 109
4.3.1 b≤a1，m≤B＜n 110
4.3.2 b≤a1，B＜m＜n 112
4.3.3 b≤a1，B≥n 116
4.3.4 b≥an，m＜B＜n 117
4.3.5 b≥an，B≤m＜n 120
4.3.6 b≥an，B≥n 121
4.3.7 a1≤b≤an，max｛m， B｝＜n 123
4.3.8 a1≤b≤an，B≥n 124
4.4问题F2 （B， m） | BI， unfixed | Cmax 125
4.4.1 m=B=2 125
4.4.2 max{m， B｝＜n 128
4.4.3 B≥n 131
第五章 问题F2 （B， m） | B1， fixed | C 134
5.1问题F2 （B， m） | BI，fixed，bij≡bCmax的最优算法 134
5.1.1算法 134
5.1.2定理 135
5.2问题F2 （B， nm）|BI，fixed | C 135
5.2.1算法 135
5.2.2定理 137
第六章 总结与讨论 139
参考文献 141
作者在攻读博士学位期间公开发表及完成的论文 150
致谢 152