[發明專利]一種任務調度方法、系統及存儲介質

在審

• 申請號: 202010085087.2
• 申請日: 2020-02-10
• 公開（公告）號: CN111338749A
• 公開（公告）日: 2020-06-26
• 發明（設計）人: 周舟;韓永貴;袁余俊明;恭慶茹;劉萍;李方敏
• 申請（專利權）人: 長沙學院;湖南大學
• 主分類號: G06F9/455
• 分類號: G06F9/455;G06F9/48
• 代理公司: 長沙朕揚知識產權代理事務所(普通合伙) 43213
• 代理人: 何湘玲

1.一種任務調度方法，其特征在于，包括以下步驟：

獲取云計算環境下用戶提交的任務作為初始任務集；

為所述初始任務集中的每一個任務分配一個唯一對應的編碼；

計算每個編碼對應的任務在所述初始任務集中的個體適應度，根據所述個體適應度計算每一個任務被隨機選中的選中概率；

根據所述概率對所述初始任務集中的每個任務進行預處理；

采用貪心策略對預處理結果進行選擇以得到任務調度的最優解，并根據所述最優解進行任務調度。

2.根據權利要求1所述的任務調度方法，其特征在于，所述個體適應度的計算公式如下：

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

3.根據權利要求1所述的任務調度方法，其特征在于，所述選中概率的計算公式如下：

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

4.根據權利要求1所述的任務調度方法，其特征在于，所述根據所述概率對所述初始任務集中的每個任務進行預處理具體包括：

交叉處理，根據所述選中概率選取兩個編碼對應的任務，并將所述任務交換至對方虛擬機上，并計算交換后對應虛擬機的總執行時間；

重新選取兩個編碼對應的任務重復上述交叉處理直至所述初始任務集中的每個任務都經過交叉處理。

5.根據權利要求1所述的任務調度方法，其特征在于，所述根據所述概率對所述初始任務集中的每個任務進行預處理具體包括：

變異處理，根據所述選中概率選取某個編碼對應的任務，將所述任務變異為所述初始任務集中的除該任務以外的其余任務，并計算變異后對應虛擬機的總執行時間；

重新選取某個編碼對應的任務重復上述變異處理直至所述初始任務集中的每個任務都經過變異處理。

6.根據權利要求1所述的任務調度方法，其特征在于，所述根據所述概率對所述初始任務集中的每個任務進行預處理具體包括：交叉處理和變異處理，其中：

所述交叉處理包括：根據所述選中概率選取兩個編碼對應的任務，并將所述任務交換至對方虛擬機上，并計算交換后對應虛擬機的總執行時間；重新選取兩個編碼對應的任務重復上述交叉處理直至所述初始任務集中的每個任務都經過交叉處理；

所述變異處理包括：根據所述選中概率選取某個編碼對應的任務，將所述任務變異為所述初始任務集中的除該任務以外的其余任務，并計算變異后對應虛擬機的總執行時間；

重新選取某個編碼對應的任務重復上述變異處理直至所述初始任務集中的每個任務都經過變異處理。

7.根據權利要求1所述的任務調度方法，其特征在于，所述采用貪心策略對預處理結果進行選擇以得到任務調度的最優解包括：

根據所述編碼確定每個虛擬機的任務列，根據所述任務列計算每個虛擬機的預計執行總時間；

將所有虛擬機根據預計執行總時間按照從大到小的順序進行初始排序；

將預計執行總時間最長的虛擬機上的任務需要時長最短的任務剔除，并再次根據虛擬機執行總時間進行重新排序；

判斷經過重新排序后的當前預計執行時間最小的虛擬機是否為初始排序中預計執行時間最大的虛擬機，若是，則退出貪心選擇，反之，則將剔除的任務加入到執行時間最小的虛擬機中；

重復上述步驟。