Algorithm

World Wide Web

Generalized assignment problem

Statistics

Economics

Computer science

Mathematical optimization

Greedy algorithm

Assignment problem

Task (project management)

Upper and lower bounds

Mathematics

Management

Mathematical analysis

Online algorithm

Artificial intelligence

Matching (statistics)

Crowdsourcing

Competitive analysis

Optimization problem

IEEE Transactions on Services Computing

With the advent of intelligent technology, the users of spatio-temporal crowdsourcing and their participation in the crowdsourcing tasks continue to increase exponentially. This poses new challenges to the crowdsourcing field. One of the core research areas of spatio-temporal crowdsourcing is task assignment. Most of the existing research on task assignment is focused on offline optimal task assignment, where, the platform has already learned all the information about workers and tasks beforehand. However, these studies cannot obtain good results in real-world situations. At the same time, online task assignment problems often result in local optimal assignment. To solve these problems, more attention needs to be paid to online task assignments and the arrival time of workers. This paper proposes an Online Bilateral Assignment (OBA) problem based on the online assignment model. The competitive ratio of the Greedy algorithm is analyzed according to the OBA problem model. Also, another solution to the OBA problem according to the Greedy algorithm, the Improved-Baseline algorithm, is proposed. Additionally, a Bilateral Online Priority Reassignment algorithm (BOPR) is proposed. The BOPR algorithm realizes real-time task/worker assignment through the bilateral assignment as a solution for online task assignment. In order to guarantee the number of matching tasks, a priority queue is designed in the BOPR algorithm. Considering the waiting time deadlines of tasks and workers and the error rate for priority ranking, it avoids tasks and workers waiting too long and assigns each task to the best possible extent. On this basis, a two-stage assignment strategy is designed for unsuccessful tasks, which could minimize the error rate of the task and significantly improve the efficiency of task assignment. Finally, through experiments on real data sets, the algorithm's performance in terms of global utility value and the number of matches is evaluated.

Two-stage Bilateral Online Priority Assignment in Spatio-temporal Crowdsourcing