DPCS2017+33+空间众包中多类型任务的分配与调度方法研究

摘要/Abstract

摘要： 摘要: 针对空间众包多类型任务完成的质量与数量问题，提出多类型任务的分配与调度方法。针对任务分配，结合空间众包中多类型任务和用户的特点，在贪婪分配算法进行改进，提出基于距离值分配算法(Distance based Assignment, -DA)，将任务分配给附近的用户，以提高任务完成质量；然后利用分支定界思想，根据专业匹配分数的大小，对任务序列进行调度，最后找到最佳的任务序列。由于分支定界思想的调度算法运行速度较慢，提出最有前途分支启发式算法(Most Promising Branch Heuristic, MPBH)。该算法利用局部最优，使用户在截止时间前完成最多的任务。实验证明，本文提出的任务分配和调度方法，能够提高任务完成的质量以及数量，并且在运行速度和精确性方面具有优势。

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

Abstract: Abstract: In order to solve the problem of the quality and quantity of multi type tasks in te spatial crowdsourcing, a method of multiple task assignment and scheduling was proposed. For multiple types of tasks, in the phase of task assignment, according to the temporal characteristics of spatial tasks, considering the character of tasks and workers, tasks are assigned based on -DA algorithm (Distance Based Assignment, -DA). -DA algorithm assigns tasks to proper workers to improve the the quality of task completed. To further improve the quality of the tasks dispatch, adopting the idea of branch and bound, the tasks sequences are scheduled to find the best one based on the professional matching scores. Due to the low speed of the branch and bound, Most Promising Branch Heuristic, MPBH, was put forward to utilize local optimizations that allows the user to complete the most tasks before the deadline. The experimental results illustrate that the proposed tasks assignment and dispatch can improve the quality and quantity of task completion and exhibit the advantages of speed and accuracy in the spatial crowdsourcing.

Key words: Keywords: Spatial crowdsourcing, tasks assignment, tasks dispatch, branch and bound, local optimizations

毛莺池穆超包威李晓芳. DPCS2017+33+空间众包中多类型任务的分配与调度方法研究[J]. 计算机应用.

参考文献

