Compact Scheduling for Task Graph Oriented Mobile Crowdsourcing
Compact Scheduling for Task Graph Oriented Mobile Crowdsourcing
复制标题
面向任务图的移动众包的紧凑调度
DOI：
10.1109/tmc.2020.3040007
复制
发表时间：
2020
影响因子：
7.9
通讯作者：
Zhang, Daqing
中科院分区：
文献类型：
--
作者：
Wang, Liang;Yu, Zhiwen;Han, Qi;Yang, Dingqi;Pan, Shirui;Yao, Yuan;Zhang, Daqing
随着越来越强大的移动的设备和无线网络的扩散，移动的众包已经作为一种新颖的服务范例出现。它使人群工作者能够接管外包的位置依赖性任务，并引起了研究界和行业的广泛关注。在本文中，我们考虑一个移动的众包场景，其中一个移动的众包任务太复杂（例如，地震后恢复、全市范围内的包裹递送），但可以分为许多更容易的子任务，这些子任务之间具有相互依赖性。在这种情况下，我们研究了一个重要的问题，namelytask graph scheduling in移动的crowdsourcing（TGS-MC），它试图优化一个紧凑的调度，使得任务完成时间（即，在考虑工人可靠性的情况下，同时最小化最大完工时间）和总空闲时间。分析了TGS-MC问题的复杂性和NP完全性，分别从局部优化和全局优化的角度提出了两种启发式算法，包括基于BFS的动态优先级排序BFSPriD算法和基于进化多任务的EMTTSCH算法.我们使用两个真实世界的数据集进行了广泛的评估，并证明了我们提出的方法的优越性。
With the proliferation of increasingly powerful mobile devices and wireless networks, mobile crowdsourcing has emerged as a novel service paradigm. It enables crowd workers to take over outsourced location-dependent tasks, and has attracted much attention from both research communities and industries. In this paper, we consider a mobile crowdsourcing scenario, where a mobile crowdsourcing task is too complex (e.g., post-earthquake recovery, citywide package delivery) but can be divided into a number of easier subtasks, which have interdependency between them. Under this scenario, we investigate an important problem, namelytask graph scheduling in mobile crowdsourcing(TGS-MC), which seeks to optimize a compact scheduling, such that the task completion time (i.e., makespan) and overall idle time are simultaneously minimized with the consideration of worker reliability. We analyze the complexity and NP-complete of the TGS-MC problem, and propose two heuristic approaches, including BFS-based dynamic priority schedulingBFSPriDalgorithm, and an evolutionary multitasking-basedEMTTSchalgorithm, to solve our problem from local and global optimization perspective, respectively. We conduct extensive evaluation using two real-world data sets, and demonstrate superiority of our proposed approaches.