[發(fā)明專利]一種工作流多目標(biāo)調(diào)度方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 202110611200.0
• 申請(qǐng)日: 2021-06-01
• 公開（公告）號(hào): CN113220437B
• 公開（公告）日: 2022-11-01
• 發(fā)明（設(shè)計(jì)）人: 陳進(jìn)朝;杜承烈;韓朋城;何昱;王佳輝;王麗芳;蔣澤軍;劉一帆;杜曉燕;白璐
• 申請(qǐng)（專利權(quán)）人: 西北工業(yè)大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/455;G06N3/00;G06N3/12
• 代理公司: 廣州三環(huán)專利商標(biāo)代理有限公司 44202
• 代理人: 黨娟娟;郭永麗

本發(fā)明公開了一種工作流多目標(biāo)調(diào)度方法及裝置，用以解決現(xiàn)有云計(jì)算工作流調(diào)度存在生成包含多個(gè)解的帕累托集合，存在工作流的執(zhí)行時(shí)間長(zhǎng)和執(zhí)行成本較大的問題。該方法包括采用LLH算法低層次啟發(fā)式算法庫(kù)包括的至少兩種LLH算法分別對(duì)初始種群按照設(shè)定迭代次數(shù)運(yùn)行，確定設(shè)定迭代次數(shù)后各個(gè)LLH算法包括的第一非支配解、第一HV(LLH)、第一RNI(LLH)和第一IEA(LLH)；確定各個(gè)LLH算法對(duì)應(yīng)的第一CF選擇函數(shù)；將最大第一CF對(duì)應(yīng)的LLH算法確定為第一LLH算法，根據(jù)第一LLH算法所對(duì)應(yīng)的策略更新初始種群中的個(gè)體；當(dāng)確定第一LLH算法對(duì)應(yīng)的累計(jì)迭代次數(shù)等于全部LLH算法的累計(jì)迭代最大值時(shí)，將外部種群中存儲(chǔ)的非支配解確定為工作流多目標(biāo)調(diào)度的帕累托集合。

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

本發(fā)明涉及分布式計(jì)算技術(shù)領(lǐng)域，更具體的涉及一種工作流多目標(biāo)調(diào)度方法及裝置。

背景技術(shù)

如今的大規(guī)模科學(xué)和工業(yè)應(yīng)用，比如氣候模擬、災(zāi)害預(yù)警、物聯(lián)網(wǎng)系統(tǒng)等，可以表示為一個(gè)工作流。應(yīng)用中的處理組件對(duì)應(yīng)工作流中的任務(wù)，組件之間的數(shù)據(jù)傳遞確定任務(wù)的數(shù)據(jù)依賴關(guān)系。工作流已經(jīng)成為目前最重要的表示大規(guī)模應(yīng)用的模型。由于任務(wù)的數(shù)目非常多，以及多樣化的拓?fù)浣Y(jié)構(gòu)，比如度分布和任務(wù)之間的依賴關(guān)系，這些工作流通常是非常復(fù)雜的。為了滿足用戶的各種服務(wù)質(zhì)量(quality of service，QoS)需求，這些工作流應(yīng)用通常部署在分布式系統(tǒng)上執(zhí)行。分布式系統(tǒng)包含大量的計(jì)算資源，可以同時(shí)執(zhí)行多個(gè)任務(wù)，從而提升工作流應(yīng)用的性能。傳統(tǒng)的多處理器系統(tǒng)、集群、網(wǎng)格到如今最流行的云計(jì)算系統(tǒng)都被廣泛用來執(zhí)行工作流應(yīng)用。相比傳統(tǒng)的分布式系統(tǒng)，云計(jì)算系統(tǒng)提供按需的資源訪問和按使用量計(jì)價(jià)的模式，更適合于執(zhí)行工作流應(yīng)用。由于盈利最大化是云計(jì)算廠商的首要目標(biāo)，因此在執(zhí)行工作流應(yīng)用時(shí)，既需要考慮工作流的性能，如執(zhí)行時(shí)間，也需要考慮工作流的執(zhí)行成本。執(zhí)行時(shí)間和執(zhí)行成本是兩個(gè)互相沖突的目標(biāo)，也是云計(jì)算用戶最關(guān)注的兩個(gè)QoS需求，如何在兩者之間取得平衡是工作流調(diào)度的關(guān)鍵。

云計(jì)算系統(tǒng)中工作流調(diào)度問題是非常復(fù)雜的，通常具有NP-hard和多目標(biāo)的特征。研究人員通常采用啟發(fā)式方法(heuristic)解決工作流調(diào)度問題，這些方法依賴問題特定的知識(shí)執(zhí)行，通常能夠在合理的時(shí)間內(nèi)得到計(jì)算有效的解。但是，由于工作流結(jié)構(gòu)的多樣性，特定的啟發(fā)式方法并不總能得到行之有效的解。超啟發(fā)式方法(hyper-heuristic)可以很好的解決這個(gè)問題。超啟發(fā)式方法控制一組啟發(fā)式方法，在不同的迭代階段根據(jù)特定的性能指標(biāo)采用不同的啟發(fā)式方法，充分的利用各個(gè)啟發(fā)式方法的優(yōu)點(diǎn)，避免了單個(gè)啟發(fā)式方法可能陷入局部最優(yōu)的情況，從而生成更好的解。目前有少量的為工作流調(diào)度問題設(shè)計(jì)的超啟發(fā)式方法，但是它們都是面向單目標(biāo)優(yōu)化問題的。云計(jì)算工作流調(diào)度問題本質(zhì)上是一個(gè)多目標(biāo)優(yōu)化問題，工作流的完成時(shí)間和執(zhí)行成本都是需要考慮的因素，生成的不是一個(gè)解而是一個(gè)包含許多解的帕累托集合(Pareto set)。

綜上所述，現(xiàn)有的云計(jì)算工作流調(diào)度存在生成包含多個(gè)解的帕累托集合，存在工作流的執(zhí)行時(shí)間長(zhǎng)和執(zhí)行成本較大的問題。

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

本發(fā)明實(shí)施例提供一種工作流多目標(biāo)調(diào)度方法及裝置，用以解決現(xiàn)有云計(jì)算工作流調(diào)度存在生成包含多個(gè)解的帕累托集合，存在工作流的執(zhí)行時(shí)間長(zhǎng)和執(zhí)行成本較大的問題。

本發(fā)明實(shí)施例提供一種工作流多目標(biāo)調(diào)度方法，包括：

采用LLH低層次啟發(fā)式算法庫(kù)包括的至少兩種LLH算法分別對(duì)工作流多目標(biāo)調(diào)度包括的初始種群按照設(shè)定迭代次數(shù)運(yùn)行，確定設(shè)定迭代次數(shù)后各個(gè)所述LLH算法包括的第一非支配解、第一HV(LLH)、第一RNI(LLH)和第一IEA(LLH)；

根據(jù)各個(gè)所述LLH算法的對(duì)應(yīng)的累計(jì)迭代次數(shù)以及所述LLH算法所對(duì)應(yīng)的第一HV(LLH)、第一IEA(LLH)和第一RNI(LLH)，確定各個(gè)所述LLH算法對(duì)應(yīng)的第一CF選擇函數(shù)；

將最大第一CF對(duì)應(yīng)的所述LLH算法確定為第一LLH算法，根據(jù)所述第一LLH算法所對(duì)應(yīng)的策略更新初始種群中的個(gè)體，將所述第一LLH算法對(duì)所述初始種群進(jìn)行一次迭代所得到的第二非支配解存儲(chǔ)至所述外部種群中；