帶釋放時(shí)間的可分任務(wù)調(diào)度優(yōu)化模型與算法研究.pdf

1、隨著信息科學(xué)技術(shù)和計(jì)算機(jī)科學(xué)的飛速發(fā)展，系統(tǒng)對存儲、計(jì)算速度和帶寬的要求也在不斷的增加，單一的計(jì)算節(jié)點(diǎn)已經(jīng)無法滿足很多大規(guī)模計(jì)算密集型應(yīng)用的需求，并行與分布式平臺應(yīng)運(yùn)而生。任務(wù)調(diào)度問題是并行與分布式平臺研究和應(yīng)用必須解決的一個關(guān)鍵問題。高效的任務(wù)調(diào)度算法能夠根據(jù)并行與分布式平臺資源和任務(wù)的不同情況，在滿足一定約束的情況下，達(dá)到任務(wù)完成時(shí)間最短的目標(biāo)。但是由于分布式平臺需要考慮諸多的因素，情況也比單一節(jié)點(diǎn)復(fù)雜，如何設(shè)計(jì)出高效的任務(wù)調(diào)度算法

2、成為當(dāng)前的一個研究熱點(diǎn)?？煞秩蝿?wù)理論的提出給了設(shè)計(jì)高效的任務(wù)調(diào)度算法一種很簡單直觀且有效的思路，它在模型的簡單性和精確性之間取得了很好的折衷，因而成為并行與分布式平臺下任務(wù)調(diào)度相關(guān)問題的一個研究熱點(diǎn)。
　　本研究主要內(nèi)容包括：⑴并行與分布式系統(tǒng)下的可分任務(wù)調(diào)度問題已經(jīng)被證明是NP-hard問題，而遺傳算法作為一種啟發(fā)式隨機(jī)算法，已經(jīng)被廣泛用于NP-hard問題的求解并且有著不錯的效果。本文針對帶釋放時(shí)間的可分任務(wù)調(diào)度問題，建立了新

3、的任務(wù)調(diào)度模型，然后設(shè)計(jì)了新的遺傳算法對模型進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明了模型的有效性和算法的高效性。⑵已有的可分任務(wù)調(diào)度算法大多假設(shè)處理機(jī)在任務(wù)分配開始時(shí)刻全部處于空閑狀態(tài)，然而在實(shí)際的并行與分布式系統(tǒng)中，新的任務(wù)到來時(shí)，很多處理機(jī)可能還處于忙碌狀態(tài)。每臺處理機(jī)從忙碌狀態(tài)轉(zhuǎn)到空閑狀態(tài)的等待時(shí)間一般是不同的，即處理機(jī)具有不同的釋放時(shí)間。本文針對同構(gòu)系統(tǒng)下帶釋放時(shí)間的可分任務(wù)調(diào)度問題，詳細(xì)分析了三種不同約束條件下的任務(wù)調(diào)度過程，進(jìn)而提出了一種新

4、的帶釋放時(shí)間的可分任務(wù)調(diào)度模型，并設(shè)計(jì)了高效的全局優(yōu)化遺傳算法對其進(jìn)行求解。實(shí)驗(yàn)結(jié)果表明所提出的算法能夠根據(jù)各處理機(jī)的釋放時(shí)間合理分配任務(wù)，避免了任務(wù)的等待時(shí)間，從而減少了任務(wù)的完成時(shí)間。⑶實(shí)際的并行與分布式系統(tǒng)多由異構(gòu)的處理機(jī)構(gòu)成，而處理機(jī)的調(diào)度順序?qū)τ谌蝿?wù)的完成時(shí)間至關(guān)重要。本文針對異構(gòu)系統(tǒng)下帶釋放時(shí)間的可分任務(wù)調(diào)度問題，詳細(xì)分析了三種不同約束條件下的任務(wù)調(diào)度過程，進(jìn)而提出了一種新的帶釋放時(shí)間并同時(shí)考慮處理機(jī)最優(yōu)調(diào)度順序的可分任務(wù)調(diào)