網(wǎng)格環(huán)境下任務(wù)調(diào)度算法的研究.pdf

1、網(wǎng)格環(huán)境下的任務(wù)調(diào)度問題是調(diào)度理論中的經(jīng)典問題,也屬于NP完全問題,因此很難在有限代價(jià)之內(nèi)獲取問題的最優(yōu)解。網(wǎng)格資源具有動(dòng)態(tài)性、異構(gòu)性、地理上廣泛分布和自治性等特點(diǎn),使求解該問題具有極大的挑戰(zhàn)。遺傳算法是建立在自然選擇和遺傳理論基礎(chǔ)上,是一類求解問題的并行全局的優(yōu)化搜索算法,被廣泛應(yīng)用于解決網(wǎng)格環(huán)境下的任務(wù)調(diào)度問題。本文的任務(wù)為在滿足任務(wù)約束、資源約束和截止時(shí)間限制的前提下,以最小化調(diào)度長(zhǎng)度和最小化資源數(shù)目為目標(biāo),設(shè)計(jì)出網(wǎng)格環(huán)境下任務(wù)調(diào)

2、度問題的有效近似算法。
　　本文對(duì)遺傳算法進(jìn)行了改進(jìn),改進(jìn)后的算法在編碼、選擇、雜交、變異方法上都與傳統(tǒng)遺傳算法明顯不同。采用了符號(hào)編碼,合理體現(xiàn)了問題的特點(diǎn),有效控制了問題的規(guī)模;針對(duì)雙目標(biāo)任務(wù)調(diào)度問題,提出了向量形式的適應(yīng)度函數(shù),描述了不同解決方案在各目標(biāo)函數(shù)上的性能相對(duì)關(guān)系;引入了序優(yōu)化方法進(jìn)行選擇操作,利用序比較和目標(biāo)軟化兩個(gè)基本思想解決了種群中優(yōu)秀個(gè)體的有效選擇問題;選取與編碼方案相應(yīng)的交叉、變異算子,實(shí)現(xiàn)了種群的多樣性