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

Max A. Deppert, David Fischer, Klaus Jansen

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 div…