資源描述：
《淺議基于動(dòng)態(tài)遺傳算法的網(wǎng)格任務(wù)調(diào)度算法研究》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、天津大學(xué)碩士學(xué)位論文基于動(dòng)態(tài)遺傳算法的網(wǎng)格任務(wù)調(diào)度算法研究姓名：薛桂香申請(qǐng)學(xué)位級(jí)別：碩士專(zhuān)業(yè)：計(jì)算機(jī)軟件與理論指導(dǎo)教師：趙政20051201摘要將異構(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ī)。但是，他們都爹睛
2、況作了各種假設(shè)，降低了解決方案的通用性，如調(diào)度必須事先離線(xiàn)做出并且不能改變，所有的通信時(shí)間事先知道，所有的處理機(jī)具有相同的處理能力，處理機(jī)專(zhuān)門(mén)用來(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(DynamicGeneticAlgorithm)，根據(jù)網(wǎng)格系統(tǒng)各服務(wù)節(jié)點(diǎn)的計(jì)算能力、負(fù)載及網(wǎng)絡(luò)狀態(tài)進(jìn)行動(dòng)態(tài)調(diào)度，從而向用戶(hù)提供最優(yōu)性能，不僅使總的完成時(shí)間最短，還盡
3、量考慮到使主機(jī)的空閑時(shí)間最短，同時(shí)要滿(mǎn)足每個(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)度算法(如Min-min、Max-min、FCFS等)進(jìn)行了對(duì)比，試驗(yàn)結(jié)果表明，動(dòng)態(tài)遺傳算法具有很好的
4、優(yōu)化能力，提供了較好的服務(wù)質(zhì)量。關(guān)鍵詞：網(wǎng)格計(jì)算，遺傳算法，0PNET，任務(wù)調(diào)度ABSTRACTneproblemofschedulingheterogeneoustasksontoheterogeneousresources．otherwiseknownasthetaskallocationproblem,isallNP—hardproblemforthegeneralcase．Manyheuristicalgorithmsexistforspecificinstancesofthetasksc
5、hedulingproblem．butareinefficientforamoregeneralcase．TheuseofHolland’sgeneticalgorithmsinscheduling，allowsgoodsolutionstobefoundquicklyandfortheschedulertobeappliedtomoregeneralproblem．ManyresearchershaveinvestigatedtheuseofGAstoscheduletasksinhomogen
6、eousandheterogeneousmulti—processorsystems、jvitllnotableSucCeSS．Unfortunately，assumptionsareoftenmadewhichreducethegeneralityofthesesolutions，suchthatschedulingcallbecalculatedoff-lineinadvanceandcannotchange，allcommunicatiOIIStimesareknowninadvance，a
7、llprocessorshaveequalcapabilitiesandarededicatedtoprocessingtasksfromthescheduler．Theseassumptionslimitthegeneralityoftheseschedulingstrategiesinreal-worlddistributedsystems．11lemaincharactersofgridaredynamicandheterogeneous．SOthesestrategiesarenotapp
8、ropriateforgridcomputing．Desirablegoalsforgridtaskschedulingalgorithmswouldshortenaveragedelays，maximizesystemutilizationandfulfilluserconstraints．InthispaperaschedulingstrategyispresentedwhichUSeSaDynamicGA(DGA)toscheduleheterogeneoustasksont
