[發明專利]基于遺傳算法的動態工作流調度方法

在審

• 申請號: 201811194823.7
• 申請日: 2018-10-15
• 公開（公告）號: CN109492872A
• 公開（公告）日: 2019-03-19
• 發明（設計）人: 張軍;陳偉能;詹志輝;余維杰;周淑姿
• 申請（專利權）人: 華南理工大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06N3/12
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 李斌

1.一種基于遺傳算法的動態工作流調度方法，其特征在于，所述的調度方法包括：

S1、對動態工作流所有可能出現的流拓撲結果進行構造，通過建立一系列子圖來對應每一種可能發生的流拓撲結果，并用概率模型進行整體建模，過程如下：

S101、確定工作流中所有可能存在的拓撲結構總數n；

S102、將工作流有向無環圖改寫成子圖集合{Φ₁,Φ₂,…,Φ_n}，其中Φ_i代表該動態工作流中可能出現的一種控制流拓撲結構；

S103、建立{p₁,p₂,…,p_n}概率集合，其中p_i代表動態工作流采取Φ_i控制流拓撲結構執行工作的概率，p_i根據工作流在此前的m次歷史執行記錄信息中采取Φ_i控制流拓撲結構的次數N_i而計算得出的，m≥500，即：

并且有：

S2、對模型進行優化，其中，優化目標是找到一組工作流調度方式K，使得工作流在動態環境下執行的費用耗費的期望值

最小化，其中K.C(Φ_j)是指調度K在控制流拓撲結構Φ_j下所需的開銷。

2.根據權利要求1所述的基于遺傳算法的動態工作流調度方法，其特征在于，所述的步驟S2中對模型進行優化的過程如下：

S201、初始化算法的交叉率px、變異率pm和種群大小參數popsize，并生成第一代種群，種群中每個個體的編碼方式為

K(k₁,k₂,…,k_n)

其中，k_i表示將工作流的任務T_i匹配到相應的云計算服務執行；

S202、評價種群中每個個體的適應值，評價的方式如下：

根據動態工作流的每一種可能的控制流拓撲結構Φ_j，分別計算每個解K在該拓撲結構Φ_j下所需的執行時間K.T(Φ_j)和費用開銷K.C(Φ_j)，如果對于所有的拓撲結構{Φ₁,Φ₂,…Φ_n}，都有K.T(Φ_j)≤Deadline，即所有拓撲結構下工作流的執行時間都能夠滿足用戶所定義的完成期限Deadline，則解K的適應值K.fitness按如下式子計算：

如果該調度K在一個或多個控制流拓撲結構中有K.T(Φ_j)>Deadline，即不能滿足用戶定義的完成期限，則該解K的適應值設置為適應值的上限MAX；

S203、采用競爭選擇的方式，從上一代種群中選出popsize個個體；

S204、對上述選出的新一代群體進行交叉操作；

S205、對選擇、交叉后得到的新一代種群進一步進行變異操作

S206、對以上交叉、變異操作所得到的新一代種群的每個個體，按照步驟S202的方式進行適應值評價；

S207、用上述操作得到的新一代種群中適應值最小的最優個體替換當前一代種群的最差個體；

S208、如果當前迭代次數超出算法設定的最大迭代次數則結束優化，否則返回步驟S203繼續執行。

3.根據權利要求2所述的基于遺傳算法的動態工作流調度方法，其特征在于，所述的步驟S203過程如下：

從種群中任意選擇出兩個個體，比較這兩個個體的適應值K.fitness的大小，并從中選擇K.fitness較小的一個進入新的種群之中，按照上述過程重復執行popsize次得到popsize個進入下一代種群的個體。