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

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

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

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

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