Approximation Bounds for SLACK on Identical Parallel Machines

We examine the problem of scheduling tasks on identical parallel machines using the SLACK heuristic. This method sorts tasks in non-increasing order of processing times, partitions them into sets of size m (corresponding to the number of machines), and subsequently schedules them in non-increasing order of slack with a list-based heuristic. Similar to LPT, SLACK has a time complexity of \(O(n \log n)\), where n denotes the number of tasks, and exhibits strong empirical performance in some scenarios. However, no formal approximation guarantee has been established for this heuristic. In this work, we provide a 4/3-approximation ratio, which, while slightly worse than with LPT, is tight. Moreover, we derive improved bounds under the constraint that processing times do not exceed a fraction of the optimal makespan. Specifically, we show that SLACK is a \(\left( 1+\frac{m-1}{m(k+1)}\right) \)-approximation algorithm when the processing time of any task is at most \(\text {OPT}/ k\) for \(k \ge 2\).