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

有效

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

1.一種公平的眾包工作流分配方法，其特征在于：所述方法包括如下步驟：

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

S2、初始化工作流中的任務和工人的分配參數，遍歷任務集合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、接受的任務數w_i.n₁、分配的任務數w_i.n₂和技能向量w_i.s；

S3、尋找圖G的最長路徑p_l＝{start，t₁，t₂，...，t_n，end}，其中，start和end是兩個虛擬的起始頂點和結束頂點；如果t_n.q₃＞Θ或路徑長度為0則結束本次分配；

S4、根據圖G生成待分配任務集合T‘，即獲取起始頂點start的后繼頂點post(start)；

S5、對所有的t_i∈T‘，生成待分配任務的提名工人集合N；

S6、根據提名集合中工人的相似性，生成集合N的一個劃分

S7、把任務組播給N_i中的每一個工人，生成對應的候選工人集合C_i；

S8、計算每一個C_i的公平性，并從中選擇一個最不公平的候選工人集合C‘_i；

S9、從選中的最不公平的候選工人集合C‘_i中發現受到最不公平待遇的工人w’_i，把任務分配給該工人；

S10、從圖G中移除任務t_i，然后返回S5；

S11、當集合T‘中的任務全部被工人完成后，更新分配參數繼續分配圖G中剩余的任務。