排序與時序最優(yōu)化引論

目錄
《運籌與管理科學叢書》序
前言
第1章 緒論 1
1.1 學科的定位 1
1.1.1 組合最優(yōu)化 1
1.1.2 時序性組合最優(yōu)化 2
1.1.3 歷史注記 5
1.2 基本概念 6
1.2.1 工件-機器模型 6
1.2.2 數(shù)學模型中的機程方案 8
1.2.3 有向圖與無向圖 14
1.2.4 偏序關(guān)系與偏序集 17
1.2.5 數(shù)據(jù)結(jié)構(gòu)中的順序表示 18
1.2.6 模型的分類 20
1.3 選題線索概覽 21
1.3.1 時序問題的組合特性 21
1.3.2 可解性與難解性 23
1.3.3 難易程度的層次分類 25
1.3.4 結(jié)構(gòu)性質(zhì)提要 26
1.3.5 選題范圍的約定 27
習題1 28
第2章 獨立性與貪婪型算法 31
2.1 可分離性結(jié)構(gòu) 31
2.1.1 可分離系數(shù)的分配問題 31
2.1.2 貪婪型算法的一般形式 34
2.1.3 可分離費用的時序問題 36
2.2 可分離系數(shù)的推廣——凸性排序原理 44
2.2.1 局部交換性條件 44
2.2.2 凸性的解釋 47
2.2.3 工件的獨立相鄰關(guān)系 48
2.2.4 加權(quán)總完工時間問題 51
2.2.5 二機器流水作業(yè)問題 55
2.2.6 二機器自由作業(yè)問題 59
2.3 獨立系統(tǒng)上的貪婪算法 62
2.3.1 獨立系統(tǒng)與擬陣 62
2.3.2 擬陣算法應用于排序問題 65
2.3.3 單機延誤數(shù)問題的貪婪算法 66
2.3.4 有到達期的延誤數(shù)問題 71
2.3.5 有截止期的延誤數(shù)問題 74
2.4 后向貪婪算法 77
2.4.1 一般最大費用模型 77
2.4.2 有截止期的最大費用問題 78
2.4.3 有到達期的最大費用問題 78
習題2 81
第3章 限位結(jié)構(gòu)與分配型算法 84
3.1 工件與位置的可匹配性 84
3.1.1 二部圖的匹配算法 84
3.1.2 匹配算法應用于時序問題 86
3.1.3 凸二部圖 89
3.1.4 區(qū)間圖 92
3.1.5 連續(xù)型匹配問題的Hall型定理 93
3.1.6 連續(xù)型匹配問題迭代方法 95
3.2 工件與機器的相容關(guān)系 98
3.2.1 有機器限位約束的平行機問題 98
3.2.2 具有一般目標函數(shù)的模型 103
3.2.3 具有凸性約束的特殊模型 105
3.3 可分拆工件的位置分配 108
3.3.1 可中斷的平行機問題 108
3.3.2 可中斷的自由作業(yè)問題 113
3.3.3 分配型線性規(guī)劃方法的應用 117
3.4 連貫加工的位置約束 120
3.4.1 凸二部圖與凸子集族的刻畫 120
3.4.2 有連貫加工約束的時序問題 127
習題3 135
第4章 偏序結(jié)構(gòu)與線性擴張算法 138
4.1 最優(yōu)性條件中的偏序關(guān)系 138
4.1.1 局部優(yōu)先關(guān)系擴充為最優(yōu)順序 138
4.1.2 二機器流水作業(yè)問題的偏序與半序 139
4.1.3 二機器流水作業(yè)問題的最優(yōu)性準則 142
4.1.4 總延誤問題中的優(yōu)先關(guān)系 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 有序列平行偏序約束的流水作業(yè)問題 178
4.4 偏序集的鏈分解 182
4.4.1 Dilworth定理 182
4.4.2 最小機器數(shù)平行作業(yè)問題 184
4.5 跳躍數(shù)與調(diào)整時間排序 185
4.5.1 跳躍數(shù)問題 185
4.5.2 具有調(diào)整時間的排序問題 188
習題4 190
第5章 劃分結(jié)構(gòu)與難解性判定 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 變尺度的不等式設(shè)計方法 222
5.4.1 單機總延誤問題 223
5.4.2 公共工期的加權(quán)總延誤問題 231
5.4.3 可中斷問題舉例 236
習題5 238
第6章 遞推結(jié)構(gòu)與隱枚舉搜索 241
6.1 動態(tài)規(guī)劃的遞推方法 241
6.1.1 最優(yōu)化原理 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 單機加權(quán)延誤數(shù)問題 256
6.2.3 兩臺平行機的加權(quán)總完工時間問題 258
6.2.4 公共工期的加權(quán)總延誤問題 260
6.2.5 單機總延誤問題 262
6.3 分批排序問題的動態(tài)規(guī)劃方法 263
6.3.1 加權(quán)總完工時間的分批排序 263
6.3.2 最大延遲的分批排序 267
6.3.3 延誤數(shù)的分批排序 271
6.4 分枝定界方法 273
6.4.1 最優(yōu)化原理的另一應用 273
6.4.2 三臺機器的流水作業(yè)問題 276
6.5 啟發(fā)式算法 281
6.5.1 局部鄰域搜索法 281
6.5.2 汽輪機葉片排序問題 283
6.5.3 電網(wǎng)機組檢修調(diào)度 286
習題6 288
第7章 結(jié)構(gòu)松弛與近似算法 290
7.1 近似算法的逼近程度衡量 290
7.1.1 近似算法的性能比 290
7.1.2 性能比分析方法: 均值下界與關(guān)鍵工件 292
7.1.3 工件陸續(xù)到達情形的動態(tài)分析方法 299
7.1.4 線性規(guī)劃松弛方法 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章 空間模式的序結(jié)構(gòu)優(yōu)化問題 340
8.1 遍歷性與巡回路線最優(yōu)化 340
8.1.1 遍歷性問題 340
8.1.2 運輸與車輛調(diào)度 341
8.1.3 中國郵遞員問題 344
8.1.4 車行路由問題 345
8.2 稀疏矩陣計算的順序優(yōu)化 349
8.2.1 稀疏矩陣的存儲方式 350
8.2.2 稀疏矩陣的消去與填充 354
8.2.3 圖的排序與標號問題 356
8.2.4 研究課題概述 364
8.3 電路布線與順序嵌入 371
8.3.1 網(wǎng)絡嵌入的一般模型 371
8.3.2 線性順序嵌入 373
8.3.3 循環(huán)順序嵌入 375
8.3.4 二維網(wǎng)格嵌入 377
8.3.5 書式嵌入 379
8.4 走向更寬闊的時空優(yōu)化領(lǐng)域 380
8.4.1 序貫決策最優(yōu)化 380
8.4.2 DNA基因組序列排序問題 382
8.4.3 移位寄存器設(shè)計 385
8.4.4 頻道分配問題 386
8.4.5 競賽排名問題 387
8.4.6 從路嵌入到樹嵌入 388
習題8 391
參考文獻 393
時序優(yōu)化問題分類索引 406
I.單機模型 406
II.平行機模型 408
III.串聯(lián)機模型 409
IV.其他序結(jié)構(gòu)優(yōu)化模型 410
索引 412
《運籌與管理科學叢書》已出版書目 418