[發(fā)明專利]基于遺傳算法的動(dòng)態(tài)工作流調(diào)度方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201811194823.7
• 申請(qǐng)日: 2018-10-15
• 公開（公告）號(hào): CN109492872A
• 公開（公告）日: 2019-03-19
• 發(fā)明（設(shè)計(jì)）人: 張軍;陳偉能;詹志輝;余維杰;周淑姿
• 申請(qǐng)（專利權(quán)）人: 華南理工大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06;G06N3/12
• 代理公司: 廣州市華學(xué)知識(shí)產(chǎn)權(quán)代理有限公司 44245
• 代理人: 李斌

本發(fā)明公開了一種基于遺傳算法的動(dòng)態(tài)工作流調(diào)度方法，該調(diào)度方法的目標(biāo)是在滿足用戶所指定的最大執(zhí)行周期約束和工作流一個(gè)周期的總執(zhí)行時(shí)間約束下，優(yōu)化工作流的每個(gè)周期的平均費(fèi)用。由于工作流在云計(jì)算的實(shí)現(xiàn)環(huán)境下執(zhí)行方式是動(dòng)態(tài)多變的，所以本發(fā)明對(duì)動(dòng)態(tài)工作流所有可能出現(xiàn)的流拓?fù)浣Y(jié)果進(jìn)行構(gòu)造，通過建立一系列子圖來對(duì)應(yīng)每一種可能發(fā)生的流拓?fù)浣Y(jié)果，并用概率模型進(jìn)行整體建模，從而綜合考慮了工作流的動(dòng)態(tài)時(shí)變的特性，并采用遺傳算法對(duì)工作流在動(dòng)態(tài)環(huán)境中執(zhí)行的周期費(fèi)用進(jìn)行優(yōu)化，從而提高了工作流的執(zhí)行效率。

技術(shù)領(lǐng)域

本發(fā)明涉及云計(jì)算以及智能算法技術(shù)領(lǐng)域，具體涉及一種基于遺傳算 法的動(dòng)態(tài)工作流調(diào)度方法。

背景技術(shù)

云計(jì)算通過對(duì)大量計(jì)算資源的虛擬聚合和共享，實(shí)現(xiàn)按需向用戶提供 各種各樣的計(jì)算服務(wù)，因此能夠滿足日益增長的大數(shù)據(jù)處理需求。為了進(jìn) 一步提高云計(jì)算系統(tǒng)對(duì)大數(shù)據(jù)的管理和處理能力，如何合理、高效地調(diào)度 云計(jì)算的資源從而實(shí)現(xiàn)向用戶彈性地提供計(jì)算服務(wù)是提高云計(jì)算系統(tǒng)性 能的關(guān)鍵。

在云計(jì)算環(huán)境中，由于云計(jì)算資源的數(shù)量龐大、云系統(tǒng)所承擔(dān)的計(jì)算 服務(wù)量也相當(dāng)巨大，云網(wǎng)絡(luò)的使用狀態(tài)也時(shí)刻變化，因此動(dòng)態(tài)時(shí)變性是云 計(jì)算系統(tǒng)運(yùn)作過程中所具有的重要特征。在應(yīng)用云計(jì)算處理大數(shù)據(jù)計(jì)算任 務(wù)時(shí)，一類常用的任務(wù)組織方式是工作流。工作流定義為一個(gè)完成復(fù)雜目 標(biāo)的特定的任務(wù)序列。通常地，工作流可以通過有向無環(huán)圖(DAG)的形式 給出，圖的節(jié)點(diǎn)表示單個(gè)任務(wù)，而節(jié)點(diǎn)之間的有向邊表示任務(wù)之間的優(yōu)先 約束關(guān)系。然而，在現(xiàn)有的工作流調(diào)度模型中，一個(gè)工作流的控制流拓?fù)?結(jié)構(gòu)是固定不變的，即是由單一的DAG給出。在實(shí)際應(yīng)用中，工作流的控 制流結(jié)構(gòu)可能還具有IF-THEN等選擇分支，其控制流拓?fù)浣Y(jié)構(gòu)也具有動(dòng)態(tài) 時(shí)變的特性，如何能夠在工作流調(diào)度過程中考慮云環(huán)境和工作流控制拓?fù)?的動(dòng)態(tài)時(shí)變特性，從而進(jìn)一步提高工作流調(diào)度系統(tǒng)在動(dòng)態(tài)、時(shí)變環(huán)境中的 可用性，對(duì)工作流調(diào)度方法提出了新的挑戰(zhàn)。

隨著優(yōu)化技術(shù)的發(fā)展，如遺傳算法等新型的元啟發(fā)式智能計(jì)算方法為 復(fù)雜優(yōu)化問題的求解提供了新的有效手段。遺傳算法是模擬自然界生物的 進(jìn)化現(xiàn)象而提出的一種隨機(jī)式優(yōu)化方法，它自20世紀(jì)60年代提出以來引 起了廣泛的關(guān)注，并且已經(jīng)被成功地應(yīng)用于眾多科學(xué)與工程領(lǐng)域的應(yīng)用中。 Jakimovski提出了一種利用遺傳算法優(yōu)化網(wǎng)格工作流的方法，然而對(duì)于動(dòng) 態(tài)工作流中可能包含多個(gè)流拓?fù)浣Y(jié)構(gòu)的特點(diǎn)，該算法并不能直接進(jìn)行優(yōu)化。

發(fā)明內(nèi)容

本發(fā)明的目的是為了解決現(xiàn)有技術(shù)中的上述缺陷，提供一種基于遺傳 算法的動(dòng)態(tài)工作流調(diào)度方法。

本發(fā)明的目的可以通過采取如下技術(shù)方案達(dá)到：

一種基于遺傳算法的動(dòng)態(tài)工作流調(diào)度方法，所述的調(diào)度方法包括：

S1、對(duì)動(dòng)態(tài)工作流所有可能出現(xiàn)的流拓?fù)浣Y(jié)果進(jìn)行構(gòu)造，通過建立一 系列子圖來對(duì)應(yīng)每一種可能發(fā)生的流拓?fù)浣Y(jié)果，并用概率模型進(jìn)行整體建 模，過程如下：

S101、確定工作流中所有可能存在的拓?fù)浣Y(jié)構(gòu)總數(shù)n；

S102、將工作流有向無環(huán)圖改寫成子圖集合{Φ₁,Φ₂,…,Φ_n}，其中Φ_i代 表該動(dòng)態(tài)工作流中可能出現(xiàn)的一種控制流拓?fù)浣Y(jié)構(gòu)；

S103、建立{p₁,p₂,…,p_n}概率集合，其中p_i代表動(dòng)態(tài)工作流采取Φ_i控 制流拓?fù)浣Y(jié)構(gòu)執(zhí)行工作的概率，p_i根據(jù)工作流在此前的m次歷史執(zhí)行記錄 信息中采取Φ_i控制流拓?fù)浣Y(jié)構(gòu)的次數(shù)N_i而計(jì)算得出的，m≥500，即：

并且有：