空间众包中多类型任务的分配与调度方法  

Multi-type task assignment and scheduling oriented to spatial crowdsourcing

作　　者：毛莺池[1] 穆超 包威[1] 李晓芳[2] 

机构地区：[1]河海大学计算机与信息学院,南京211100 [2]常州工学院计算机信息工程学院,江苏常州213032

出　　处：《计算机应用》2018年第1期6-12,共7页journal of Computer Applications

基　　金：国家自然科学基金资助项目(U1301252);国家科技支撑计划项目(2013BAB06B04);国家重点研发计划项目(2016YFC0400910);国家科技重大专项(2017ZX07104-001);中央高校基本科研业务费专项(2015B22214)~~

摘　　要：针对空间众包多类型任务完成的质量与数量问题,提出多类型任务的分配与调度方法。首先,在任务分配过程中,结合空间众包中多类型任务和用户的特点,对贪婪分配算法改进,提出基于距离ε值分配(ε-DA)算法;然后,将任务分配给附近的用户,以提高任务完成质量;其次,利用分支定界思想(BBS),根据专业匹配分数的大小,对任务序列进行调度;最后,找到最佳的任务序列。针对分支定界思想的调度算法运行速度较慢的问题,提出最有前途分支启发式(MPBH)算法。通过MPBH算法,使得在每次任务分配过程中实现局部最优化,与分支定界思想的调度算法相比,在运行速度上提高了30%。实验结果表明,所提方法能够提高任务完成的质量以及数量,有效地提高了运行速度与精确性。Aiming at the quality and quantity problem of multi-type task completion in spatial crowdsourcing, a method of multi-type task assignment and scheduling was proposed. Firstly, in the task assignment process, by combining with the characteristics of multi-type tasks and users in spatial crowdsourcing and improving the greedy allocation algorithm, a Distance e based Assignment （e-DA） algorithm was proposed. Then the tasks were assigned to the nearby user, in order to improve the quality of task completion. Secondly, the idea of Branch and Bound Schedule （BBS） was utilized, and the task sequences were scheduled according to the size of the professional matching scores. Finally, the best sequence of tasks was found. Due to the low running speed of the scheduling algorithm of branch and bound idea, the Most Promising Branch Heuristic （MPBH） algorithm was presented. Through the MPBH algorithm, local optimization was achieved in each task allocation process. Compared with the scheduling algorithm of branch and bound idea, the running speed of the proposed algorithm was increased by 30%. The experimental results show that the proposed method can improve the quality and quantity of task completion and raise the running speed and accuracy.

关 键 词：空间众包 任务分配 任务调度 分支定界 局部最优 

分 类 号：TP393.027[自动化与计算机技术—计算机应用技术]