基于化學反應優(yōu)化的網格任務調度研究.pdf

1、網格計算是伴隨著互聯網技術的迅速發(fā)展而產生的一種新型分布式計算模式，通過互聯網將分散的計算資源虛擬成一個超級計算機，實現跨地域的、并行分布式聯合計算，以完成重大科學領域的大規(guī)模復雜計算問題。網格任務調度是網格計算的核心技術之一，高效的網格任務調度算法可以充分利用網格系統中的計算資源，從而盡可能的使整個系統的性能達到最佳。然而，由于網格資源自身的分布性、異構性、動態(tài)性等特征，使得網格任務調度極其困難、復雜，因此，如何開發(fā)出高效的任務調度算

2、法來盡可能地提高網格系統的吞吐量是網格計算的一大挑戰(zhàn)。
　　針對網格任務調度問題，目前已經研究出了一些有效的調度策略，如基于表結構調度的最早完成時間(Heterogeneous Earliest Finish Time，HEFT)算法以及基于隨機搜索的遺傳算法、蟻群算法、模擬退火算法、禁忌算法等。這些算法皆優(yōu)缺點分明，并且網格環(huán)境中的任務調度己被證明是一個NP(Non-deterministicPolynomial)難問題，所以通

3、常也只能得到問題的近似最好解。網格環(huán)境中，存在著大量類型的調度問題，而目前所實現的解決方案并不是很多，并且不存在有效地通用調度算法，所以需要開發(fā)出更多的解決方法。
　　本文對網格任務調度的概念、特點及目標進行了介紹，并對網格環(huán)境中的任務調度方法進行了詳細地分類及介紹。針對網格環(huán)境中最主要的任務類型：依賴任務，介紹了其有向無環(huán)圖(Directed Acyclic Graph，DAG)數學模型，并在該數學模型上，提出了一種新的網格任務

4、調度算法，CROTS(Chemical ReactionOptimization for Task Scheduling)。該算法由兩部分組成，一種基于任務層次的智能任務序列搜索算法以及基于化學反應優(yōu)化(chemical reaction optimization，CRO)的處理機映射方案搜索。CRO是通過模擬化學反應中，分子運動這種自然現象得到的一種元啟發(fā)式方法，算法的核心為四種基本操作：撞墻、分解、交換以及合成。其中，分解操作有效地