

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。