1.一种众包平台的协作式任务分配方法,其特征在于,包括以下步骤:
S10、任务请求端发出请求指令:任务请求端过滤众包平台发布的众包任务并发送需要完成的所述众包任务指令给归属地的承接端;
S20、任务承接端接收任务请求指令并作出判断:任务承接端接收众包平台的所述众包任务指令并判断能否执行所述众包任务指令,若能,则执行S30,若不能,则执行S40;
S30、任务承接端执行所述众包任务指令并将答案返回给任务请求端;
S40、向其他承接端发出指令寻求协助,其他承接端接收指令并完成所述众包任务;
为了使整体协助开销最小,通过第一阶段和第二阶段进行任务分配;
所述第一阶段对任务集T进行任务分配:把任务集T中的任务全部分配一次,保证任务请求端发出的任务请求都可被完成;第二阶段通过对任务集T重复分配任务,减少协助开销;提出了基于强度的贪心算法和基于开销的贪心算法来解决任务分配问题,以达到整体协助开销最小的目的;
基于强度的贪心算法:
首先,将任务集T中的任务都分配一次:每次把T中强度最大的任务分配给剩余工作强度最大的承接端,直到T中的任务都被分配完毕;接下来挑选任务进行重复分配:遍历其他承接端,把每个任务承接端si收到任务强度最大的任务tl分配给他;重复以上操作,直到承接端没有剩余工作强度能承接任一任务时停止;
基于开销的贪心算法:
从任务分配给承接端后产生协助开销大小的角度出发,首先将T中的任务分配一次:计算T中每个任务分配给承接端后产生协助开销的大小,按照由小到大的顺序将任务分配出去,直到T中的任务都被分配完毕;接下来挑选任务进行重复分配:在为第二阶段留有足够的剩余工作强度条件下,按照剩余工作强度由大到小的顺序挑选承接端,计算T中的任务分配给承接端后,任务产生协助开销的大小,按照开销由小到大的顺序进行分配;重复以上操作,直到承接端没有剩余工作强度能承接任一任务时停止;
S50、重复步骤S10至S40。
2.根据权利要求1所述的一种众包平台的协作式任务分配方法,其特征在于,所述S10中令tl为众包平台发布的众包任务,每个众包任务tl有任务强度al,其中tM为具有最大强度aM的最大众包任务,那么T={t1,t2,…,tn}为众包平台发布的众包任务集合,n为众包任务的总数量,令a为众包平台发布的众包任务的总强度:a=∑1≤l≤nal。
3.根据权利要求2所述的一种众包平台的协作式任务分配方法,其特征在于,所述S10中令si为任务承接端,每个任务承接端si有工作强度bi,其中sM为具有最大工作强度bM的最大任务承接端,那么S={s1,s2,…,sm}为众包平台中的所有任务承接端集合,m为任务承接端的总数量,任务承接端si承接的任务集标记为T(si),能完成任务tl的承接端集合为S(tl)={si|tl∈T(si)}。
4.根据权利要求3所述的一种众包平台的协作式任务分配方法,其特征在于,所述S40中当任务承接端si无法完成众包任务tl时,向能完成此任务的其他承接端sj请求协助,此时,产生协助开销cji·al,其中cji为其他承接端sj传输答案给任务承接端si的单位开销。
5.根据权利要求4所述的一种众包平台的协作式任务分配方法,其特征在于,为了减少协助开销cji·al,任务承接端si会选择能完成众包任务tl并且开销最小的其他承接端sj来完成众包任务,最小协助开销为 那么任务承接端si所产生的协助开销为众包平台的整体协助开销就是所有承接端所产生的协助开销总和,因此众包平台协助开销定义为:
6.根据权利要求1所述的一种众包平台的协作式任务分配方法,其特征在于,任务承接端出现动态问题时采用基于强度的动态承接端算法或基于开销的动态承接端算法。