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

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

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

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