[1] Howe J. Crowdsourcing: Why the power of the crowd is driving the future of business. Crown Business. 2009. [2] Musthag M, Ganesan D. Labor dynamics in a mobile micro-task market. In: Proc. of the 2013 ACM SIGCHI Conference on Human Factors in Computing Systems. 2013. 641-650. [3] Doan A, Franklin MJ, Kossmann D, Kraska T. Crowdsourcing applications and platforms: a data management perspective. In: Proc. of the VLDB Endowment, 2011,5(11):1495-1506. [4] Deutch D, Milo T. Mob data sourcing. In: Proc. of the 2012 ACM SIGMOD International Conference on Management of Data. 2012. 581–584. [5] Chen L, Lee D, Zhang M. Crowdsourcing in information and knowledge management. In: Proc. of the 23rd ACM International Conference on Conference on Information and Knowledge Management. 2014. [6] Chen L, Lee D, Milo T. Data-driven crowdsourcing: management, mining and applications. In: Proc. of the 31st International Conference on Data Engineering. 2015. 1527-1529. [7] 冯剑红,李国良,冯建华. 众包技术研究综述. 计算机学报, 2015, 9: 1713-1726. Feng J H, Li G L, Feng J H. Summary of the study of crowdsourcing technology. Journal of Computer Science, 2015, 9: 1713-1726. [8] Burkard RE, Dell'Amico M, Martello S. Assignment problems. Society for Industrial and Applied Mathematics, 2009. [9] Wong RC, Tao YF, Fu AW, Xiao XK. On efficient spatial matching. In: Proc. of the 33rd Int’l Conf. on Very Large Data Bases. University of Vienna: ACM Press, 2007. 579-590. [10] U LH, Yiu ML, Mouratidis K, Mamoulis N. Capacity constrained assignment in spatial databases. In: Proc. of the 27th Int’l Conf. on Management of Data. Vancouver: ACM Press, 2008. 15-28. [11] Tong YX, She JY, Ding BL, Wang LB, Chen L. Online mobile micro-task allocation in spatial crowdsourcing. In: Proc. of the 32nd Int’l Conf. on Data Engineering. 2016. 49-60. [12] Tong YX, She JY, Ding BL, Chen L, Wo TY, Xu K. Online minimum matching in real-time spatial data: experiments and analysis. In: Proc. of the VLDB Endowment, 2016,9(12): 1053-1064. [13] Ho C, Vaughan J. Online task assignment in crowdsourcing markets. In: Proc. of the 26th AAAI Conference on Artificial Intelligence. 2012. 45-51. [14] Ho C, Jabbari S, Vaughan J. Adaptive Task Assignment for Crowdsourced Classification. In: Proc. of the 30th International Conference on Machine Learning.2013. 534-542. [15] Karger D, Oh S, Shah D. Budget-optimal task allocation for reliable crowdsourcing systems. Operations Research, 2014,62(1):1-24. [16] Kazemi L, Shahabi C. Geocrowd: enabling query answering with spatial crowdsourcing. In: Proc. of the SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems. 2012. 189-198. [17] To H, Fan L, Tran L, Shahabi C. Real-time task assignment in hyperlocal spatial crowdsourcing under budget constraints. In: Proc. of the 17th Int’l Conf. on Pervasive Computing and Communications. 2016. 1-8. [18] Hung Dang, Tuan Nguyen, and Hien To. 2013. Maximum complex task assignment: Towards tasks correlation in spatial crowdsourcing. In Proceedings of International Conference on Information Integration and Web-based Applications & Services. ACM, New York, NY, 77. [19] Garey MR, Johnson DS. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. [20] Vansteenwegen P, Souffriau W, Oudheusden DV. The orienteering problem: a survey. European Journal of Operational Research, 2011, 209(1): 1-10. [21] Li Y, Yiu ML, Xu W. Oriented online route recommendation for spatial crowdsourcing task workers. In: Proc. of the 14th International Conference on Advances in Spatial and Temporal Databases. 2015. 137-156. [22] Deng D, Shahabi C, Demiryurek U. Maximizing the number of worker's self-selected tasks in spatial crowdsourcing. In: Proc. of the SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems. 2013. 314-323. [23] Deng D, Shahabi C, Zhu L. Task matching and scheduling for multiple workers in spatial crowdsourcing. In: Proc. of the SIGSPATIAL 2015 International Conference on Advances in Geographic Information Systems. 2015. 21. [24] Ipeirotis P, Provost F, Wang J. Quality Management on Amazon Mechanical Turk. In: Proc. of the ACM SIGKDD Workshop on Human Computation. 2010. 64-67. [25] Liu X, Lu M, Ooi B, Shen Y, Wu S, Zhang M. CDAS: A Crowdsourcing Data Analytics System. In: Proc. of the VLDB Endowment, 2012,5(11):1495-1506. [26] Cao CC, She JY, Tong YX, Chen L. Whom to ask? jury selection for decision making tasks on micro-blog services. In: Proc. of the VLDB Endowment, 2012,5(11):1495-1506. [27] Cao CC, Tong YX, Chen L, Jagadish H. WiseMarket: a new paradigm for managing wisdom of online social users. In: Proc. of the 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2013. 455-463. [28] Gao J, Liu X, Ooi B, Wang H, Chen G. An online cost sensitive decision-making method in crowdsourcing systems. In: Proc. of the 2013 ACM SIGMOD International Conference on Management of Data. 2013. 217-228. [29] Kazemi L, Shahabi C, Chen L. GeoTruCrowd: trustworthy query answering with spatial crowdsourcing. In: Proc. of the SIGSPATIAL 2013 International Conference on Advances in Geographic Information Systems. 2013. 304-313. [30] To H, Shahabi C, Kazemi L. A server-assigned spatial crowdsourcing framework. ACM Transactions on Spatial Algorithms and Systems, 2015,1(1):2. [31] Yelp dataset. http://www.yelp.com/dataset challenge/