Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (1): 6-12.DOI: 10.11772/j.issn.1001-9081.2017071886

Previous Articles     Next Articles

Multi-type task assignment and scheduling oriented to spatial crowdsourcing

MAO Yingchi1, MU Chao1, BAO Wei1, LI Xiaofang2   

  1. 1. College of Computer and Information, Hohai University, Nanjing Jiangsu 211100, China;
    2. College of Computer and Information Engineering, Changzhou Institute of Technology, Changzhou Jiangsu 213032, China
  • Received:2017-08-04 Revised:2017-08-21 Online:2018-01-10 Published:2018-01-22
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (U1301252), the National Key Technology R&D Program (2013BAB06B04), the National Key R&D Program of China (2016YFC0400910), the National Science and Technology Major Project (2017ZX07104-001), the Fundamental Research Funds for the Central Universities (2015B22214).

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

毛莺池1, 穆超1, 包威1, 李晓芳2   

  1. 1. 河海大学 计算机与信息学院, 南京 211100;
    2. 常州工学院 计算机信息工程学院, 江苏 常州 213032
  • 通讯作者: 穆超
  • 作者简介:毛莺池(1976-),女,上海人,副教授,博士,CCF会员,主要研究方向:分布式计算、并行处理、分布式数据管理;穆超(1993-)男,内蒙古赤峰人,硕士研究生,主要研究方向:分布式计算;包威(1990-),男,江苏淮安人,硕士研究生,主要研究方向:分布式计算;李晓芳(1972-),女,内蒙古赤峰人,副教授,博士,主要研究方向:分布式计算。
  • 基金资助:
    国家自然科学基金资助项目(U1301252);国家科技支撑计划项目(2013BAB06B04);国家重点研发计划项目(2016YFC0400910);国家科技重大专项(2017ZX07104-001);中央高校基本科研业务费专项(2015B22214)。

Abstract: 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 ε based Assignment (ε-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.

Key words: spatial crowdsourcing, task assignment, task scheduling, branch and bound, local optimization

摘要: 针对空间众包多类型任务完成的质量与数量问题,提出多类型任务的分配与调度方法。首先,在任务分配过程中,结合空间众包中多类型任务和用户的特点,对贪婪分配算法改进,提出基于距离ε值分配(ε-DA)算法;然后,将任务分配给附近的用户,以提高任务完成质量;其次,利用分支定界思想(BBS),根据专业匹配分数的大小,对任务序列进行调度;最后,找到最佳的任务序列。针对分支定界思想的调度算法运行速度较慢的问题,提出最有前途分支启发式(MPBH)算法。通过MPBH算法,使得在每次任务分配过程中实现局部最优化,与分支定界思想的调度算法相比,在运行速度上提高了30%。实验结果表明,所提方法能够提高任务完成的质量以及数量,有效地提高了运行速度与精确性。

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

CLC Number: