批調(diào)度與網(wǎng)絡問題的組合算法

第一章 緒論
第二章 極小化加權完工時間和的批機器并行調(diào)度
第1章 緒論\t1
1．1 背景知識\t1
1．2 算法復雜性的若干基礎概念\t4
第2章 極小化加權完工時間和的批機器并行調(diào)度\t6
2．1 引言\t6
2．2 預備知識\t8
2．3 小工件\t10
2．4 一般問題\t13
2．4．1 動態(tài)規(guī)劃框架\t13
2．4．2 工件子集的壓縮表示\t14
2．4．3 在一個塊中調(diào)度工件\t19
2．5 結語\t22
第3章 極小化加權完工時間和的無界批機器并行調(diào)度\t23
3．1 引言\t23
3．2 預備知識\t24
3．3 動態(tài)規(guī)劃\t26
3．4 工件子集的壓縮表示\t27
3．5 在一個塊中調(diào)度工件\t29
3．6 結語\t32
第4章 極小化最大延遲的批機器并行調(diào)度\t33
4．1 引言\t33
4．2 預備知識\t35
4．3 小工件分批\t38
4．4 調(diào)度工件\t42
4．5 結語\t46
第5章 工件具有尺寸的極小化最大完工時間的單機批調(diào)度\t48
5．1 引言\t48
5．2 預備知識\t50
5．3 SBPP問題的多項式時間近似方案\t50
5．3．1 簡化輸入\t51
5．3．2 短工件\t52
5．3．3 一般情形\t55
5．4 問題BPP的一個 ( )-近似算法\t59
第6章 環(huán)形網(wǎng)呼叫接納控制\t61
6．1 引言\t61
6．2 預備知識\t62
6．3 無向環(huán)形網(wǎng)\t63
6．4 有向環(huán)形網(wǎng)\t69
6．5 結語\t70
第7章 多纖網(wǎng)利潤極大化\t71
7．1 引言\t71
7．2 多纖鏈網(wǎng)\t73
7．3 多纖環(huán)形網(wǎng)\t76
7．4 均勻多纖環(huán)形網(wǎng)\t77
7．5 結語\t79
第8章 圈上t-區(qū)間的k-染色\t80
8．1 引言\t80
8．2 預備知識\t81
8．3 一個3．042-近似算法\t82
8．4 結語\t84
附錄A 符號說明\t85
參考文獻\t87