An Efficient Allocation Mechanism for Crowdsourcing Tasks with Minimum Execution Time

摘要

Crowdsourcing is used to leverage external crowds to perform specialized tasks quickly and inexpensively. In the application of crowdsourcing, one task may often include many ordered steps. Based on the different requirements (e.g. workers' skills and etc.) of steps, the task requester may divide the task into many sub-tasks, and publish the subtasks in the crowdsourcing system. Moreover, service requesters usually want to finish their submitted tasks as immediately as possible. However, there has been no allocation mechanism with consideration of crowdsourcing tasks with precedence constraints and minimization of the total execution time simultaneously. To tackle this challenge, we consider the precedence constraints among tasks and design an efficient task allocation mechanism for the crowdsourcing system. In this work, we first introduce the crowdsourcing system model and formulate the task allocation problem. After proving that the studied problem is NP-hard, we propose an approximation algorithm that can minimize the total execution time of all the tasks. Then, we conduct extensive simulations to evaluate the performance of the proposed algorithm, and the simulation results show that the proposed algorithm has good approximate optimal ratios under different parameter settings.