第1章 概述 1
1.1组合优化问题的算法 1
1.1.1算法 1
1.1.2算法的评估 2
1.2排序问题的记号和模型描述 2
1.2.1排序问题的记号 2
1.2.2排序问题的模型描述 3
第2章 一台机器上的排序 6
2.1 1||nΣ j=1 ajCj 6
2.1.1算法 6
2.1.2最优性证明 6
2.1.3另一个问题 7
2.1.4 1‖1/n nΣ i=1 Ci 8
2.2 1‖nΣ i=1 vi 8
2.2.1算法 8
2.2.2最优性证明 9
2.3在某些工件必须按时交货的条件下的模型1|T|1/nΣ i=1 vi 12
2.3.1算法 13
2.3.2最优性证明 14
2.4模型1|rj≥0|nΣ i=1 vi 17
2.4.1算法 18
2.4.2 最优性证明 19
2.5 1|prec|nΣ i=1 fi（ci） 25
2.5.1枚举树 26
2.5.2 消去准则 26
2.5.3消去准则的应用 30
2.5.4下界 31
2.6 1|prec|min max i=1 fi（ci） 35
2.6.1算法 35
2.6.2最优性证明 36
2.6.3 1||min maxj｛0，cj-dj｝ 37
2.7模型1|rj≥0，pmtn，prec|min max j fj（Cj） 37
2.7.1无先后关系的模型1|rj≥0，pmtn|min max j fj（Cj） 38
2.7.2有先后关系的模型1|rj≥0，pmtn，prec|min max j fj（Cj） 40
2.8一个应用例子——循环矩阵 42
2.8.1问题的提出 42
2.8.2 实例 43
2.8.3 Hamilton循环 47
第3章 两台机器的情形 50
3.1问题的提出 50
3.1.1第一种情形 50
3.1.2第二种情形 50
3.1.3第三种情形 50
3.1.4若干指标和记号 50
3.2模型F2||Cmax 52
3.2.1算法 52
3.2.2最优性证明 52
3.3模型J2|ti≤2|Cmax 56
3.3.1算法 56
3.3.2最优性证明 56
3.4模型J2|pij=1|max Li 56
3.4.1算法 56
3.4.2最优性证明 58
3.5模型O2||Cmax 60
3.5.1问题的解法 60
3.5.2模型的一般情况 61
3.6树状或林状的工件加工系统：P|树状或林状，pj=1|Cmax 62
3.6.1问题的提出 62
3.6.2算法 63
3.6.3最优性证明 64
3.7 1|prec|min max i ri（Fi） 65
3.7.1算法 65
3.7.2 最优性证明 65
3.8 P2|pi=1，prec|Cmax 66
3.8.1问题的提出 66
3.8.2 Fujii等的算法 67
3.8.3 Edmonds的算法 67
3.8.4 M-花朵方法 69
3.8.5 CG方法 74
第4章 近似算法 77
4.1概述 77
4.1.1设计算法 77
4.1.2模拟求解 77
4.1.3近似算法求解 77
4.2近似解的定义 77
4.2.1一些定义 77
4.2.2实例 79
4.3一些排序问题的近似计算 80
4.3.1 LPT算法 80
4.3.2完工时间的估算 83
4.3.3两台机器的情形 85
4.4装箱问题 89
4.4.1 NF算法 90
4.4.2 FF算法 90
4.4.3 BF算法 96
4.5装箱问题（续） 96
4.5.1记号 97
4.5.2引理和定理 98
4.5.3例子 101
4.6 FFD算法 102
4.6.1 FFD算法的由来 102
4.6.2定理和证明 103
4.6.3更紧界的证明 111
4.6.4紧界的证明 117
4.6.5 FFD算法对小物件装箱的渐近最坏性能比 123
4.6.6附录：Csirik（1993）的有关结论及证明 129
4.7排序问题与装箱问题的联系 144
4.7.1问题简化法 144
4.7.2权函数法 145
4.7.3 FFD算法在排序问题上的运用 145
4.7.4 γm上界的改进 150
第5章 流水作业排序问题的最优算法 156
5.1消去准则 156
5.1.1排序问题的消去准则 156
5.1.2 消去准则的选取 159
5.1.3任意条件下的消去准则 163
5.2分枝定界方法 163
5.2.1定义 163
5.2.2分枝方法 164
5.3上界和下界的估计 165
5.3.1瓶颈机器 165
5.3.2下界计算 165
5.3.3上界计算 167
第6章 Steiner比猜想 169
6.1 Steiner比猜想 169
6.1.1生成树 169
6.1.2 Steiner树 171
6.1.3简单回顾 172
6.2关于n=3，4，5的情况 172
6.2.1 n=3 173
6.2.2 n=4 176
6.2.3 n=5 180
6.3一般情况 186
6.3.1问题的提出 186
6.3.2预备知识 186
6.4 Steiner比猜想的证明 191
6.4.1情形λ≥0.5 191
6.4.2情形λ＜0.5 195
6.4.3其他情形 197
6.5评注 197
第7章 多重算法 198
7.1引言 198
7.1.1简单回顾 198
7.1.2最小反例 200
7.1.3k件箱 202
7.2若干引理 202
7.2.1对△的分划 202
7.2.2△≥15/4δ和△＞5δ 202
7.2.3△≥7.5δ 204
7.2.4△＞2.5δ时的权函数 206
7.2.5最优箱 209
7.3无X4-型物件或Y2-箱 213
7.3.1无X4-型物件 213
7.3.2无Y2-型物件 214
7.4不同数值的△的多重算法 219
7.4.1 105/17δ＜△≤7.5δ 219
7.4.2 5δ≤△＜105/17δ 220
7.4.3 2.5δ≤△＜5δ 221
7.4.4 0＜△＜2.5δ 223
7.4.5 l4的若干情况 226
参考文献 230
索引 234