Compact Scheduling for Task Graph Oriented Mobile Crowdsourcing
Liang Wang, Zhiwen Yu, Qi Han, Dingqi Yang, Shirui Pan, Yuan Yao, Daqing Zhang
Abstract
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, namely <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">task graph scheduling in mobile crowdsourcing</i> (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 scheduling <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">BFSPriD</i> algorithm, and an evolutionary multitasking-based <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">EMTTSch</i> algorithm, 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.