基于動態(tài)遺傳算法的網格任務調度算法研究.pdf

1、將異構任務調度到異構資源上的問題,即任務分配問題,一般是NP問題. 存在許多任務調度問題的具體實例的啟發(fā)式算法,但多數情況下效率都不高. Holland提出的遺傳算法應用進化策略實現了對調度空間的更快搜索,能夠更快更好的找到優(yōu)質的解.該算法在許多領域都得到了應用.許多研究者探索了遺傳算法在同構和異構多處理機上對任務調度的應用,并取得了許多成績. 但是,他們都多情況作了各種假設,降低了解決方案的通用性,如調度必須事

2、先離線做出并且不能改變,所有的通信時間事先知道,所有的處理機具有相同的處理能力,處理機專門用來處理來自調度器分配來的任務等.這些假設限制了這些調度策略在分布式系統(tǒng)中的通用性.網格具有動態(tài)性和異構性,所以這些策略不適合網格中的應用. 本文提出了一種遺傳算法的改進算法一動態(tài)遺傳算法DGA(DynamicGenetic Algorithm),根據網格系統(tǒng)各服務節(jié)點的計算能力、負載及網絡狀態(tài)進行動態(tài)調度,從而向用戶提供最優(yōu)性能,不僅使總

3、的完成時間最短,還盡量考慮到使主機的空閑時間最短,同時要滿足每個任務的deadline的要求.動態(tài)遺傳算法主要是在基本遺傳算法的基礎上,針對網格任務調度的動態(tài)特性,提出了新的編碼機制和適應度函數,能夠很好的適應空閑主機數量和等待調度任務數量的動態(tài)變化.根據新的編碼機制,重新設計了選擇算子、交叉算子和變異算子. 在OPNET環(huán)境中構建了一個局部網格的仿真模型,對所提出的動態(tài)遺傳算法進行了仿真實現,并與常見的其他網格任務調度算法(如