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

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