Near-Linear Approximation Algorithms for Scheduling Problems with Batch Setup Times

Max A. Deppert, Klaus Jansen

We investigate the scheduling of $n$ jobs divided into $c$ classes on $m$ identical parallel machines. For every class there is a setup time which is required whenever a machine sw…