Improved Algorithms for Unrelated Crowd Worker Scheduling in Mobile Social Networks
This work addresses efficient task scheduling in mobile social networks, offering incremental algorithmic improvements for crowd worker management.
The paper tackles the scheduling problem for unrelated crowd workers in mobile social networks to minimize total weighted completion time, improving the approximation ratio for identical workers and introducing a randomized algorithm with a 1.45 expected ratio for unrelated workers, outperforming prior methods in experiments.
This paper addresses the scheduling problem for unrelated crowd workers in mobile social networks, where the required service time for each task varies among the assigned crowd workers. The goal is to minimize the total weighted completion time of all tasks. First, in an environment with identical crowd workers, we improve the approximation ratio of the Largest-Ratio-First (LRF) scheduling algorithm and provide an updated competitive ratio for its online version. Next, for the unrelated crowd workers environment, we introduce a randomized approximation algorithm that achieves an expected approximation ratio of 1.45. This result improves upon the 1.5-approximation ratio reported in our previous work. We also present a derandomization method for this algorithm. Furthermore, to improve computational efficiency, we propose an algorithm that leverages the property that the optimal schedule on a single crowd worker arranges tasks in non-increasing order by their Smith ratios. Experimental results demonstrate that our proposed method outperforms three variants of the LRF algorithm.