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

1、本課題的研究對象是分布式環(huán)境下的多任務靜態(tài)調(diào)度問題。研究求解該問題的高效近似算法具有極高的理論價值和實踐價值。這個問題是強NP 完全的，是最難的組合優(yōu)化問題之一。各國學者已對它做了十多年的深入研究，并提出了多種調(diào)度模型和算法。 一般用有向無回路圖(Directed Acyclic Graph, DAG)來描述有優(yōu)先關系的任務集，目前文獻中只給出了有向無回路圖的存在性定義。本文提出了有向無回路圖的兩種構造性定義，使DAG 直觀化、

2、可操作化。然后將問題的約束歸納為任務約束、鏈路約束和資源約束，給出了分布式環(huán)境下多任務靜態(tài)調(diào)度問題的統(tǒng)一的、完整的描述和形式化的定義，證明了這個問題是可計算的但也是強NP 完全的，不存在任何常數(shù)近似比的多項式時間近似算法。 遵循從簡單到復雜、循序漸進的研究方法，深入地研究了同構環(huán)境下的多任務靜態(tài)調(diào)度問題。前人在這個問題的描述上，雖然采用加權的DAG 描述問題，但沒有建立問題的約束和目標的完整數(shù)學模型，尤其是允許任務復制的情況；另

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

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

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

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