In the Parallel Task Scheduling (PTS) problem, we are tasked with scheduling $n$ jobs, each with a fixed processing time and machine requirement, to minimize the completion time of the last job. Jansen and Rau (2019) presented an algorithm for PTS that achieves an approximation ratio of $(3/2)\mathrm{OPT} + p_{\max}$. They posed the open question of whether an approximation ratio of $(4/3)\mathrm{OPT} + p_{\max}$ is achievable. In this work, we present an algorithm that achieves this with a running time of $O(n\log n)$.
The Multiple Cluster Scheduling (MCS) problem is a natural extension of PTS, where we have $N$ clusters, each with $m$ machines to schedule jobs. Jansen and Rau adapted their PTS algorithm to MCS with the following results: (1) a 2-approximation, and (2) a near-linear $9/4$ approximation if $N$ is divisible by 3. We improve the running time of their 2-approximation and generalize the $9/4$ approximation to the general case. The 2-approximation for MCS is tight, as one cannot hope for a better approximation ratio than 2 unless P=NP [Zhuk, 2006]. In addition to our theoretical results, we implement our algorithm and demonstrate its practical applicability.
Blogger's Review: The algorithms presented in this paper hold significant importance both theoretically and practically, particularly for efficiently solving parallel task and multiple cluster scheduling problems, showcasing the potential of optimization algorithms in tackling complex scheduling challenges.