论 文：J. Jiang,B. An,Y. Jiang,P. Shi,Z. Bu, and J. Cao.\"大众Batch Allocation for Tasks with Overlaping Skill Requirements in Crowdsourcing.\"大众 IEEE Transactions on Parallel and Distributed Systems, DOI 10.1109/TPDS.2019.2894146.https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8620370
择要现有的零售风办法的分配方法紧张有以下两种问题：一是每个任务都被从头开始独立实行，二是每个事情者只同时实行一小部分任务，事情技能和韶光都没有充分利用。现实天下中有些任务有相似的技能哀求和较长的任务截止韶光，基于此本文提出一种有重叠技能哀求的任务分配方法。任务要求者由于任务的批量分配和实行花费更少报偿，事情者由于同时实行多个任务得到更多收入。批量分配的优化是NP难问题，这里有分层的和基于核心批量分配两种启示式方法，前者打算开销较大，后者由于从批量任务中选取核心任务而使繁芜度降落，显著降落打算本钱。与零售式分配法在理论剖析和Upwork数据集上的实验比拟表明，本文方法在任务要求者所付报偿、事情者所获均匀收入、任务成功完成的概率及更少的任务分配韶光几个方面性能更优。
关键词: 任务分配、众包、批量形成、折扣、技能交叠
以前众包的任务分配有两种类型：都是原子打算操作的大略任务和有很多打算操作的繁芜任务，前者直接分给个人，后者不是被分成小的子任务便是直接被分给一个团队。现行的任务分配与市场的零售业类似，都是单独分配。如主流的众包网站upwork同时会发布有很多研发B2C和O2O网站的任务，由于这个中有些根本的任务一样或相似，以是像这样的方法效率不高。这样两个任务分给同一个人的话，由于两个相似网站可以一起开拓，开拓一个网站的履历可用于另一个，故研发本钱会显著降落。零售式分配法不能降落同时进行的任务的大规模，由于每个任务从零开始独立分配，还涉及任务和事情者之间重复性的最优匹配。总体来说有两个问题：一是任务要求者要全款支付实行者的任务。由于很多任务的相似性，整合技能交叠的任务后进行批量分配可以节省很多分配用度，批量相似任务的实行人也能将复用部分实行结果，这样降落实行本钱就能给任务要求者给出的实际报偿打折。二是零售是任务分配可能没有使实行者大施才能，很多人实在一次可以胜任多个任务，这样的话每个任务的报偿又打折了，每个实行者由于同时实行多个任务而时薪又变高了，两全其美。
为办理此问题本文提出一种有交叠技能哀求的任务批量分配法，启示于降落本钱的批发业。先是根据技能哀求批量化相似任务，然后批量分给事情者。此方法有两个好处：一是节约分配韶光，二是中报系统为任务要求者所付报偿打折，三是事情者时薪变高。实行者全能胜任批量任务还好，否则的话他们会乞助于网络社区互助完成，而不会让任务要求者帮忙。由于任务要求者本身不知道哪些人可以有效完成任务。另一方面说来，事情者如果自己不会做某项任务也不乞助他们，他的名声就会变坏。
办理这批量分配优化这一NP难问题的两种启示式方法，一是分层法，它用层次模式形成所有可能的批量，然后根据批量和现有事情者的情形批量分配。该方法性能尚可不过打算本钱很大，由于要形成所有的可能批量。二是基于核心的方法，它从打算本钱较低的次优化批量中选取核心任务。和零售式方法关于理论剖析和基于Upwork网站上真实数据的实验比拟表明，本文提出的方法在任务要求者所付报偿、事情者所获均匀收入、任务成功完成的概率及更少的任务分配韶光方面，都有更好的性能。
下文第二节先容干系事情，第三节先容实验动机和问题描述，第四节先容分层批量形成的方法与任务分配，第五节先容基于核心的批量形成的方法与任务分配，第六节给出实验结果，第七节总结全文。
2 干系事情零售式分配对众包中繁芜任务有分解和单一整体分配两种办法。分解是指把任务分成大略的子任务流后再将子任务发给个人，紧张用于面向小人物市场的众包系统和事情者非专业，只能完成大略的小任务的场景。Tran-Thanh等提出一种细化要被分到事情流每阶段并为每个小任务动态分配预算的小任务数量的众包算法，研究多个繁芜事情流，并提出决定相互依赖的小任务数和每个事情流中每个任务搪塞的价格。Bernstein等提出校正和编辑文档的笔墨处理接口，将繁芜任务分成查找、修订和证明三阶段，新实行者给修订阶段最好的答案投票以掌握质量。比拟之下，本文对相似任务的批量化整合不能像分解法一样降落打算本钱和实际报偿。
单一整体分配将繁芜任务直接分给个人或团队。面向单个个体的分配指现在一些如upwork的众包网根据任务和事情者简技能的匹配程度以及事情者的名声或技能给专业事情者分配繁芜任务，这种分配一样平常非冗余，有些任务申请者还会通过即时通讯软件口试候选者决定其是否能完成任务。很多事情者处于社会网络中，Bozzon等提出一种在社会网络中探求可实行任务的最有学问的人。假如自己不会完成及UI将繁芜任务转交给另一个人，Heidari and Kearns研究设计了一种从一个人到另一个人的高效的转交构造。比拟之下，本文的方法分配全体的繁芜任务给个人，也整合了一些相似的繁芜任务，比先前的研究更能降落任务报偿，也更能充分利用事情者韶光。
关于单一整体分配中面向团队形成的分配，团队中不同技能的人互助完成繁芜任务，Liu等提出一种众包中生涉及经济勉励与担保任务要求者和实行者双方利益的有效的团队形成方法，经济机制下形成一个可完成任务并决定每个个体收入的团队。目前团队形成有一些自组织方法，如Rokicki等用自组织策略提出一种团队形成方法，个中事情者决定团队的形成，开始形成一个仅一人的团队且此人为管理者，事情者可自选想加入的团队；Lykourentzou等提出的方法中则是被雇佣的事情者可自选队友。总结来说每个团队是为一个特界说务而人为选出的，不适宜批量任务，而本文关注整合任务而非给事情者分组。
3 动机与问题描述如upwork和freelancer这样主流的面向繁芜任务的众包网站中有几百上千个事情者、几千个任务，概括有下面几个特点: 其一，不同任务的交叠技能哀求(如upwork中繁芜任务的范例种类是web移动开拓)，研究显示以上两个网站每个任务都均匀需一种以上的技能，且众包任务存在技能哀求的交叠。其二，任务间所需技能存在相似性，故同种类繁芜任务的技能需求可能相似。其三，事情者同时承担的任务数，通过打算每个事情者承担的任务数、实行任务所占韶光可知大多数人只实行很少数量的任务。其四，这些任务截止日期一样平常都很长，韶光短的也不会放在事情者技能水平也不靠谱的众包网上。大批量分组的大略小任务由于不用事情者选任务而很受欢迎，其上风一是批量任务的总体实行成本相比于每个任务独立发给不同事情者来说降落了，二是整批任务分配的韶光比较于零售式没有冗余的独立发送单个任务来说减少了。
事情者处理批量多任务可能会延期，故其报偿会打折；另一方面批量分配可减小任务的实际实行开销且可提高事情者收入，故事情者乐意接管这种开销。同一个人批量分配的任务越多，众包系统给报偿打折的力度越大且事情者时薪也越高。但分配给同一人的任务太多会引起事情者及其互助者的技能哀求不达标、报偿折扣力度大到无法知足事情者预期以及任务完成韶光超过截止日期等问题。优化目标是在每个任务的报偿不低于事情者预期、完成韶光不超过截止韶光的限定下，形成得当的批量最大化众包代价，减少任务要求者所付实际报偿。可证优化的批量任务分配是NP难问题，减少总的实际报偿和提高个体事情者收入并不冲突。使批量变大可减少实际报偿，事情者也可从较大批量中得到更高收入。因此在知足上述两个限定的情形下要增大批量，由于单人从大批量所得报偿被证明大于小批量所得；但批量增大的同时，边际收益(即加入与不加入另一个任务集的报偿差)被证明也会减少。为办理这个批量分配的NP难问题，本文提出分层和基于核心任务的两种启示式方法。前者报偿减少但打算量很高，后者的批量基于最小技能差异的核心任务，其批量结果只管不是最优，但显著降落了批量形成与分配的打算开销。
4 技能先容1）分层批量形成与任务分配
该方法利用自底向上的模式一步步迭代形成批量，初始化批量后一层的结果传给上一层，层级越高批量越大。在底层知足截止韶光和薪水限定的事情者被加入批量的候选者凑集，然后通过给较低层的每个批量加任务来迭代天生所有可能的批量，没有知足批量的截止韶光和薪水限定的事情者就去掉该层的批量。第i层每个批量有i个任务，任务以截止韶光排序。该算法繁芜度是O(2n)（n是任务数），但由于事情者可承受的批量大小被折扣机制所限定，该算法实际上是可行的，况且截止韶光和薪水的限定移除了一部分没有候选者的批量。该算法中批量越大折扣力度越大，进而担保了分层批量的形成靠近最小化实际报偿的优化目标。个中层级越大事情者越少，某批量所需报偿越多；某层没有事情者则更高层就不须要任务加入，更高层也没有事情者，提高事情者实际收入的目标就达到了。
批量任务中事情者被指派的优先级由以下四个成分：个人技能与批量任务哀求技能的覆盖度、实际报偿上事情者预期薪水的所占比（比值越低越可能让协作者实行更多任务）、事情者对批量任务的估计完成韶光、事情者的名声（紧张由履历决定，常常成功完成任务的人名声值越高）。事情者们处于社会网络中，不会实行批量任务的时候他们会乞助他们网络中的其他事情者，因此众包代价可通过考量事情者及其网络环境中其他事情者的以上四个成分来度量分派事情者批量任务的优先级。四种成分越优，优先级越高，但自己成分不优而其环境中事情者成分较优的事情者优先级也可能很高，故该方法在事情者自己能否完成任务的两种情形下均适用。
分配算法中，为达到优化目标，众包系统从高层开始选知足限定的得当的事情者，批量被指派给候选事情者凑集中的一人，分配成功就不用考虑同层或更低层的批量，避免冗余。重复该过程直到所有任务分完或所有事情者都有任务为止。为避免事情者有过多任务，假定一个事情者一次分配只承担一个批量，由于层级越高批量越大，同层批量大小同等，这里贪心地从高到低分配批量，基于批量分层的任务分配的繁芜度是O(nm)（n是任务数，m是事情者数）。图1显示了一个批量形成和任务分配的例子。首先，根据上述批量形成的算法形成批量，没有事情者的批量则其后代（高层）批量也没有事情者，没有批量任务的候选人就让批量形成在该层停滞；然后从高层可能的分配序列中选择报偿较低的批量开始，根据分配算法分配批量。
图1 分层批量形成和任务分配的例子
2）基于核心的批量形成与任务分配
由于分层的批量形成算法的繁芜度是O(2n)，任务数n很大时打算代价过高且批量形成过程中会产生很多没用的批量，这里提出一种次优化方法显著降落打算本钱。基于核心任务的批量形成与分配方法的紧张步骤是：首先选出与其他任务的间隔和最小的核心任务；然后用它初始化批量，与该核心任务间隔最近的任务加入该批量，系统检测是否有候选事情者，没有就选间隔第二小的另一个任务，关于该核心任务的批量形成过程一贯重复直到没有与该核心任务有技能交叠的任务为止；接着以该核心任务开始的批量形成后，得当的事情者被指派该批量；末了，任务集中去掉批量所包含的所有任务，为剩下的任务重复以上步骤直到没有新的核心任务或事情者为止。该方法中任务实行顺序取决于它们与核心任务间隔的大小，间隔越小实行越早。此方法可行由于相似任务很随意马虎出结果，其算法繁芜度最坏是O(nm)，比较于分层方法显著地降落了打算本钱，后者繁芜度为O(2n)+O(nm)。该算法中，批量越大候选人凑集越小，批量所需报偿越多。该算法选更大的批量，以靠近优化目标。
5 实验实验是在真实数据与可行配置上比较本文方法与零售式任务分配的基准方法，同时将本文方法与全批量分配算法（列出所有可能的批量分配）作比较。成功地实行任务被任务所需技能被知足的概率、任务在截止韶光之前实行与否、事情者对报偿满意与否、事情者名声这四个成分所影响。现在主流的基于繁芜任务的众包网站不分解任务，直接将其不冗余地独立发给专业事情者，即零售式任务分配法。个中候选事情者的技能覆盖度、名声与预期薪水这个三个成分须要考虑。本文方法考虑到事情者社会网络环境的成分，为公正比较也将其考虑进零售式方法中，将众包代价定义为特定事情者被指派特界说务的优先级。任务被以截止韶光的增序被逐一分配，每个任务都在知足截止韶光和期望薪水的限定下贪心地找最大优先级分配给事情者。
由于对繁芜任务的线上实验代价太高，现在很多干系研究在仿照实验上被证明有效，只要其数据真实、配置可行就行。故本文利用upwork上的真实数据，参考此网站上真实众包流程的可行配置进行仿照实验。本文从upwork网上搜集事情者和任务数据，事情者历史任务均匀所得假设是自己预期的，选择个中Web移动软件开拓种类的任务。为担保实验结果一样平常性本文删除了一些极度数据，且认为每个网站任务的一样平常截止韶光是[67,127]中任意一个数，从而均匀是97.7，估计任务完成韶光是截止韶光的一半与总韶光之间的任意一个数。实验中利用随机网、自由尺度网和小天下网三种经典网络来仿照社会网络环境，并测试本文方法在不同网络构造中的普遍性。本文两种分配法与零售式分配法的性能评价指标有四：所有任务完成比例、任务要求者需付总报偿、给定时期事情者均匀时薪与任务分配韶光（算法运行韶光，用于衡量分配方法的打算效率，包括批量的形成与分配进程）。
实验结果紧张受折扣因子、衰减因子（影响作为社会间隔函数的得到技能的概率的衰减率）、社会网络构造和任务数（影响性能）这四个成分影响，本文实验测试它们在性能指标上的影响。测试任务完成率时，折扣因子对零售式法无影响；同样网络构造下三种分配方法的任务完成率相似，基于核心的方法稍优于分层法，由于分层法在分配时总贪心地找报偿更低的批量；随机网下的任务完成率优于小天下网，由于任务完成率与一个事情者到另一个有所需技能的事情者之间的间隔有关，随机网中的该间隔稍小于小天下中的；其余，自由尺度网的均匀间隔最短，故它的任务完成率最高。对付衰减因子，所有方法的任务完成率在衰减因子增大时剧烈低落，随机网的任务完成率稍高于小天下，自由尺度网由于均匀间隔最小故有最高任务完成率。
在三种网络和不同折扣因子下测试任务要求者需付总报偿、事情者均匀收入与任务分配韶光。由于衰减因子只影响任务实行价段，而以上三个指标由任务分配阶段决定，故没必要在这三个指标上测试其影响。实验表明本文两种方法比较零售式方法而言，使要求者需付总报偿更少、事情者均匀收入更高、任务分配韶光更低；分层法比基于核心的批量分配法在任务要求者需付总报偿和事情者均匀收入上表现更好，但它花费更多的韶光分配任务；随折扣因子的增加，本文两种方法的任务要求者需付总报偿和事情者均匀收入都低落，个中分层法的运行韶光稍有低落，由于折扣越大意味着任务报偿越低，分层批量分配中的候选事情者越少，从而加速算法运行；网络构造的影响不大，由于三种指标与任务分配有关，而网络构造更能影响任务实行。
测试任务数的可扩展性时，随机打算upwork最新发布的不同种类的任务数目后创造一样平常是几百，本文批量操持中任务同种类且在一天中，故实验基于几百个任务。测试三种方法在不同任务数下的性能后结果表明，任务数对任务完成率没有影响；随着任务增多，本文方法在要求者需付总报偿上上风明显，三种方法的事情者均匀收入均增加；比较零售式法而言，本文方法在算法运行韶光点上有更好的可扩展性。
与全批量分配算法比较时，本文设计了一种基于递归列举所有可能的批量分配，全分配法打算繁芜度是O(n!)，故仅适用于少量任务，但可用作比较基准。本文紧张优化目标是最小化总报偿，这里仅比较这个指标。首先随机从总任务中选出一定数量的任务，仅保留有任务所需技能的事情者；然后比较两种方法和全分配算法的性能，打算本文算法结果与全算法结果之比，结果我们方法的任务要求者需总报偿约为小任务量下全算法的1.6倍。
总结来说比拟零售式方法，本文两种方法在任务要求者需付总报偿和事情者均匀收入上性能更优，同时保持附近的任务完成率，花费较少的任务分配韶光；再者，本文方法对不同网络具有普遍性。基于核心任务的方法韶光本钱更低，产生次优化结果。只管本文方法任务要求者需付报偿是全算法的1.6倍，但后者任务数可扩展性远远不及前者，后者仅适用于小任务数。当然，由于实验基于真实数据与可行配置的仿照环境，现有结果有以下一些局限性：其一，本文假定同一个事情者在任务中可能复用，且只考虑复用本钱没有供应详细的复用模型，这种假设的局限性会导致无法办理实际系统中复用的多样性、动态性和繁芜性。而事实上不同领域的复用千差万别，如软件领域的复用受软件特点、开拓者和运用环境等成分的影响。未来将探索不同复用模型对本文批量分配方法的影响，也会用软件复用技能整合批量分配方法来探索软件领域的实际运用。其二，本文假定社会网络在任务分配和实行中可靠，比如事情者依赖他们的社会网络技能集完成被指派的任务，但社会网的不愿定性和开放性导致环境中事情者有时不太可靠。因此须要引入名声和信赖机制来应对社会网络中不可靠的事情者。
6 结论盛行的零售式任务分配法由于打算本钱大无法扩展到大量并发任务，由于每个任务被独立分配、从零开始实行。再者，很多事情者同时承担小数量的任务使得他们的技能和韶光没有得到充分利用。为办理这些弊端，本文提出以减少任务要求者需付总的实际报偿和增加每个事情者收入为目标的批量分配方法。开始本文证明了批量分配优化是NP难问题，然后提出性能更优但打算本钱更高的分层批量分配法和性能次优但打算本钱显著降落的基于核心任务的批量分配法。本文进行理论剖析和基于真实数据的广泛实验来证明提出方法的有效性和上风：通过和基准的零售式任务分配法作比较，本文方法减少任务要求者需付总的实际报偿和提高事情者实际收入的优化目标通被证明，双方成功完成任务的概率附近，而本文方法任务分配所花韶光更少。未来将紧张探索批量分配机制对事情者会动态加入或离开且他们的策略和技能也动态变革的动态众包环境的适应性，也将通过与主流众包平台互助来进行大规模真实的线上实验。
7 本文紧张贡献本文从众包任务独立实行和事情者同时实行一小部分任务而导致的效率不高、资源利用率不足的弊端出发，创新性地提出了有重叠技能哀求的任务分配方法。 本文从现实天下有相似技能哀求和较长截止韶光的任务出发，提出的方法使任务要求者由于任务的批量分配和实行花费更少报偿，事情者由于同时实行多个任务得到更多收入，得到双赢。本文的提出的分层的和基于核心任务的批量分配方法在任务要求者所付报偿。事情者所获均匀收入、任务成功完成的概率和更少的任务等几个方面都优于现在盛行的零售式分配法。致谢此文由南京大学打算机科学与技能系2018级硕士魏丽霞翻译转述。
本转述事情部分得到国家重点研发操持“信息产品及科技做事集成化众测做事平台研发与运用 (2018YFB1403400)”帮助
