[發(fā)明專利]任務(wù)分配方法及任務(wù)分配裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 202111663346.6
• 申請(qǐng)日: 2021-12-30
• 公開（公告）號(hào): CN114461386A
• 公開（公告）日: 2022-05-10
• 發(fā)明（設(shè)計(jì)）人: 束柬;徐生;王金钖;陳劍波;況夫容
• 申請(qǐng)（專利權(quán)）人: 科大訊飛股份有限公司
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50;G06N3/12
• 代理公司: 北京布瑞知識(shí)產(chǎn)權(quán)代理有限公司 11505
• 代理人: 宋琪

1.一種任務(wù)分配方法，其特征在于，包括：

對(duì)多個(gè)計(jì)算任務(wù)和多個(gè)計(jì)算資源單元進(jìn)行定量化表征，得到定量表征結(jié)果；

針對(duì)所述多個(gè)計(jì)算任務(wù)和所述多個(gè)計(jì)算資源單元，根據(jù)所述定量表征結(jié)果確定多個(gè)目標(biāo)函數(shù)和對(duì)應(yīng)的多個(gè)約束條件；

基于所述多個(gè)約束條件，利用多目標(biāo)優(yōu)化算法對(duì)所述多個(gè)目標(biāo)函數(shù)進(jìn)行求解，獲得非劣解集，其中，所述非劣解集中的每個(gè)非劣解對(duì)應(yīng)一種任務(wù)分配策略；

從所述非劣解集中選擇最優(yōu)解，并根據(jù)所述最優(yōu)解將所述多個(gè)計(jì)算任務(wù)分配到所述多個(gè)計(jì)算資源單元上執(zhí)行。

2.根據(jù)權(quán)利要求1所述的任務(wù)分配方法，其特征在于，所述多目標(biāo)優(yōu)化算法包括遺傳算法，并且所述遺傳算法在求解搜索過程中遺傳算子針對(duì)的序列的長度是可變的。

3.根據(jù)權(quán)利要求2所述的任務(wù)分配方法，其特征在于，所述遺傳算法包括：

a、隨機(jī)生成的N_p個(gè)可行解，作為初始化種群P；并生成一個(gè)外部存檔集Q，并令Q為空；

b、為所述初始化種群分配適應(yīng)度并執(zhí)行環(huán)境選擇過程；

c、判斷是否滿足終止條件；

d、當(dāng)滿足所述終止條件時(shí)，返回所述外部存檔集Q中的解作為所述非劣解集；

e、當(dāng)不滿足所述終止條件時(shí)，執(zhí)行配對(duì)選擇操作，并且基于序列長度可變的遺傳算子執(zhí)行進(jìn)化操作，獲得新種群；

將所述新種群中的N_p個(gè)可行解作為所述初始化種群，迭代執(zhí)行上述步驟b至步驟e。

4.根據(jù)權(quán)利要求3所述的任務(wù)分配方法，其特征在于，所述遺傳算子包括交叉算子，所述基于序列長度可變的遺傳算子執(zhí)行進(jìn)化操作，獲得新種群，包括：

隨機(jī)選取滿足所述多個(gè)目標(biāo)函數(shù)的任意兩個(gè)待交叉可行解中的交叉起始點(diǎn)；

從所述交叉起始點(diǎn)向左或向右逐項(xiàng)對(duì)所述任意兩個(gè)待交叉可行解進(jìn)行交叉操作；

計(jì)算每次交叉操作生成的每個(gè)新可行解的多個(gè)目標(biāo)函數(shù)值；

當(dāng)所述交叉操作生成的其中一個(gè)新可行解的多個(gè)目標(biāo)函數(shù)值完全劣于交叉操作前的任一解的多個(gè)目標(biāo)函數(shù)值時(shí)，交叉操作停止。

5.根據(jù)權(quán)利要求3所述的任務(wù)分配方法，其特征在于，所述遺傳算子包括變異算子，所述基于序列長度可變的遺傳算子執(zhí)行進(jìn)化操作，獲得新種群，包括：

隨機(jī)選取滿足所述多個(gè)目標(biāo)函數(shù)的待變異可行解中的變異點(diǎn)位置；

從所述變異點(diǎn)位置向左或向右逐項(xiàng)對(duì)所述待變異可行解進(jìn)行變異操作；

計(jì)算每次變異操作生成的新解的多個(gè)目標(biāo)函數(shù)值；

當(dāng)所述變異操作生成的新解的多個(gè)目標(biāo)函數(shù)值非完全劣于變異操作前的任一解的多個(gè)目標(biāo)函數(shù)值時(shí)，變異操作繼續(xù)進(jìn)行；

當(dāng)所述變異操作生成的新解的多個(gè)目標(biāo)函數(shù)值完全劣于變異操作前的任一解的多個(gè)目標(biāo)函數(shù)值時(shí)，變異操作停止。

6.根據(jù)權(quán)利要求5所述的任務(wù)分配方法，其特征在于，還包括：

對(duì)每次變異操作生成的新解進(jìn)行資源約束判斷，并丟棄產(chǎn)生的無效解。

7.根據(jù)權(quán)利要求1至6中的任一項(xiàng)所述的任務(wù)分配方法，其特征在于，所述目標(biāo)函數(shù)包括時(shí)間函數(shù)、執(zhí)行成本函數(shù)和/或服務(wù)質(zhì)量函數(shù)。

8.根據(jù)權(quán)利要求7所述的任務(wù)分配方法，其特征在于，所述時(shí)間函數(shù)滿足：所述多個(gè)計(jì)算任務(wù)的總運(yùn)行時(shí)間最短，其中，所述多個(gè)計(jì)算任務(wù)中的每個(gè)計(jì)算任務(wù)的運(yùn)行時(shí)間用所述計(jì)算任務(wù)的任務(wù)計(jì)算量除以對(duì)應(yīng)計(jì)算資源單元的計(jì)算效率來表征。

9.根據(jù)權(quán)利要求7所述的任務(wù)分配方法，其特征在于，所述執(zhí)行成本函數(shù)滿足：所述多個(gè)計(jì)算任務(wù)的總執(zhí)行成本最低，其中，所述多個(gè)計(jì)算任務(wù)中的每個(gè)計(jì)算任務(wù)的執(zhí)行成本用所述計(jì)算任務(wù)的運(yùn)行時(shí)間乘以對(duì)應(yīng)計(jì)算資源單元的單位計(jì)算成本來表征。

10.根據(jù)權(quán)利要求7所述的任務(wù)分配方法，其特征在于，所述服務(wù)質(zhì)量函數(shù)滿足：所述多個(gè)計(jì)算任務(wù)的總服務(wù)質(zhì)量最高，其中，所述多個(gè)計(jì)算任務(wù)中的每個(gè)計(jì)算任務(wù)的服務(wù)質(zhì)量用對(duì)應(yīng)計(jì)算資源單元的服務(wù)質(zhì)量來表征。