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

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

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

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