排序与时序最优化引论

　　线性模型的一阶可解性从可分离系数的排序规则开始，发展为梯度递增的凸性规则，再到拟阵与独立系统，从而概括一大类经典问题。二阶可解性是借助限位结构，将求解途径纳入基于交错链变换的匹配型算法。可解性的另一线索是从局部的偏序关系扩张为整体的全序关系，即偏序集的线性扩张方法。进而，一旦遇到划分结构，便进入难解性境地。证明NP-困难性的方法，是运用模拟、强迫及变尺度的技巧，构造时序问题的划分模型。在判定NP-困难性之后，精确算法主要是隐枚举，即动态规划与分枝定界。运用动态规划建立伪多项式时间算法，为近似算法做准备。难解性问题的最终归宿是近似算法设计与分析，其中性能比分析的主导思想是运用均值下界及关键工件进行结构松弛，任意精度逼近是运用伸缩尺度方法。最后，概述空间模式的顺序优化，包括车行路线、电路布线、矩阵运算、DNA基因序列重构等。

暂缺《排序与时序最优化引论》作者简介

目录
《运筹与管理科学丛书》序
前言
第1章 绪论 1
1.1 学科的定位 1
1.1.1 组合最优化 1
1.1.2 时序性组合最优化 2
1.1.3 历史注记 5
1.2 基本概念 6
1.2.1 工件-机器模型 6
1.2.2 数学模型中的机程方案 8
1.2.3 有向图与无向图 14
1.2.4 偏序关系与偏序集 17
1.2.5 数据结构中的顺序表示 18
1.2.6 模型的分类 20
1.3 选题线索概览 21
1.3.1 时序问题的组合特性 21
1.3.2 可解性与难解性 23
1.3.3 难易程度的层次分类 25
1.3.4 结构性质提要 26
1.3.5 选题范围的约定 27
习题1 28
第2章 独立性与贪婪型算法 31
2.1 可分离性结构 31
2.1.1 可分离系数的分配问题 31
2.1.2 贪婪型算法的一般形式 34
2.1.3 可分离费用的时序问题 36
2.2 可分离系数的推广——凸性排序原理 44
2.2.1 局部交换性条件 44
2.2.2 凸性的解释 47
2.2.3 工件的独立相邻关系 48
2.2.4 加权总完工时间问题 51
2.2.5 二机器流水作业问题 55
2.2.6 二机器自由作业问题 59
2.3 独立系统上的贪婪算法 62
2.3.1 独立系统与拟阵 62
2.3.2 拟阵算法应用于排序问题 65
2.3.3 单机延误数问题的贪婪算法 66
2.3.4 有到达期的延误数问题 71
2.3.5 有截止期的延误数问题 74
2.4 后向贪婪算法 77
2.4.1 一般最大费用模型 77
2.4.2 有截止期的最大费用问题 78
2.4.3 有到达期的最大费用问题 78
习题2 81
第3章 限位结构与分配型算法 84
3.1 工件与位置的可匹配性 84
3.1.1 二部图的匹配算法 84
3.1.2 匹配算法应用于时序问题 86
3.1.3 凸二部图 89
3.1.4 区间图 92
3.1.5 连续型匹配问题的Hall型定理 93
3.1.6 连续型匹配问题迭代方法 95
3.2 工件与机器的相容关系 98
3.2.1 有机器限位约束的平行机问题 98
3.2.2 具有一般目标函数的模型 103
3.2.3 具有凸性约束的特殊模型 105
3.3 可分拆工件的位置分配 108
3.3.1 可中断的平行机问题 108
3.3.2 可中断的自由作业问题 113
3.3.3 分配型线性规划方法的应用 117
3.4 连贯加工的位置约束 120
3.4.1 凸二部图与凸子集族的刻画 120
3.4.2 有连贯加工约束的时序问题 127
习题3 135
第4章 偏序结构与线性扩张算法 138
4.1 最优性条件中的偏序关系 138
4.1.1 局部优先关系扩充为最优顺序 138
4.1.2 二机器流水作业问题的偏序与半序 139
4.1.3 二机器流水作业问题的最优性准则 142
4.1.4 总延误问题中的优先关系 146
4.1.5 总延误问题的偏序扩张 150
4.1.6 总延误问题的分解原理 153
4.2 有偏序约束的单机问题 157
4.2.1 有序列平行偏序约束的问题 158
4.2.2 有树型偏序约束的问题 164
4.2.3 有一般偏序约束的单位工时问题 166
4.3 有偏序约束的多台机器问题 168
4.3.1 有树型约束的平行机问题 168
4.3.2 有一般偏序约束的平行机问题 173
4.3.3 有序列平行偏序约束的流水作业问题 178
4.4 偏序集的链分解 182
4.4.1 Dilworth定理 182
4.4.2 最小机器数平行作业问题 184
4.5 跳跃数与调整时间排序 185
4.5.1 跳跃数问题 185
4.5.2 具有调整时间的排序问题 188
习题4 190
第5章 划分结构与难解性判定 192
5.1 计算复杂性的基本概念 192
5.1.1 多项式时间算法 192
5.1.2 P 类及NP类问题 195
5.1.3 NP-完全问题及NP-困难问题 196
5.1.4 基本的NP-完全及NP-困难问题 198
5.1.5 基本证明方法I:模拟变换法 200
5.1.6 基本证明方法II:强制压迫法 203
5.2 常义NP-困难问题 206
5.2.1 以划分问题为参照问题 206
5.2.2 以背包问题为参照问题 208
5.3 强NP-困难问题 210
5.3.1 纯组合的参照问题 211
5.3.2 以3-划分问题为参照问题 217
5.4 变尺度的不等式设计方法 222
5.4.1 单机总延误问题 223
5.4.2 公共工期的加权总延误问题 231
5.4.3 可中断问题举例 236
习题5 238
第6章 递推结构与隐枚举搜索 241
6.1 动态规划的递推方法 241
6.1.1 最优化原理 241
6.1.2 含参变量的序列极值方法 244
6.1.3 独立决策过程的贪婪算法 245
6.1.4 不定期过程方法 246
6.1.5 同顺序mn排序问题 251
6.2 伪多项式时间算法的建立 255
6.2.1 背包问题 255
6.2.2 单机加权延误数问题 256
6.2.3 两台平行机的加权总完工时间问题 258
6.2.4 公共工期的加权总延误问题 260
6.2.5 单机总延误问题 262
6.3 分批排序问题的动态规划方法 263
6.3.1 加权总完工时间的分批排序 263
6.3.2 最大延迟的分批排序 267
6.3.3 延误数的分批排序 271
6.4 分枝定界方法 273
6.4.1 最优化原理的另一应用 273
6.4.2 三台机器的流水作业问题 276
6.5 启发式算法 281
6.5.1 局部邻域搜索法 281
6.5.2 汽轮机叶片排序问题 283
6.5.3 电网机组检修调度 286
习题6 288
第7章 结构松弛与近似算法 290
7.1 近似算法的逼近程度衡量 290
7.1.1 近似算法的性能比 290
7.1.2 性能比分析方法: 均值下界与关键工件 292
7.1.3 工件陆续到达情形的动态分析方法 299
7.1.4 线性规划松弛方法 306
7.2 任意精度逼近理论 312
7.2.1 多项式时间逼近方案 312
7.2.2 伪多项式时间算法的舍入变换 315
7.2.3 运用枚举搜索的逼近方法 322
7.2.4 运用划分范围的逼近方法 329
7.3 不可近似性分析 334
7.3.1 性能比的下界 334
7.3.2 排除PTAS的可能性 337
习题7 338
第8章 空间模式的序结构优化问题 340
8.1 遍历性与巡回路线最优化 340
8.1.1 遍历性问题 340
8.1.2 运输与车辆调度 341
8.1.3 中国邮递员问题 344
8.1.4 车行路由问题 345
8.2 稀疏矩阵计算的顺序优化 349
8.2.1 稀疏矩阵的存储方式 350
8.2.2 稀疏矩阵的消去与填充 354
8.2.3 图的排序与标号问题 356
8.2.4 研究课题概述 364
8.3 电路布线与顺序嵌入 371
8.3.1 网络嵌入的一般模型 371
8.3.2 线性顺序嵌入 373
8.3.3 循环顺序嵌入 375
8.3.4 二维网格嵌入 377
8.3.5 书式嵌入 379
8.4 走向更宽阔的时空优化领域 380
8.4.1 序贯决策最优化 380
8.4.2 DNA基因组序列排序问题 382
8.4.3 移位寄存器设计 385
8.4.4 频道分配问题 386
8.4.5 竞赛排名问题 387
8.4.6 从路嵌入到树嵌入 388
习题8 391
参考文献 393
时序优化问题分类索引 406
I.单机模型 406
II.平行机模型 408
III.串联机模型 409
IV.其他序结构优化模型 410
索引 412
《运筹与管理科学丛书》已出版书目 418