[發(fā)明專利]基于一維灰狼算法云計(jì)算任務(wù)調(diào)度方法、裝置及存儲(chǔ)介質(zhì)

在審

• 申請?zhí)枺?/td>: 202210921087.0
• 申請日: 2022-08-02
• 公開（公告）號: CN115145694A
• 公開（公告）日: 2022-10-04
• 發(fā)明（設(shè)計(jì)）人: 黃興旺;張宗良;蘇錦河;李超鵬
• 申請（專利權(quán)）人: 集美大學(xué)
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/48;G06F9/50;G06N3/00
• 代理公司: 廈門市精誠新創(chuàng)知識產(chǎn)權(quán)代理有限公司 35218
• 代理人: 張銳

本發(fā)明提供了一種基于一維灰狼算法云計(jì)算任務(wù)調(diào)度方法、裝置及存儲(chǔ)介質(zhì)，所述方法針對云計(jì)算環(huán)境下的任務(wù)調(diào)度問題，在灰狼算法中，采用了一維的實(shí)數(shù)直接編碼方式進(jìn)行編碼，使得種群大小等于待調(diào)度的任務(wù)數(shù)，每個(gè)灰狼個(gè)體表示一個(gè)任務(wù)到虛擬機(jī)節(jié)點(diǎn)的分配；進(jìn)一步地，采用貪心算法對在灰狼算法中所更新的種群進(jìn)行賦值更新，直到符合結(jié)束條件，獲取種群適應(yīng)度值最小的云調(diào)度方案作為最終的云計(jì)算任務(wù)調(diào)度方案。本發(fā)明將搜索空間降至一維，同時(shí)有機(jī)整合了進(jìn)化算法的高性能和貪心算法的高效率的優(yōu)點(diǎn)，消除了種群大小的超參設(shè)置，優(yōu)化了云計(jì)算資源分配，減少了云計(jì)算任務(wù)的總運(yùn)行時(shí)間，提高了所分配的云計(jì)算任務(wù)的計(jì)算效率。

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

本發(fā)明涉及云計(jì)算領(lǐng)域，具體涉及一種基于一維灰狼算法云計(jì)算任務(wù)調(diào)度方法、裝置及存儲(chǔ)介質(zhì)。

背景技術(shù)

隨著互聯(lián)網(wǎng)和物聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡(luò)中的數(shù)據(jù)量急劇增加，云計(jì)算因此發(fā)揮了越來越重要的作用。與網(wǎng)格計(jì)算等其他分布式計(jì)算技術(shù)相比，云計(jì)算可以為用戶提供靈活、可擴(kuò)展的服務(wù)。云提供多種類型的服務(wù)。最重要的服務(wù)是基礎(chǔ)架構(gòu)即服務(wù)(IaaS)，平臺即服務(wù)(PaaS)和軟件即服務(wù)(SaaS)。用戶可以通過互聯(lián)網(wǎng)按使用付費(fèi)的方式使用計(jì)算資源和平臺，而不需要了解底層技術(shù)。

云計(jì)算的基本工作機(jī)制是將計(jì)算任務(wù)分配給資源池中的虛擬機(jī)(VM)進(jìn)行執(zhí)行，以滿足資源需求，減少完成任務(wù)所需的時(shí)間。由于云計(jì)算是面向市場需求的應(yīng)用系統(tǒng)，為了最大限度地提高云提供商和用戶的利潤和投資回報(bào)，必須具有能夠支持軟件和用戶應(yīng)用程序、任務(wù)和工作等的高級資源調(diào)度策略。事實(shí)上，調(diào)度對系統(tǒng)性能有直接影響，比如資源利用效率和運(yùn)營成本，因此調(diào)度對云計(jì)算至關(guān)重要。

由于采用了虛擬化技術(shù)，虛擬機(jī)可以動(dòng)態(tài)配置、分配和管理，因此云計(jì)算中的調(diào)度問題通常可以分為兩個(gè)主要級別。第一級是計(jì)劃用戶提交的任務(wù)，并將其映射到一組可用的VM節(jié)點(diǎn)。第二個(gè)級別是VM和主機(jī)之間的映射，它允許在合適的主機(jī)上創(chuàng)建或遷移VM。調(diào)度用戶提交到虛擬機(jī)的任務(wù)將直接影響云計(jì)算系統(tǒng)的處理能力，優(yōu)化的調(diào)度算法可以有效提高云計(jì)算系統(tǒng)的處理能力。有效的任務(wù)調(diào)度過程需要能夠減小應(yīng)用程序的任務(wù)完工時(shí)間。因此，需要在云中使用調(diào)度任務(wù)的算法，以便以最佳方式將任務(wù)分配給資源。但是，找到解決方案所需的時(shí)間隨問題的規(guī)模大小而變化，因此該問題是NP-hard優(yōu)化問題，通常采用進(jìn)化算法或貪心算法這兩類啟發(fā)式算法進(jìn)行求解。采用進(jìn)化算法處理任務(wù)調(diào)度問題時(shí)，雖然可以十分方便地表示任務(wù)到虛擬機(jī)節(jié)點(diǎn)的映射，但存在效率低下和維度爆炸的問題。而采用貪心算法處理，則由于其采用隨機(jī)搜索或者局部搜索，因此其全局搜索能力受限，性能難以保證。

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

針對現(xiàn)有技術(shù)的上述問題，本發(fā)明提供了一種基于一維灰狼算法的云計(jì)算任務(wù)調(diào)度的方法、裝置及存儲(chǔ)介質(zhì)，以降低解空間的搜索維度，消除種群大小的超參數(shù)設(shè)置，大大優(yōu)化云調(diào)度方案，提高計(jì)算機(jī)的運(yùn)行效率。

為了實(shí)現(xiàn)上述目的，一方面提供了一種基于一維灰狼算法的云計(jì)算任務(wù)調(diào)度的方法，包括：

S1,確定云計(jì)算任務(wù)調(diào)度要解決的問題為：將N個(gè)云計(jì)算任務(wù)分配給M個(gè)虛擬機(jī)，使所述N個(gè)云計(jì)算任務(wù)的總完成時(shí)間最小，其中N和M均為自然數(shù)，其中，在灰狼算法中將所述N個(gè)云計(jì)算任務(wù)中的每一個(gè)任務(wù)分配到對應(yīng)虛擬機(jī)的調(diào)度方案的組合構(gòu)建為一個(gè)灰狼種群，所述灰狼總?cè)旱拇笮镹；

S2,采用一維的實(shí)數(shù)對所述灰狼種群進(jìn)行編碼并初始化所述灰狼種群，所述灰狼種群中，每個(gè)灰狼個(gè)體都是一維的整數(shù)，表示其中的一個(gè)計(jì)算任務(wù)到虛擬機(jī)的調(diào)度方案；

S3,將所述N個(gè)云計(jì)算任務(wù)的總完成時(shí)間作為適應(yīng)度函數(shù)計(jì)算所述灰狼種群中所有個(gè)體所表示的調(diào)度方案的適應(yīng)度值；

S4,判定所計(jì)算的適應(yīng)度值或迭代次數(shù)是否滿足預(yù)設(shè)的終止條件；如是，則將此時(shí)適應(yīng)度值最小的種群編碼作為所述N個(gè)云計(jì)算任務(wù)的最終云計(jì)算任務(wù)調(diào)度方案，并結(jié)束流程；如否，則執(zhí)行步驟S5；

S5,利用預(yù)設(shè)的貪心策略對當(dāng)前灰狼種群中選定的個(gè)體進(jìn)行更新；