A $(4/3+\epsilon )$-Approximation for Preemptive Scheduling with Batch Setup Times

Abstract

We consider the $\mathcal{NP}$-hard problem $\mathrm{P}|\mathrm{pmtn},\mathrm{setup}={\mathrm{s}}_{\mathrm{i}}|{\mathrm{C}}_{\max }$, the problem of scheduling $n$ jobs, which are divided into $c$ classes, on $m$ identical parallel machines while allowing preemption. For each class $i$ of the $c$ classes, we are given a setup time $s_i$ that is required to be scheduled whenever a machine switches from processing a job of one class to a job from another class. The goal is to find a schedule that minimizes the makespan. We give a $(4/3+\epsilon )$-approximate algorithm with run time in $\mathcal{O}(n^2\log (1/\epsilon ))$. For any $\epsilon <1/6$, this improves upon the previously best known approximation ratio of $3/2$ for this problem. Our main technical contributions are as follows. We first partition any instance into an "easy" and a "hard" part, such that a $4/3T$-approximation for the former is easy to compute for some given makespan $T$. We then proceed to show our main structural result, namely that there always exists a $4/3T$-approximation for any instance that has a solution with makespan $T$, where the hard part has some easy to compute properties. Finally, we obtain an algorithm that computes a $(4/3+\epsilon )$-approximation in time n $\mathcal{O}(n^2\log (1/\epsilon ))$ for general instances by computing solutions with the previously shown structural properties.