A BETTER HEURISTIC FOR PREEMPTIVE PARALLEL MACHINE SCHEDULING WITH BATCH SETUP TIMES

This paper addresses the problem of scheduling N jobs on M identical parallel machines with the objective of minimizing the makespan. Jobs are divided into B batches. A sequence-independent batch setup time on a machine is incurred whenever the machine starts its processing on or switches it from a job in one batch to a job in another batch. On the basis of a heuristic for this NP-hard problem proposed by Monma and Ports, a modified heuristic that requires the same implementing time O(N + (M + B)log(M + B)) and is asymptotically optimal is presented. Furthermore, for a certain class of problems, which includes the case in which each batch contains a single job, it has the worst-case performance ratio tau M = max [GRAPHICS]