Improved Approximation Algorithms for Parallel Task Scheduling and Multiple Cluster Scheduling
2026-07-01 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study scheduling problems where multiple jobs need to be assigned to machines to finish as soon as possible. They improve on previous work by creating a faster algorithm that guarantees a closer approximation to the best possible schedule for the Parallel Task Scheduling problem. They also improve and generalize results for scheduling jobs over multiple clusters of machines, keeping the runtime efficient. Their work includes both theoretical improvements and practical testing of the algorithm. This helps better understand the limits of efficient scheduling in these scenarios.
Parallel Task SchedulingApproximation AlgorithmProcessing TimeMachine RequirementMultiple Cluster SchedulingApproximation RatioNP-hardnessAlgorithm Running TimeScheduling Theory
Authors
Bennet Edler, Klaus Jansen, Felix Ohnesorge, Lis Pirotton
Abstract
In the problem of Parallel Task Scheduling (PTS), we are asked to schedule $n$ jobs, each with a fixed processing time and machine requirement, such that the completion time of the last job is minimized. Jansen and Rau (2019) presented an algorithm for PTS that achieves an approximation ratio of $(3/2)\text{OPT} + p_{\max}$. They additionally posed the open question whether an approximation ratio of $(4/3)\text{OPT} + p_{\max}$ is possible. In this work, we present such an algorithm with a running time of $O(n\log n)$. The problem of Multiple Cluster Scheduling (MCS) is a natural extension of PTS where we are given $N$ clusters each of $m$ machines to schedule jobs. Jansen and Rau (2019) 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, since one cannot hope for an approximation ratio better than 2, unless P=NP [Zhuk, 2006]. In addition to our theoretical results, we implement our algorithm and show its practical applicability.