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

目錄
《運(yùn)籌與管理科學(xué)叢書》序
前言
第1章 緒論 1
1.1 學(xué)科的定位 1
1.1.1 組合最優(yōu)化 1
1.1.2 時(shí)序性組合最優(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 有向圖與無(wú)向圖 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 時(shí)序問(wèn)題的組合特性 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ù)的分配問(wèn)題 31
2.1.2 貪婪型算法的一般形式 34
2.1.3 可分離費(fèi)用的時(shí)序問(wèn)題 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)總完工時(shí)間問(wèn)題 51
2.2.5 二機(jī)器流水作業(yè)問(wèn)題 55
2.2.6 二機(jī)器自由作業(yè)問(wèn)題 59
2.3 獨(dú)立系統(tǒng)上的貪婪算法 62
2.3.1 獨(dú)立系統(tǒng)與擬陣 62
2.3.2 擬陣算法應(yīng)用于排序問(wèn)題 65
2.3.3 單機(jī)延誤數(shù)問(wèn)題的貪婪算法 66
2.3.4 有到達(dá)期的延誤數(shù)問(wèn)題 71
2.3.5 有截止期的延誤數(shù)問(wèn)題 74
2.4 后向貪婪算法 77
2.4.1 一般最大費(fèi)用模型 77
2.4.2 有截止期的最大費(fèi)用問(wèn)題 78
2.4.3 有到達(dá)期的最大費(fèi)用問(wèn)題 78
習(xí)題2 81
第3章 限位結(jié)構(gòu)與分配型算法 84
3.1 工件與位置的可匹配性 84
3.1.1 二部圖的匹配算法 84
3.1.2 匹配算法應(yīng)用于時(shí)序問(wèn)題 86
3.1.3 凸二部圖 89
3.1.4 區(qū)間圖 92
3.1.5 連續(xù)型匹配問(wèn)題的Hall型定理 93
3.1.6 連續(xù)型匹配問(wèn)題迭代方法 95
3.2 工件與機(jī)器的相容關(guān)系 98
3.2.1 有機(jī)器限位約束的平行機(jī)問(wèn)題 98
3.2.2 具有一般目標(biāo)函數(shù)的模型 103
3.2.3 具有凸性約束的特殊模型 105
3.3 可分拆工件的位置分配 108
3.3.1 可中斷的平行機(jī)問(wèn)題 108
3.3.2 可中斷的自由作業(yè)問(wèn)題 113
3.3.3 分配型線性規(guī)劃方法的應(yīng)用 117
3.4 連貫加工的位置約束 120
3.4.1 凸二部圖與凸子集族的刻畫 120
3.4.2 有連貫加工約束的時(shí)序問(wèn)題 127
習(xí)題3 135
第4章 偏序結(jié)構(gòu)與線性擴(kuò)張算法 138
4.1 最優(yōu)性條件中的偏序關(guān)系 138
4.1.1 局部?jī)?yōu)先關(guān)系擴(kuò)充為最優(yōu)順序 138
4.1.2 二機(jī)器流水作業(yè)問(wèn)題的偏序與半序 139
4.1.3 二機(jī)器流水作業(yè)問(wèn)題的最優(yōu)性準(zhǔn)則 142
4.1.4 總延誤問(wèn)題中的優(yōu)先關(guān)系 146
4.1.5 總延誤問(wèn)題的偏序擴(kuò)張 150
4.1.6 總延誤問(wèn)題的分解原理 153
4.2 有偏序約束的單機(jī)問(wèn)題 157
4.2.1 有序列平行偏序約束的問(wèn)題 158
4.2.2 有樹(shù)型偏序約束的問(wèn)題 164
4.2.3 有一般偏序約束的單位工時(shí)問(wèn)題 166
4.3 有偏序約束的多臺(tái)機(jī)器問(wèn)題 168
4.3.1 有樹(shù)型約束的平行機(jī)問(wèn)題 168
4.3.2 有一般偏序約束的平行機(jī)問(wèn)題 173
4.3.3 有序列平行偏序約束的流水作業(yè)問(wèn)題 178
4.4 偏序集的鏈分解 182
4.4.1 Dilworth定理 182
4.4.2 最小機(jī)器數(shù)平行作業(yè)問(wèn)題 184
4.5 跳躍數(shù)與調(diào)整時(shí)間排序 185
4.5.1 跳躍數(shù)問(wèn)題 185
4.5.2 具有調(diào)整時(shí)間的排序問(wèn)題 188
習(xí)題4 190
第5章 劃分結(jié)構(gòu)與難解性判定 192
5.1 計(jì)算復(fù)雜性的基本概念 192
5.1.1 多項(xiàng)式時(shí)間算法 192
5.1.2 P 類及NP類問(wèn)題 195
5.1.3 NP-完全問(wèn)題及NP-困難問(wèn)題 196
5.1.4 基本的NP-完全及NP-困難問(wèn)題 198
5.1.5 基本證明方法I:模擬變換法 200
5.1.6 基本證明方法II:強(qiáng)制壓迫法 203
5.2 常義NP-困難問(wèn)題 206
5.2.1 以劃分問(wèn)題為參照問(wèn)題 206
5.2.2 以背包問(wèn)題為參照問(wèn)題 208
5.3 強(qiáng)NP-困難問(wèn)題 210
5.3.1 純組合的參照問(wèn)題 211
5.3.2 以3-劃分問(wèn)題為參照問(wèn)題 217
5.4 變尺度的不等式設(shè)計(jì)方法 222
5.4.1 單機(jī)總延誤問(wèn)題 223
5.4.2 公共工期的加權(quán)總延誤問(wèn)題 231
5.4.3 可中斷問(wèn)題舉例 236
習(xí)題5 238
第6章 遞推結(jié)構(gòu)與隱枚舉搜索 241
6.1 動(dòng)態(tài)規(guī)劃的遞推方法 241
6.1.1 最優(yōu)化原理 241
6.1.2 含參變量的序列極值方法 244
6.1.3 獨(dú)立決策過(guò)程的貪婪算法 245
6.1.4 不定期過(guò)程方法 246
6.1.5 同順序mn排序問(wèn)題 251
6.2 偽多項(xiàng)式時(shí)間算法的建立 255
6.2.1 背包問(wèn)題 255
6.2.2 單機(jī)加權(quán)延誤數(shù)問(wèn)題 256
6.2.3 兩臺(tái)平行機(jī)的加權(quán)總完工時(shí)間問(wèn)題 258
6.2.4 公共工期的加權(quán)總延誤問(wèn)題 260
6.2.5 單機(jī)總延誤問(wèn)題 262
6.3 分批排序問(wèn)題的動(dòng)態(tài)規(guī)劃方法 263
6.3.1 加權(quán)總完工時(shí)間的分批排序 263
6.3.2 最大延遲的分批排序 267
6.3.3 延誤數(shù)的分批排序 271
6.4 分枝定界方法 273
6.4.1 最優(yōu)化原理的另一應(yīng)用 273
6.4.2 三臺(tái)機(jī)器的流水作業(yè)問(wèn)題 276
6.5 啟發(fā)式算法 281
6.5.1 局部鄰域搜索法 281
6.5.2 汽輪機(jī)葉片排序問(wèn)題 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á)情形的動(dòng)態(tài)分析方法 299
7.1.4 線性規(guī)劃松弛方法 306
7.2 任意精度逼近理論 312
7.2.1 多項(xiàng)式時(shí)間逼近方案 312
7.2.2 偽多項(xiàng)式時(shí)間算法的舍入變換 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)化問(wèn)題 340
8.1 遍歷性與巡回路線最優(yōu)化 340
8.1.1 遍歷性問(wèn)題 340
8.1.2 運(yùn)輸與車輛調(diào)度 341
8.1.3 中國(guó)郵遞員問(wèn)題 344
8.1.4 車行路由問(wèn)題 345
8.2 稀疏矩陣計(jì)算的順序優(yōu)化 349
8.2.1 稀疏矩陣的存儲(chǔ)方式 350
8.2.2 稀疏矩陣的消去與填充 354
8.2.3 圖的排序與標(biāo)號(hào)問(wèn)題 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 走向更寬闊的時(shí)空優(yōu)化領(lǐng)域 380
8.4.1 序貫決策最優(yōu)化 380
8.4.2 DNA基因組序列排序問(wèn)題 382
8.4.3 移位寄存器設(shè)計(jì) 385
8.4.4 頻道分配問(wèn)題 386
8.4.5 競(jìng)賽排名問(wèn)題 387
8.4.6 從路嵌入到樹(shù)嵌入 388
習(xí)題8 391
參考文獻(xiàn) 393
時(shí)序優(yōu)化問(wèn)題分類索引 406
I.單機(jī)模型 406
II.平行機(jī)模型 408
III.串聯(lián)機(jī)模型 409
IV.其他序結(jié)構(gòu)優(yōu)化模型 410
索引 412
《運(yùn)籌與管理科學(xué)叢書》已出版書目 418