《批調度與網路問題的組合算法》是2017年6月人民郵電出版社出版的圖書，作者是李曙光、於立萍、宋英傑、張斌。
基本介紹
- 中文名：批調度與網路問題的組合算法
- 作者：李曙光、於立萍、宋英傑、張斌
- ISBN：9787115455956
- 頁數：97頁
- 定價：39元
- 出版社：人民郵電出版社
- 出版時間：2017年6月
- 裝幀：平裝
- 開本：大32開
內容簡介,圖書目錄,
內容簡介
本書以作者在算法設計領域的研究成果為基礎，給出了求解批調度問題的一系列組合算法，以及求解網路最佳化問題的若干組合算法。主要研究了極小化加權完工時間和、最大延遲和最大完工時間3種調度目標函式，以及網路中的呼叫接納、利潤極大化和t區間的k染色問題等。
本書可作為從事調度理論、組合最最佳化、算法設計與套用科技人員的參考書。
圖書目錄
第 一章 緒論
第 二章 極小化加權完工時間和的批機器並行調度
第 1章 緒論 1
1.1 背景知識 1
1.2 算法複雜性的若干基礎概念 4
第 2章 極小化加權完工時間和的批機器並行調度 6
2.1 引言 6
2.2 預備知識 8
2.3 小工件 10
2.4 一般問題 13
2.4.1 動態規劃框架 13
2.4.2 工件子集的壓縮表示 14
2.4.3 在一個塊中調度工件 19
2.5 結語 22
第3章 極小化加權完工時間和的無界批機器並行調度 23
3.1 引言 23
3.2 預備知識 24
3.3 動態規劃 26
3.4 工件子集的壓縮表示 27
3.5 在一個塊中調度工件 29
3.6 結語 32
第4章 極小化最大延遲的批機器並行調度 33
4.1 引言 33
4.2 預備知識 35
4.3 小工件分批 38
4.4 調度工件 42
4.5 結語 46
第5章 工件具有尺寸的極小化最大完工時間的單機批調度 48
5.1 引言 48
5.2 預備知識 50
5.3 SBPP問題的多項式時間近似方案 50
5.3.1 簡化輸入 51
5.3.2 短工件 52
5.3.3 一般情形 55
5.4 問題BPP的一個 ( )-近似算法 59
第6章 環形網呼叫接納控制 61
6.1 引言 61
6.2 預備知識 62
6.3 無向環形網 63
6.4 有向環形網 69
6.5 結語 70
第7章 多纖網利潤極大化 71
7.1 引言 71
7.2 多纖鏈網 73
7.3 多纖環形網 76
7.4 均勻多纖環形網 77
7.5 結語 79
第8章 圈上t-區間的k-染色 80
8.1 引言 80
8.2 預備知識 81
8.3 一個3.042-近似算法 82
8.4 結語 84
附錄A 符號說明 85
參考文獻 87
