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

目錄
《運(yùn)籌與管理科學(xué)叢書》序
前言
第1章 緒論 1
1.1 學(xué)科的定位 1
1.1.1 組合最優(yōu)化 1
1.1.2 時序性組合最優(yōu)化 2
1.1.3 歷史注記 5
1.2 基本概念 6
1.2.1 工件-機(jī)器模型 6
1.2.2 數(shù)學(xué)模型中的機(jī)程方案 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
習(xí)題1 28
第2章 獨(dú)立性與貪婪型算法 31
2.1 可分離性結(jié)構(gòu) 31
2.1.1 可分離系數(shù)的分配問題 31
2.1.2 貪婪型算法的一般形式 34
2.1.3 可分離費(fèi)用的時序問題 36
2.2 可分離系數(shù)的推廣——凸性排序原理 44
2.2.1 局部交換性條件 44
2.2.2 凸性的解釋 47
2.2.3 工件的獨(dú)立相鄰關(guān)系 48
2.2.4 加權(quán)總完工時間問題 51
2.2.5 二機(jī)器流水作業(yè)問題 55
2.2.6 二機(jī)器自由作業(yè)問題 59
2.3 獨(dú)立系統(tǒng)上的貪婪算法 62
2.3.1 獨(dú)立系統(tǒng)與擬陣 62
2.3.2 擬陣算法應(yīng)用于排序問題 65
2.3.3 單機(jī)延誤數(shù)問題的貪婪算法 66
2.3.4 有到達(dá)期的延誤數(shù)問題 71
2.3.5 有截止期的延誤數(shù)問題 74
2.4 后向貪婪算法 77
2.4.1 一般最大費(fèi)用模型 77
2.4.2 有截止期的最大費(fèi)用問題 78
2.4.3 有到達(dá)期的最大費(fèi)用問題 78
習(xí)題2 81
第3章 限位結(jié)構(gòu)與分配型算法 84
3.1 工件與位置的可匹配性 84
3.1.1 二部圖的匹配算法 84
3.1.2 匹配算法應(yīng)用于時序問題 86
3.1.3 凸二部圖 89
3.1.4 區(qū)間圖 92
3.1.5 連續(xù)型匹配問題的Hall型定理 93
3.1.6 連續(xù)型匹配問題迭代方法 95
3.2 工件與機(jī)器的相容關(guān)系 98
3.2.1 有機(jī)器限位約束的平行機(jī)問題 98
3.2.2 具有一般目標(biāo)函數(shù)的模型 103
3.2.3 具有凸性約束的特殊模型 105
3.3 可分拆工件的位置分配 108
3.3.1 可中斷的平行機(jī)問題 108
3.3.2 可中斷的自由作業(yè)問題 113
3.3.3 分配型線性規(guī)劃方法的應(yīng)用 117
3.4 連貫加工的位置約束 120
3.4.1 凸二部圖與凸子集族的刻畫 120
3.4.2 有連貫加工約束的時序問題 127
習(xí)題3 135
第4章 偏序結(jié)構(gòu)與線性擴(kuò)張算法 138
4.1 最優(yōu)性條件中的偏序關(guān)系 138
4.1.1 局部優(yōu)先關(guān)系擴(kuò)充為最優(yōu)順序 138
4.1.2 二機(jī)器流水作業(yè)問題的偏序與半序 139
4.1.3 二機(jī)器流水作業(yè)問題的最優(yōu)性準(zhǔn)則 142
4.1.4 總延誤問題中的優(yōu)先關(guān)系 146
4.1.5 總延誤問題的偏序擴(kuò)張 150
4.1.6 總延誤問題的分解原理 153
4.2 有偏序約束的單機(jī)問題 157
4.2.1 有序列平行偏序約束的問題 158
4.2.2 有樹型偏序約束的問題 164
4.2.3 有一般偏序約束的單位工時問題 166
4.3 有偏序約束的多臺機(jī)器問題 168
4.3.1 有樹型約束的平行機(jī)問題 168
4.3.2 有一般偏序約束的平行機(jī)問題 173
4.3.3 有序列平行偏序約束的流水作業(yè)問題 178
4.4 偏序集的鏈分解 182
4.4.1 Dilworth定理 182
4.4.2 最小機(jī)器數(shù)平行作業(yè)問題 184
4.5 跳躍數(shù)與調(diào)整時間排序 185
4.5.1 跳躍數(shù)問題 185
4.5.2 具有調(diào)整時間的排序問題 188
習(xí)題4 190
第5章 劃分結(jié)構(gòu)與難解性判定 192
5.1 計(jì)算復(fù)雜性的基本概念 192
5.1.1 多項(xiàng)式時間算法 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:強(qiáng)制壓迫法 203
5.2 常義NP-困難問題 206
5.2.1 以劃分問題為參照問題 206
5.2.2 以背包問題為參照問題 208
5.3 強(qiáng)NP-困難問題 210
5.3.1 純組合的參照問題 211
5.3.2 以3-劃分問題為參照問題 217
5.4 變尺度的不等式設(shè)計(jì)方法 222
5.4.1 單機(jī)總延誤問題 223
5.4.2 公共工期的加權(quán)總延誤問題 231
5.4.3 可中斷問題舉例 236
習(xí)題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 獨(dú)立決策過程的貪婪算法 245
6.1.4 不定期過程方法 246
6.1.5 同順序mn排序問題 251
6.2 偽多項(xiàng)式時間算法的建立 255
6.2.1 背包問題 255
6.2.2 單機(jī)加權(quán)延誤數(shù)問題 256
6.2.3 兩臺平行機(jī)的加權(quán)總完工時間問題 258
6.2.4 公共工期的加權(quán)總延誤問題 260
6.2.5 單機(jī)總延誤問題 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)化原理的另一應(yīng)用 273
6.4.2 三臺機(jī)器的流水作業(yè)問題 276
6.5 啟發(fā)式算法 281
6.5.1 局部鄰域搜索法 281
6.5.2 汽輪機(jī)葉片排序問題 283
6.5.3 電網(wǎng)機(jī)組檢修調(diào)度 286
習(xí)題6 288
第7章 結(jié)構(gòu)松弛與近似算法 290
7.1 近似算法的逼近程度衡量 290
7.1.1 近似算法的性能比 290
7.1.2 性能比分析方法: 均值下界與關(guān)鍵工件 292
7.1.3 工件陸續(xù)到達(dá)情形的動態(tài)分析方法 299
7.1.4 線性規(guī)劃松弛方法 306
7.2 任意精度逼近理論 312
7.2.1 多項(xiàng)式時間逼近方案 312
7.2.2 偽多項(xiàng)式時間算法的舍入變換 315
7.2.3 運(yùn)用枚舉搜索的逼近方法 322
7.2.4 運(yùn)用劃分范圍的逼近方法 329
7.3 不可近似性分析 334
7.3.1 性能比的下界 334
7.3.2 排除PTAS的可能性 337
習(xí)題7 338
第8章 空間模式的序結(jié)構(gòu)優(yōu)化問題 340
8.1 遍歷性與巡回路線最優(yōu)化 340
8.1.1 遍歷性問題 340
8.1.2 運(yùn)輸與車輛調(diào)度 341
8.1.3 中國郵遞員問題 344
8.1.4 車行路由問題 345
8.2 稀疏矩陣計(jì)算的順序優(yōu)化 349
8.2.1 稀疏矩陣的存儲方式 350
8.2.2 稀疏矩陣的消去與填充 354
8.2.3 圖的排序與標(biāo)號問題 356
8.2.4 研究課題概述 364
8.3 電路布線與順序嵌入 371
8.3.1 網(wǎng)絡(luò)嵌入的一般模型 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è)計(jì) 385
8.4.4 頻道分配問題 386
8.4.5 競賽排名問題 387
8.4.6 從路嵌入到樹嵌入 388
習(xí)題8 391
參考文獻(xiàn) 393
時序優(yōu)化問題分類索引 406
I.單機(jī)模型 406
II.平行機(jī)模型 408
III.串聯(lián)機(jī)模型 409
IV.其他序結(jié)構(gòu)優(yōu)化模型 410
索引 412
《運(yùn)籌與管理科學(xué)叢書》已出版書目 418