Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times

The problem of preemptively scheduling N jobs on M identical parallel machines to minimize the maximum completion time is considered. Jobs are divided into B batches and a setup time on a machine is necessary whenever there is a switch from processing a job in one batch to a job in another batch. Setup times are assumed to depend only on the batch of the job to be scheduled next. Two types of heuristics are proposed and analyzed. The first type uses list scheduling for complete batches and then splits batches between selected pairs of machines. It has a time requirement of O ( N + ( M + B ) log( M + B )). Furthermore, for a certain class of problems which includes the case that each batch contains a single job, it has a worst-case performance ratio of 3/2 − 1/(4 M − 4) when M ≤ 4 and of 5/3 − 1/ M when M is a multiple of 3 and M > 3. The second type of heuristic uses a procedure which resembles McNaughton's preemptive scheduling algorithm. It requires O ( N ) time and has a worst-case performance ratio of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$2-1/(\lfloor M/2\rfloor + 1)$\end{document} .