[發(fā)明專利]一種眾包系統(tǒng)中面向工人自然群組的任務(wù)分配方法

有效

• 申請?zhí)枺?/td>: 201711001998.7
• 申請日: 2017-10-24
• 公開（公告）號: CN107886221B
• 公開（公告）日: 2021-08-31
• 發(fā)明（設(shè)計）人: 蔣玖川;蔣嶷川;何展鵬;張友紅
• 申請（專利權(quán)）人: 佛山科學(xué)技術(shù)學(xué)院
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q10/10
• 代理公司: 廣州嘉權(quán)專利商標(biāo)事務(wù)所有限公司 44205
• 代理人: 王國標(biāo)

1.一種眾包系統(tǒng)中面向工人自然群組的任務(wù)分配方法，其特征在于包括以下步驟：

(1)面向工人自然群組的眾包系統(tǒng)模型建立；

(2)工人自然群組的眾包價值計算，眾包價值用于衡量該工人自然 群組被分配任務(wù)的概率；

(3)核心工人自然群組選擇和任務(wù)分配；

所述步驟(1)中的面向工人自然群組的眾包系統(tǒng)模型建立的步驟如下：

(1.1)數(shù)據(jù)輸入：一個任務(wù)t，預(yù)算為b_t，所需要的技能集合為S_t，n個工人自然群組：G＝{G_i|1≤i≤n}，對于工人自然群組G_i中的每一個工人w_ix，他的最低要求工資是γ_ix，他的技能集合是S_ix，對于工人自然群組G_i中的每兩個工人w_ix和w_iy，d_ix,iy是他們的通信耗費(fèi)；

(1.2)面向工人自然群組的眾包系統(tǒng)模型：把整個過程建模為任務(wù)分配的過程；為了完成任務(wù)t，首先需要選擇一個最適合這個任務(wù)的工人自然群組，即要綜合考慮技能、工人的最低要求工資和工人間的通信耗費(fèi)來選擇工人自然群組，然后再從這個工人自然群組中選擇一個合適的工人子集合來真正執(zhí)行這個任務(wù)；

(1.3)問題描述和約束條件：用W_Gi(t)來表示自然群組G_i中被選中真正執(zhí)行任務(wù)t的工人子集合，問題的定義如公式(A)所示，即要選擇這樣一個工人自然群組：它要滿足任務(wù)的技能要求，同時它的工人的最低要求工資和工人間的通信耗費(fèi)要盡可能得低，考慮到任務(wù)有自己的預(yù)算，所以定義約束如公式(B)所示，它的意思是所選的工人自然群組中真正執(zhí)行任務(wù)的工人子集合的最低要求工資的和不能超過要完成的任務(wù)的預(yù)算；

2.根據(jù)權(quán)利要求1所述的眾包系統(tǒng)中面向工人自然群組的任務(wù)分配方法，其特征在于：所述步驟(2)工人自然群組的眾包價值計算的步驟如下：

(2.1)群組內(nèi)工人中心程度值定義：給定一個工人自然群組G_i，對于群組內(nèi)工人w_ix，他的群組內(nèi)中心程度值定義如公式(C)所示，其中d_ix,iy是工人w_ix和w_iy的通信耗費(fèi)，|G_i|是自然群組G_i中工人的個數(shù)；

(2.2)群組中工人的初始眾包價值定義：給定一個工人自然群組G_i，一個任務(wù)t，對于群組內(nèi)工人w_ix，他相對任務(wù)t的初始眾包價值定義如公式(D)所示，其中的γ_ix是他的最低要求工資，S_ix是他的技能集合，是公式(C)計算的工人w_ix的群組內(nèi)中心程度值，b_t是任務(wù)t的預(yù)算，S_t是任務(wù)t所需的技能集合；

(2.3)群組中工人的輔助眾包價值定義：給定一個工人自然群組G_i，對于群組內(nèi)工人w_ix，他的輔助眾包價值定義如公式(E)所示，其中，γix是他的最低要求工資，S_ix是他的技能集合，d_ix,iy是工人w_ix和w_iy的通信耗費(fèi)，是當(dāng)前被選中的將來以執(zhí)行任務(wù)t的工人集合，|W_Gi(t)|是W_Gi(t)中工人的個數(shù)，S_t是任務(wù)t所需的技能集合，S′_t是任務(wù)t剩下的尚未從W_Gi(t)得到滿足的技能集合，即b_t是任務(wù)t的預(yù)算；

(2.4)根據(jù)公式(D)計算群組中每個工人的初始眾包價值，然后選擇群組內(nèi)初始眾包價值最大的工人作為組長，記為w_il，

(2.5)b＝0，S′_t＝S_t-S_il，W_Gi(t)＝{w_il}，Temp_G_i＝G_i-W_Gi(t)；

(2.6)判斷是否滿足S′_t不為空并且b為0，若滿足，執(zhí)行步驟(2.7)；若不滿足，執(zhí)行步驟(2.11)；

(2.7)對于Temp_G_i中的工人，根據(jù)公式(E)計算他們的輔助眾包價值，選擇輔助眾包價值最大的工人，記為w_i*；

(2.8)更新Temp_G_i：Temp_G_i＝Temp_G_i-{w_i*}；

(2.9)判斷是否滿足S_i*∩S′_t不為空，若滿足，S′_t＝S′_t-S_i*，W_Gi(t)＝W_Gi(t)+{w_i*}；若不滿足，b＝1；

(2.10)判斷是否滿足Temp_G_i為空，若滿足，b＝1；跳到步驟(2.6)；

(2.11)輸出工人集合W_Gi(t)；

(2.12)工人自然群組眾包價值定義：給定一個工人自然群組G_i和一個任務(wù)t，S_t是任務(wù)t的技能集合，b_t是任務(wù)t的預(yù)算，工人自然群組眾包價值定義如公式(F)所示，其中α₁、α₂和α₃是三個參數(shù)，W_Gi(t)是步驟 (2.11)輸出的工人集合，γ_ix是工人w_ix的最低要求工資，S_ix是工人w_ix的技能集合，d_ix,iy是工人w_ix和w_iy的通信耗費(fèi)；

(2.13)根據(jù)工人集合W_Gi(t)和公式(F)計算工人自然群組對于任務(wù)t的眾包價值。

3.根據(jù)權(quán)利要求1所述的眾包系統(tǒng)中面向工人自然群組的任務(wù)分配方法，其特征在于：所述步驟(3)核心工人自然群組選擇和任務(wù)分配的步驟如下：

(3.1)b＝0，n＝1，G_temp＝G；

(3.2)判斷是否滿足b＝＝0并且n＝|G|，若滿足，執(zhí)行步驟(3.3)，若不滿足，執(zhí)行步驟(3.7)；

(3.3)選出工人自然群組眾包價值最大的工人自然群組，記為G_*；

(3.4)更新G_temp：G_temp＝G_temp-G_*；

(3.5)判斷是否滿足若滿足，b＝1；

(3.6)n＝n+1，跳到步驟(3.2)；

(3.7)根據(jù)G_*輸出W_G*(t)。