TY - JOUR
T1 - Compact scheduling for task graph oriented mobile crowdsourcing
AU - Wang, Liang
AU - Yu, Zhiwen
AU - Han, Qi
AU - Yang, Dingqi
AU - Pan, Shirui
AU - Yao, Yuan
AU - Zhang, Daqing
PY - 2020/11/24
Y1 - 2020/11/24
N2 - 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 task 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 scheduling BFSPriD algorithm, and an evolutionary multitasking-based EMTTSch 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.
AB - 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 task 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 scheduling BFSPriD algorithm, and an evolutionary multitasking-based EMTTSch 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.
KW - Crowdsourcing
KW - Directed Acyclic Graph(DAG)
KW - Job shop scheduling
KW - Makespan
KW - Mobile computing
KW - Mobile Crowdsourcing
KW - Optimization
KW - Processor scheduling
KW - Task analysis
KW - Task Schedule
KW - Toy manufacturing industry
UR - http://www.scopus.com/inward/record.url?scp=85097143366&partnerID=8YFLogxK
U2 - 10.1109/TMC.2020.3040007
DO - 10.1109/TMC.2020.3040007
M3 - Article
AN - SCOPUS:85097143366
JO - IEEE Transactions on Mobile Computing
JF - IEEE Transactions on Mobile Computing
SN - 1536-1233
ER -