多任務(wù)調(diào)度問(wèn)題的研究與實(shí)現(xiàn).pdf

1、本課題的研究對(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 直觀化、

2、可操作化。然后將問(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ù)制的情況；另

3、外對(duì)資源的數(shù)目，或者假設(shè)有無(wú)窮多，或者作為一個(gè)參數(shù)傳入。本文將約束條件歸納為任務(wù)約束、鏈路約束和資源約束，并將資源數(shù)限定為與任務(wù)數(shù)一樣多，給出了允許任務(wù)復(fù)制情況下問(wèn)題的完整描述和兩種數(shù)學(xué)模型。證明了對(duì)n 個(gè)任務(wù)的問(wèn)題，給定n 個(gè)資源足夠找到無(wú)窮多資源時(shí)的最優(yōu)解，使對(duì)問(wèn)題的認(rèn)識(shí)更深入，并使問(wèn)題的描述更趨于實(shí)際。采用三種不同的方法證明了問(wèn)題具有可計(jì)算性，從不同的角度幫助加深對(duì)問(wèn)題的理解，有利于想出好的策略。 調(diào)度方法以優(yōu)先級(jí)列表、任

4、務(wù)分簇、任務(wù)復(fù)制最具代表性，其中基于任務(wù)復(fù)制的方法（Task Duplication Based, TDB）是效率最好的一種。各種TDB 算法的理論基礎(chǔ)是采用以空間換時(shí)間的策略，通過(guò)冗余地分配任務(wù)到多個(gè)資源以減少通信開(kāi)銷，從而減少總的調(diào)度長(zhǎng)度。如何準(zhǔn)確地確定應(yīng)被復(fù)制的重要任務(wù)是獲得較短makespan 的關(guān)鍵，TDB 算法之間的主要區(qū)別也正在于其選擇復(fù)制任務(wù)的策略不同。本文基于任務(wù)復(fù)制與分簇技術(shù)，提出了兩種求解同構(gòu)環(huán)境下多任務(wù)靜態(tài)調(diào)度問(wèn)

5、題的高效近似算法。 關(guān)系演化算法(IREA)模擬人類社會(huì)的關(guān)系演化過(guò)程，是一種基于貪心分簇的啟發(fā)式算法，包括前沿調(diào)度、動(dòng)態(tài)分團(tuán)、分離圖三個(gè)子算法。IREA 采用全新的優(yōu)先級(jí)規(guī)則，定義并采用關(guān)系數(shù)、發(fā)展?jié)摿Α?quán)和歸并度來(lái)表示簇的優(yōu)先級(jí)，定義并采用任務(wù)的發(fā)展?jié)摿?lái)表示任務(wù)的優(yōu)先級(jí)。實(shí)驗(yàn)表明求解的結(jié)果頗好。 目前的TDB算法中，國(guó)外學(xué)者提出的兩種先進(jìn)算法PY和MJD算法對(duì)任意的DAG給出了性能保證，而其它算法僅部分算法對(duì)特定的

6、DAG 給出了性能保證。動(dòng)態(tài)關(guān)鍵前驅(qū)算法(DCP)借鑒理論上最優(yōu)的MJD 算法的思想，并針對(duì)其不足進(jìn)行改進(jìn)，采用新的選擇策略來(lái)定義待復(fù)制的重要祖先集。改進(jìn)了粒度的定義，理論分析表明DCP 算法的優(yōu)度好于其他近現(xiàn)代的典型TDB 算法，對(duì)任意DAG 和特定DAG 均得到了好的性能保證；實(shí)驗(yàn)求解的質(zhì)量很高，且有若干算例得到了好于前人的最優(yōu)解。定義了DAG 圖的補(bǔ)圖，討論了對(duì)樹(shù)型DAG 在無(wú)任務(wù)復(fù)制情況下的2-優(yōu)度的算法。 另外，目前同