123,123

內(nèi)容簡(jiǎn)介

　　本書(shū)以作者在算法設(shè)計(jì)領(lǐng)域的研究成果為基礎(chǔ)，給出了求解批調(diào)度問(wèn)題的一系列組合算法，以及求解網(wǎng)絡(luò)優(yōu)化問(wèn)題的若干組合算法。主要研究了極小化加權(quán)完工時(shí)間和、*大延遲和*大完工時(shí)間3種調(diào)度目標(biāo)函數(shù)，以及網(wǎng)絡(luò)中的呼叫接納、利潤(rùn)極大化和t區(qū)間的k染色問(wèn)題等。本書(shū)可作為從事調(diào)度理論、組合*優(yōu)化、算法設(shè)計(jì)與應(yīng)用科技人員的參考書(shū)。

作者簡(jiǎn)介

　　山東工商學(xué)院計(jì)算機(jī)學(xué)院副教授。1993年大本畢業(yè)于山東師范大學(xué)數(shù)學(xué)系；2001年7月碩士研究生畢業(yè)于山東大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院并獲運(yùn)籌學(xué)專業(yè)碩士學(xué)位；2007年7月博士研究生畢業(yè)于山東大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院并獲運(yùn)籌學(xué)專業(yè)博士學(xué)位；2011年12月山東大學(xué)計(jì)算機(jī)學(xué)院博士后出站。2012年4月至10月在美國(guó)佐治亞大學(xué)做訪問(wèn)學(xué)者。研究方向?yàn)榻M合*優(yōu)化與理論計(jì)算機(jī)科學(xué)。研究領(lǐng)域包括圖論和調(diào)度理論。

圖書(shū)目錄

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