[發(fā)明專利]一種基于改進(jìn)遺傳算法的云任務(wù)調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201410146309.1
• 申請日: 2014-04-11
• 公開（公告）號: CN103902375B
• 公開（公告）日: 2017-09-29
• 發(fā)明（設(shè)計）人: 王冠;梁社靜;周珺;陳建中;張少華
• 申請（專利權(quán)）人: 北京工業(yè)大學(xué)
• 主分類號: G06F9/48
• 分類號: G06F9/48;G06F9/50;G06N3/12;H04L29/08
• 代理公司: 北京思海天達(dá)知識產(chǎn)權(quán)代理有限公司11203
• 代理人: 張慧

1.一種基于改進(jìn)遺傳算法的云任務(wù)調(diào)度方法，其特征在于，該改進(jìn)遺傳算法為雙適應(yīng)度綜合乘積遺傳算法，在遺傳算法中增加一個適應(yīng)度函數(shù)即雙適應(yīng)度以及采用兩個適應(yīng)度相乘作為最終的適應(yīng)度函數(shù)，并把雙適應(yīng)度綜合乘積遺傳算法運(yùn)用于云環(huán)境Map/Reduce編程模型的任務(wù)調(diào)度過程中，包括如下步驟：

步驟1：用戶提交任務(wù)，用戶提交任務(wù)個數(shù)以及任務(wù)長度；

步驟2：Map/Reduce處理任務(wù)，Map/Reduce編程模型把用戶提交的任務(wù)分割成多個子任務(wù)，對這些眾多子任務(wù)進(jìn)行調(diào)度；

步驟3：尋找合適的資源節(jié)點，采用改進(jìn)的遺傳算法得到任務(wù)調(diào)度的資源序列，該序列即為執(zhí)行任務(wù)的資源節(jié)點序列；

步驟4：執(zhí)行任務(wù)，Map/Reduce編程模型根據(jù)步驟3得到的資源節(jié)點序列，把任務(wù)分配給該序列并行執(zhí)行，并把執(zhí)行結(jié)果返回給用戶。

2.如權(quán)利要求1所述一種基于改進(jìn)遺傳算法的云任務(wù)調(diào)度方法，其特征在于：需要輸入以下信息：

(1)任務(wù)信息，任務(wù)總個數(shù)T，每個任務(wù)劃分的子任務(wù)個數(shù)subNum，每個子任務(wù)的長度Length，每個子任務(wù)預(yù)計運(yùn)行時間；

(2)資源節(jié)點信息，云環(huán)境中總的資源節(jié)點個數(shù)W，每個資源處理任務(wù)的能力；

(3)遺傳算法參數(shù)，種群規(guī)模S，終止迭代數(shù)Generation，交叉概率P_c，變異概率P_m。

3.根據(jù)權(quán)利要求1所述的一種基于改進(jìn)遺傳算法的云任務(wù)調(diào)度方法，其特征在于：步驟3改進(jìn)遺傳算法中適應(yīng)度函數(shù)的選取，雙適應(yīng)度綜合乘積遺傳算法增加一個適應(yīng)度函數(shù)因子并采用因子的乘法，把資源完成任務(wù)總時間的倒數(shù)作為一個適應(yīng)度函數(shù)，平均執(zhí)行時間的倒數(shù)作為另一個適應(yīng)度函數(shù)，兩者之積作為個體最終的適應(yīng)度函數(shù)，雙適應(yīng)度綜合乘積遺傳算法的目標(biāo)是同時使任務(wù)總完成時間和平均完成時間都最短。

4.根據(jù)權(quán)利要求1所述的一種基于改進(jìn)遺傳算法的云任務(wù)調(diào)度方法，其特征在于：步驟3改進(jìn)遺傳算法中對于多個任務(wù)映射同一資源的問題，使用Min-Min算法解決該問題，優(yōu)先執(zhí)行短任務(wù)，避免長任務(wù)的阻塞問題。

5.根據(jù)權(quán)利要求1所述的一種基于改進(jìn)遺傳算法的云任務(wù)調(diào)度方法，其特征在于：步驟3改進(jìn)遺傳算法中變異操作，采用單點變異，變異后的基因值不是隨機(jī)選取的，而是根據(jù)時間矩陣選擇此任務(wù)預(yù)計執(zhí)行時間最短的資源節(jié)點，若該資源節(jié)點為任務(wù)當(dāng)前對應(yīng)的資源節(jié)點，則染色體對應(yīng)的基因值不進(jìn)行變異操作，將在新一代種群中繼續(xù)保留此染色體，反之，將該任務(wù)遷移到最短資源上去執(zhí)行，這保證了子染色體的基因優(yōu)于父染色體。