[發(fā)明專利]一種公平的眾包工作流分配方法

有效

• 申請?zhí)枺?/td>: 202010528051.7
• 申請日: 2020-06-10
• 公開（公告）號: CN111738576B
• 公開（公告）日: 2023-08-01
• 發(fā)明（設計）人: 付東來;蔡興旺
• 申請（專利權）人: 中北大學
• 主分類號: G06Q10/0631
• 分類號: G06Q10/0631
• 代理公司: 太原申立德知識產權代理事務所(特殊普通合伙) 14115
• 代理人: 張向瑩

本發(fā)明公開了一種公平的眾包工作流分配方法，包括：S1、輸入在線工人集合、眾包任務工作流和完成時間；S2、初始化分配參數(shù)，開始分配；S3、從工作流中發(fā)現(xiàn)待分配任務集合；S4、根據(jù)第一個待分配任務的要求提名工人，并根據(jù)被提名工人的相似性進行分組生成任務分配提名組；S5、按組征求工人意見，并生成對應的任務分配候選組；S6、計算組間的公平性，并選擇受到最不公平待遇的候選組；S7、從候選組中發(fā)現(xiàn)受到最不公平待遇的候選工人，并把任務分配給該工人；S8、完成所有待分配任務集合中的任務后，更新分配參數(shù)繼續(xù)尋找下一個待分配任務集合，直到工作流中的任務被全部分配。本發(fā)明在保證工作流被按時完成的前提下，確保分配的最大公平性。

技術領域

本發(fā)明涉及計算機技術領域，具體涉及一種公平的眾包工作流分配方法。

背景技術

眾包是一種分布式、以人為中心的問題解決范式，它的基本應用場景是任務被提交到一個平臺，再由平臺將任務分配給合適的人完成或者由平臺上注冊的用戶自己選擇平臺發(fā)布的任務并完成任務。因此，一個眾包系統(tǒng)通常有三種角色，提交任務的人被稱為任務請求者，平臺被稱為眾包平臺，完成任務的人被稱為工人。目前，眾包已經被廣泛應用到多個領域，包括教育、健康、災害監(jiān)測及軟件開發(fā)等多個領域。

眾包平臺上的任務，即眾包任務，通常可分為微任務、復雜任務、宏任務和創(chuàng)造性任務。本發(fā)明主要針對復雜任務。基于眾包的復雜任務解決方案通常是將一個復雜任務分解為若干微任務，并使用工作流表達微任務間的關系。

眾包的魅力在于有大量的工人資源來提供高質量、低成本的服務。公平是影響工人資源數(shù)量的重要因素之一。然而，目前以任務請求者為中心的復雜眾包任務分配方法，主要關注如何高質量地按時完成一個工作流，對分配過程中造成的不公平性缺少考慮。

因此，基于上述問題，有必要建立一種兼顧公平的眾包復雜任務分配方法。

發(fā)明內容

針對現(xiàn)有技術中的不足，本發(fā)明的目的在于提供一種既能按時完成任務請求者提交的工作流，又能兼顧分配過程中公平性的眾包工作流分配方法，以激勵更多的工人參與且高質量地完成眾包任務。

為實現(xiàn)上述目的，本發(fā)明采用了以下技術方案：

S1、任務請求者將任務工作流和完成時間提交到眾包平臺，工人在眾包平臺上提前注冊；其中，工作流用有向無環(huán)圖G＝{T，E}表示，圖G中的頂點t_i∈T表示工作流中的任務，圖G中的邊e_i，j∈E是任務t_i到t_j的一條有向邊，表示任務t_j在任務t_i執(zhí)行完后才能執(zhí)行，pred(t_i)表示任務t_i的前序任務集合，post(t_i)表示任務t_i的后繼任務集合，完成時長用符號Θ表示，眾包平臺上注冊的工人用集合W＝{w_i|i＝0，1，...，n}表示；

S2、初始化工作流中的任務和工人的分配參數(shù)，遍歷任務集合T，初始化任務t_i∈T的開始時間t_i·q₀、接收時間t_i·q₁、完成時長t_i·q₂、結束時間t_i·q₃和技能要求，所述技能要求用向量t_i·s表示；遍歷工人集合W，初始化工人w_i∈W的技能最低報酬向量w_i·r、接受的任務數(shù)w_i·n₁、分配的任務數(shù)w_i·n₂和技能向量w_i·s；