關鍵詞網格調度；遺傳算法；GridSim；GridBroker；仿真
1.網格資源調度簡介
在網格系統中，調度是其重要的組成部分，它要根據任務信息采用適當的策略把不同的任務分配到相應的資源結點上去運行。由於網格系統的異構性和動態性，以及運行於網格系統之中的應用程序對於資源的不同需求，使得資源調度變得極其復雜[1][2]。
壹般的網格資源調度問題已被證明是壹個NP完全問題[3][4]，因此引起了更多學者的關註，成為目前網格計算研究領域中的壹個焦點[5]。
1.1 網格調度數學模型
該數學模型定義調度算法的主要術語，不假設不支持搶先調度。並且該模型是針對已經分解的應用，即假設應用已經分解成N個任務，這些任務之間的關系分為兩種情況，即有依賴和沒有依賴。為說明問題，本文只討論簡單的無依賴的情況，數學模型假設所有的機器都是調度器可以控制的，多個任務不能在同壹個計算節點之上並發執行。
（1）自治域中存在著多個市場，每個市場可以看作是壹個虛擬組織。借助文獻[6]中的面向分組的思想，將多個任務相似的任務歸類到相同的分組。
（2）自治域內網格節點間通信延遲較小；在本文中的壹個創新想法的出處來自於文獻[6]的面向粗粒度的調度算法，在面向粗粒度的調度中，運用了壹種分組調度策略，將相似作業進行分組，再將分組提交到合適的運算資源。在建立模型的時候，在此思想的基礎之上，引入分組的思想，有效地把遺傳算法和分組（分區）結合起來，經本文後面部分的模擬實驗驗證，是壹種有效可行的方法。
（3）網格自治域中的節點數維持在壹個恒定的水平上；
由以上分析，抽象出如數學公式1.2所示：
公式1.2
1.2 抽象調度數學模型
h≥0 //任務j的需求量要大於0；
以上式中，N為壹個市場（虛擬組織）中計算資源的個數；M為任務的個數；變量i用於指示網格計算資源；變量j用於指示任務；變量k用於指示評價指標；為任務j到計算資源i的單位運輸成本；為任務j的需求量；為第k項因素在選擇模型中的影響權重，在本文中它是由專家意見以及經驗預測等獲得的權重值；為整數變量，當=1時，表示第i個計算資源被選中，反之當=0時，表示未被選中。
2.基於MGA的網格資源調度
2.1 改進遺傳算法（MGA）
本文在深入研究了基於傳統遺傳算法後[7]，提出了壹種面向分組的，並且基於優良個體特征方向來變異的變異算子。這樣，可以改進傳統遺傳算法的壹些缺陷，使其能夠有目的地、自適應地、有方向地進行變異，以此增加種群的多樣性並提高其收斂速度。
2.1.1 理論來源
在“模式定理”及“積木塊假設”基礎上，本文認為每壹個個體之所以能夠保持其優良與否的地位，原因就是其模式中具有壹些壹定的特征，對壹般的二進制和級連交叉二進制編碼來說，碼的前面部分的變動使該個體在解空間內移動的範圍(距離)比較大，而後面部分段卻恰恰相反，它們只能使得個體的解空間在該個體附近稍作變動。
比如：在1011中，從左至右階碼分別為8，4，2，1，所以如果最左邊的1變為0的時候，解空間的變化幅度就是8。而同是從1變為0，在最右邊的1所能引起的解空間變化幅度是1。
所以，可以先找出壹定的優良個體，然後從這些優良個體中提取壹些特征模式，建立起來小環境，接下來讓這些優良個體通過小（範圍）區間的變異尋優，對於那些劣質個體，就需要借鑒優良個體的特征模式從而來進行較大區間的變異。實現有目的、帶權重的變異。
2.1.2 總體思路
若有兩個染色體：
A＝()
B=()
＝（）
則分段海明距（Segment-Hamming）：
只取染色體部分編碼來計算兩個體的海明距離。對種群進行交叉操作後，從中選取壹定數量的優良個體建立小環境。
通過上面的分析，可以看出，前段的編碼對個體影響相對較大，因此，取前面壹部分的編碼用來計算兩個體的分段海明距離。用這種方式來比較兩個體是否在同壹個小環境中，若有兩個個體分段海明距離為零，則認為這樣的個體是在同壹小環境中，則只取其中壹個作為這個小環境的代表。通過對種群中提出壹定數量的這樣的優良個體，能夠建立起若幹個小環境。對於這些小環境，在每個局部範圍內進行變異搜索，采用後段編碼進行窮舉變異，找到每個小環境局部的最優(當然全局最優可能在其中)。
具體方法如下；如編碼長為12位，若為111111111010，取分段海明距離為8(指前段，即加了下畫線的那壹段不作變異)，那麽後面的4位碼長可能就有24個個體，即從0000到1111，我們窮舉這些個體(111111110000～111111111111)計算每壹個的適應度，找出它們中的最優。
●適應度函數
本文模型是壹個求最大值問題，為此建立如下適應度函數：
公式2.1.2適應度函數公式
其中，是網格調度的數學模型公式，其形式見1.2節。是是到當前所有代的最小值，且隨著代數變化。
2.2 資源調度實現過程
由上節中的數學模型知：設參與調度的任務集合為S，S={S[0]，S[1]，…S[N-1]}，其中N為任務的總數，參與調度的異構機器集合為H，H={H[0]，H[1]，…H[M-1]}，其中M為機器的數量。如果我們以調度長度為優化性能指標，則任務分配與調度的目標是將這N個計算機任務分配給這M個資源並安排好它們的執行順序，使整個任務的完成時間最短。