兩類解決基于光網(wǎng)絡(luò)的分布式計算系統(tǒng)的項目調(diào)度問題的混合遺傳算法.pdf

1、在這篇文章中，我們主要介紹基于光網(wǎng)絡(luò)的分布式計算系統(tǒng)的調(diào)度算法。基于光網(wǎng)絡(luò)的分布式計算系統(tǒng)通過高速低延時傳輸?shù)墓饩W(wǎng)絡(luò)將分布在不同地理位置的計算資源存儲資源等各種設(shè)備資源連接起來，為科學計算、系統(tǒng)設(shè)計和虛擬現(xiàn)實等新型應用提供計算服務(wù)。
　　本文主要研究基于光網(wǎng)絡(luò)的分布式計算系統(tǒng)中的任務(wù)調(diào)度算法。由于各類設(shè)備資源的數(shù)量有限，使用需求又非常大，所以如何提高系統(tǒng)效率就成為一個棘手的問題。而且這些資源的成本非常高，專用高速光網(wǎng)絡(luò)的運營費用更

2、是非常昂貴，所以盡快的執(zhí)行用戶提交的應用能盡可能多的降低使用者的成本。因此，基于光網(wǎng)絡(luò)的分布式計算系統(tǒng)非常需要一個高效的調(diào)度算法。
　　首先，我們對基于光網(wǎng)絡(luò)的分布式計算系統(tǒng)的任務(wù)調(diào)度進行數(shù)學建模，建立了基于任務(wù)流的DAG調(diào)度模型，并論述了該問題屬于資源約束下項目調(diào)度問題，隨后本文對資源約束下項目調(diào)度問題進行介紹。在描述完問題后，本文介紹了目前已有的對基于光網(wǎng)絡(luò)分布式計算系統(tǒng)的調(diào)度算法的研究情況。介紹了兩種解決該問題的貪心算法：經(jīng)

3、典的擴展鏈表調(diào)度算法和在此基礎(chǔ)上改進的基于調(diào)度關(guān)鍵路徑算法。
　　在介紹了已有的研究情況后，我們提出了兩類混合遺傳算法：一類是基于優(yōu)先權(quán)的混合遺傳算法，我們根據(jù)不同的權(quán)重分別設(shè)計了基于任務(wù)優(yōu)先權(quán)的混合遺傳算法以及基于通信權(quán)重和任務(wù)權(quán)重的加權(quán)混合遺傳算法；另一類是基于ELS的加權(quán)混合遺傳算法。
　　第一類算法是利用節(jié)點所代表的任務(wù)權(quán)重和有向邊所代表的通信權(quán)重進行編碼，并根據(jù)編碼值對任務(wù)進行排序的遺傳算法。根據(jù)任務(wù)的實際執(zhí)行代價

4、來調(diào)度任務(wù)。我們開發(fā)了一個仿真程序來對不同的算法性能進行評價。首先將不同算法在簡單的系統(tǒng)上的結(jié)果同用一個基于窮舉法的程序模塊計算出的最優(yōu)解進行了比較。我們還在比較復雜的系統(tǒng)上進行了實驗來衡量不同算法的性能。各組實驗都證明混合遺傳算法比貪心算法能夠計算出更好的調(diào)度結(jié)果。
　　第二類算法是一種利用ELS算法的思想進行排序的混合遺傳算法，該算法也是利用任務(wù)權(quán)重和通信權(quán)重進行編碼，然后利用底度值進行排序。我們也對該算法進行了仿真分析，并與