[發(fā)明專利]一種基于相似聚類及平均思想的動(dòng)態(tài)任務(wù)分配方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201910319148.4
• 申請(qǐng)日: 2019-04-19
• 公開（公告）號(hào): CN110070287A
• 公開（公告）日: 2019-07-30
• 發(fā)明（設(shè)計(jì)）人: 於志文;楊聰穎;劉一萌;王亮;郭斌
• 申請(qǐng)（專利權(quán)）人: 西北工業(yè)大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06;G06K9/62
• 代理公司: 西安利澤明知識(shí)產(chǎn)權(quán)代理有限公司 61222
• 代理人: 劉偉

1.一種基于相似聚類及平均思想的動(dòng)態(tài)任務(wù)分配方法，其特征在于：所述方法包括以下步驟：

S1、建立任務(wù)圖：將復(fù)雜任務(wù)分解為原子任務(wù),并通過其任務(wù)關(guān)系矩陣,建立相應(yīng)的任務(wù)圖；

S2、進(jìn)行任務(wù)相似度的刻畫，將任務(wù)圖Graph轉(zhuǎn)換為DiGraph，對(duì)相似度較高的任務(wù)添加雙向虛邊，來表示兩者除了依賴關(guān)系之外，還具有相似度關(guān)系；

S3、得到任務(wù)DiGraph之后，調(diào)用Tarjan算法，找到Graph的強(qiáng)連通分量，最終將相似并且依賴關(guān)系較強(qiáng)的強(qiáng)連通任務(wù)存儲(chǔ)到一個(gè)序列中，用于給動(dòng)態(tài)分配提供分配依據(jù)；

S4、根據(jù)Tarjan算法所產(chǎn)生的任務(wù)序列，遍歷現(xiàn)有數(shù)據(jù)庫中所匹配的任務(wù)對(duì)，讀取其相似任務(wù)所對(duì)應(yīng)參與者以及參與者未完成任務(wù)個(gè)數(shù)，然后調(diào)用平均分配思想的任務(wù)分配算法來對(duì)待分配任務(wù)進(jìn)行動(dòng)態(tài)任務(wù)分配。

2.根據(jù)權(quán)利要求1所述的一種基于相似聚類及平均思想的動(dòng)態(tài)任務(wù)分配方法，其特征在于：所述相似度包括位置相似度、需求相似度和時(shí)間相似度。

3.根據(jù)權(quán)利要求1所述的一種基于相似聚類及平均思想的動(dòng)態(tài)任務(wù)分配方法，其特征在于：所述S4中平均思想的任務(wù)分配方法，是根據(jù)參與者負(fù)載以及參與者未完成的任務(wù)個(gè)數(shù)，將待分配任務(wù)平均分配給參與者。

4.根據(jù)權(quán)利要求3所述的一種基于相似聚類及平均思想的動(dòng)態(tài)任務(wù)分配方法，其特征在于：首先找出所有參與者中手頭未完成任務(wù)數(shù)最大的參與者，然后找出每個(gè)參與者的對(duì)應(yīng)負(fù)載，最后計(jì)算所有參與者可以再執(zhí)行的任務(wù)之和，任務(wù)和即為所有參與者的負(fù)載。

5.根據(jù)權(quán)利要求4所述的一種基于相似聚類及平均思想的動(dòng)態(tài)任務(wù)分配方法，其特征在于：在總參與者負(fù)載任務(wù)數(shù)量小于等于待分配任務(wù)個(gè)數(shù)的情況下，直接進(jìn)行除法式的平均分配，未能整除的任務(wù)采用隨機(jī)分配。

6.根據(jù)權(quán)利要求4所述的一種基于相似聚類及平均思想的動(dòng)態(tài)任務(wù)分配方法，其特征在于：如果參與者負(fù)載總數(shù)大于待分配任務(wù)個(gè)數(shù)，則選擇降低標(biāo)桿max_task來實(shí)現(xiàn)任務(wù)均勻分配。