[發(fā)明專(zhuān)利]一種任務(wù)調(diào)度方法、系統(tǒng)及存儲(chǔ)介質(zhì)

在審

• 申請(qǐng)?zhí)枺?/td>: 202010085087.2
• 申請(qǐng)日: 2020-02-10
• 公開(kāi)（公告）號(hào): CN111338749A
• 公開(kāi)（公告）日: 2020-06-26
• 發(fā)明（設(shè)計(jì)）人: 周舟;韓永貴;袁余俊明;恭慶茹;劉萍;李方敏
• 申請(qǐng)（專(zhuān)利權(quán)）人: 長(zhǎng)沙學(xué)院;湖南大學(xué)
• 主分類(lèi)號(hào): G06F9/455
• 分類(lèi)號(hào): G06F9/455;G06F9/48
• 代理公司: 長(zhǎng)沙朕揚(yáng)知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 43213
• 代理人: 何湘玲

本發(fā)明涉及云計(jì)算技術(shù)領(lǐng)域，公開(kāi)了一種任務(wù)調(diào)度方法、系統(tǒng)及存儲(chǔ)介質(zhì)，可以在兼顧各個(gè)指標(biāo)的前提下實(shí)現(xiàn)高效的進(jìn)行任務(wù)調(diào)度；本發(fā)明的方法包括獲取云計(jì)算環(huán)境下用戶(hù)提交的任務(wù)作為初始任務(wù)集；為初始任務(wù)集中的每一個(gè)任務(wù)分配一個(gè)唯一對(duì)應(yīng)的編碼；計(jì)算每個(gè)編碼對(duì)應(yīng)的任務(wù)在初始任務(wù)集中的個(gè)體適應(yīng)度，根據(jù)個(gè)體適應(yīng)度計(jì)算每一個(gè)任務(wù)被隨機(jī)選中的選中概率；根據(jù)概率對(duì)初始任務(wù)集中的每個(gè)任務(wù)進(jìn)行預(yù)處理；采用貪心策略對(duì)預(yù)處理結(jié)果進(jìn)行選擇以得到任務(wù)調(diào)度的最優(yōu)解，并根據(jù)最優(yōu)解進(jìn)行任務(wù)調(diào)度。

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

本發(fā)明涉及云計(jì)算技術(shù)領(lǐng)域，尤其涉及一種任務(wù)調(diào)度方法、系統(tǒng)及存儲(chǔ)介質(zhì)。

背景技術(shù)

云計(jì)算是一種以商業(yè)為主要推動(dòng)力的計(jì)算模型和服務(wù)模式，其具體體現(xiàn)為，將數(shù)據(jù)分布到由大量遠(yuǎn)程計(jì)算機(jī)所構(gòu)成的資源池上。目前，人們所說(shuō)的云服務(wù)已經(jīng)不單單是一種分布式計(jì)算，而是分布式計(jì)算、效用計(jì)算、負(fù)載均衡、并行計(jì)算、網(wǎng)絡(luò)存儲(chǔ)、熱備份冗雜和虛擬化等計(jì)算機(jī)技術(shù)混合演進(jìn)并躍升的結(jié)果，在云計(jì)算的環(huán)境中，如何進(jìn)行合理的任務(wù)分配、實(shí)現(xiàn)最佳的調(diào)度極其必要。而目前使用的基于效率的算法都存在諸多問(wèn)題。例如采用遺傳算法實(shí)現(xiàn)任務(wù)調(diào)度，但是該種簡(jiǎn)單遺傳算法存在諸多不足，例如效率過(guò)低、在子代迭代過(guò)程中易于過(guò)早收斂于局部最優(yōu)解等。

因此，在兼顧各個(gè)指標(biāo)的前提下如何高效進(jìn)行任務(wù)調(diào)度成為一個(gè)急需解決的問(wèn)題。

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

本發(fā)明目的在于提供一種任務(wù)調(diào)度方法、系統(tǒng)及存儲(chǔ)介質(zhì)，以同時(shí)兼顧任務(wù)總執(zhí)行時(shí)間、負(fù)載平衡度、平均任務(wù)響應(yīng)時(shí)間和總服務(wù)質(zhì)量各指標(biāo)實(shí)現(xiàn)高效的任務(wù)調(diào)度。

為實(shí)現(xiàn)上述目的，本發(fā)明提供了一種任務(wù)調(diào)度方法，包括以下步驟：

獲取云計(jì)算環(huán)境下用戶(hù)提交的任務(wù)作為初始任務(wù)集；

為所述初始任務(wù)集中的每一個(gè)任務(wù)分配一個(gè)唯一對(duì)應(yīng)的編碼；

計(jì)算每個(gè)編碼對(duì)應(yīng)的任務(wù)在所述初始任務(wù)集中的個(gè)體適應(yīng)度，根據(jù)所述個(gè)體適應(yīng)度計(jì)算每一個(gè)任務(wù)被隨機(jī)選中的選中概率；

根據(jù)所述概率對(duì)所述初始任務(wù)集中的每個(gè)任務(wù)進(jìn)行預(yù)處理；

采用貪心策略對(duì)預(yù)處理結(jié)果進(jìn)行選擇以得到任務(wù)調(diào)度的最優(yōu)解，并根據(jù)所述最優(yōu)解進(jìn)行任務(wù)調(diào)度。

優(yōu)選地，所述個(gè)體適應(yīng)度的計(jì)算公式如下：

式中，c_n表示用于執(zhí)行第i個(gè)任務(wù)的虛擬機(jī)，其中，n＝1、2…n，d(c_n)表示第c_n個(gè)虛擬機(jī)預(yù)期執(zhí)行所有分派的任務(wù)所需的總時(shí)間。

優(yōu)選地，所述選中概率的計(jì)算公式如下：

式中，f(c_n)表示個(gè)體適應(yīng)度，fT(c_n)表示所述個(gè)體所在群體的群體適應(yīng)度，所述群體適應(yīng)度為所述群體中的所有個(gè)體適應(yīng)度的總和。

優(yōu)選地，所述根據(jù)所述概率對(duì)所述初始任務(wù)集中的每個(gè)任務(wù)進(jìn)行預(yù)處理具體包括：

交叉處理，根據(jù)所述選中概率選取兩個(gè)編碼對(duì)應(yīng)的任務(wù)，并將所述任務(wù)交換至對(duì)方虛擬機(jī)上，并計(jì)算交換后對(duì)應(yīng)虛擬機(jī)的總執(zhí)行時(shí)間；

重新選取兩個(gè)編碼對(duì)應(yīng)的任務(wù)重復(fù)上述交叉處理直至所述初始任務(wù)集中的每個(gè)任務(wù)都經(jīng)過(guò)交叉處理。

優(yōu)選地，所述根據(jù)所述概率對(duì)所述初始任務(wù)集中的每個(gè)任務(wù)進(jìn)行預(yù)處理具體包括：

變異處理，根據(jù)所述選中概率選取某個(gè)編碼對(duì)應(yīng)的任務(wù)，將所述任務(wù)變異為所述初始任務(wù)集中的除該任務(wù)以外的其余任務(wù)，并計(jì)算變異后對(duì)應(yīng)虛擬機(jī)的總執(zhí)行時(shí)間；

重新選取某個(gè)編碼對(duì)應(yīng)的任務(wù)重復(fù)上述變異處理直至所述初始任務(wù)集中的每個(gè)任務(wù)都經(jīng)過(guò)變異處理。