排序與時序最最佳化引論

內容簡介

線性模型的一階可解性從可分離係數的排序規則開始，發展為梯度遞增的凸性規則，再到擬陣與獨立系統，從而概括一大類經典問題。二階可解性是藉助限位結構，將求解途徑納入基於交錯鏈變換的匹配型算法。可解性的另鑽白遷一線索是從局部的偏序關係擴張為整體的全序關係，即偏序集的線性擴張方法。進而，一旦遇到劃分結構，便進入難解性境地。證明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

排序與時序最最佳化引論

基本介紹

內容簡介

圖書目錄

相關詞條

熱門詞條