本課題的研究對(duì)象是分布式環(huán)境下的多任務(wù)靜態(tài)調(diào)度問(wèn)題。研究求解該問(wèn)題的高效近似算法具有極高的理論價(jià)值和實(shí)踐價(jià)值。這個(gè)問(wèn)題是強(qiáng)NP完全的,是最難的組合優(yōu)化問(wèn)題之一。各國(guó)學(xué)者已對(duì)它做了十多年的深入研究,并提出了多種調(diào)度模型和算法。一般用有向無(wú)回路圖（Directed Acyclic Graph, DAG）來(lái)描述有優(yōu)先關(guān)系的任務(wù)集,目前文獻(xiàn)中只給出了有向無(wú)回路圖的存在性定義。本文提出了有向無(wú)回路圖的兩種構(gòu)造性定義,使DAG直觀化、可操作化。然后將問(wèn)題的約束歸納為任務(wù)約束、鏈路約束和資源約束,給出了分布式環(huán)境下多任務(wù)靜態(tài)調(diào)度問(wèn)題的統(tǒng)一的、完整的描述和形式化的定義,證明了這個(gè)問(wèn)題是可計(jì)算的但也是強(qiáng)NP完全的,不存在任何常數(shù)近似比的多項(xiàng)式時(shí)間近似算法。遵循從簡(jiǎn)單到復(fù)雜、循序漸進(jìn)的研究方法,深入地研究了同構(gòu)環(huán)境下的多任務(wù)靜態(tài)調(diào)度問(wèn)題。前人在這個(gè)問(wèn)題的描述上,雖然采用加權(quán)的DAG描述問(wèn)題,但沒(méi)有建立問(wèn)題的約束和目標(biāo)的完整數(shù)學(xué)模型,尤其是允許任務(wù)復(fù)制的情況;另外對(duì)資源的數(shù)目,或者假設(shè)有無(wú)窮多,或者作為一個(gè)參數(shù)傳入。本文將約束條件歸納為任務(wù)約束、鏈路約束和資源約束,并將資源數(shù)限定為與任務(wù)數(shù)一樣多,給出了允許... 

【文章來(lái)源】：華中科技大學(xué)湖北省 211工程院校 985工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：143 頁(yè)

【學(xué)位級(jí)別】：博士

【部分圖文】：

多級(jí)的資源調(diào)度結(jié)構(gòu)

以上分析可得出，對(duì)于樹(shù)型和規(guī)則對(duì)稱的 DAG 圖，IREA 的求解優(yōu)度中有 6 個(gè)算例得到了比上述 5 個(gè)算法更優(yōu)的解。對(duì)不規(guī)則不對(duì)稱的 D情況不是太好，但不是最差的，進(jìn)一步分析對(duì) NEQ 和 IRR 的求解過(guò)程務(wù)間的互連邊較多，動(dòng)態(tài)分團(tuán)對(duì)其幾乎不起作用，下一步將考慮如何改進(jìn)對(duì)任務(wù)間互連邊較多的 DAG 的求解。

中有 6 個(gè)算例得到了比上述 5 個(gè)算法更優(yōu)的解。對(duì)不規(guī)則不對(duì)稱的 D情況不是太好，但不是最差的，進(jìn)一步分析對(duì) NEQ 和 IRR 的求解過(guò)程務(wù)間的互連邊較多，動(dòng)態(tài)分團(tuán)對(duì)其幾乎不起作用，下一步將考慮如何改進(jìn)對(duì)任務(wù)間互連邊較多的 DAG 的求解。圖 4.7 加速比比較

【參考文獻(xiàn)】：
期刊論文
[1]網(wǎng)格環(huán)境下資源調(diào)度問(wèn)題的統(tǒng)一建模與分析[J]. 何琨,趙勇.  華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版). 2006(03)
[2]一個(gè)調(diào)度Fork-Join任務(wù)圖的最優(yōu)算法（英文）[J]. 李慶華,阮幼林,劉干,蔣盛益,楊世達(dá).  軟件學(xué)報(bào). 2005(05)
[3]網(wǎng)絡(luò)集群計(jì)算系統(tǒng)中的并行任務(wù)調(diào)度[J]. 黃金貴,陳建二,陳松喬.  計(jì)算機(jī)學(xué)報(bào). 2004(06)
[4]一個(gè)調(diào)度Fork-Join任務(wù)圖的新算法[J]. 劉振英,方濱興,姜 譽(yù),張 毅,趙 宏,張 毅.  軟件學(xué)報(bào). 2002(04)
[5]任務(wù)分配與調(diào)度的共同進(jìn)化方法[J]. 鐘求喜,謝濤,陳火旺.  計(jì)算機(jī)學(xué)報(bào). 2001(03)

博士論文
[1]網(wǎng)格工作流關(guān)鍵技術(shù)研究[D]. 張紹華.復(fù)旦大學(xué) 2004



本文編號(hào)：3236595