Complex Task Allocation in Spatial Crowdsourcing: A Task Graph Perspective

In this paper, we study a novel spatial crowdsourcing scenario, where a complex outsourced task is divided into a group of subtasks with dependency relationships. Under this scenario, we investigate a Task Graph Assignment problem in Spatial Crowdsourcing (TGA-SC), which strives to achieve an optimal task assignment solution, with the goal of minimizing the overall makespan and idle time, simultaneously. We propose two heuristic approaches, namely random walk-based algorithm RwalkS, and layered evolutionary algorithm LayGA to tackle TGA-SC problem. Using two real-world data sets, we implement extensive experiments to show the superiority of our proposed approaches.