Analysis of heuristics for preemptive parallel machine scheduling with batch setup times

Analysis of heuristics for preemptive parallel machine scheduling with batch setup times

0.00 Avg rating0 Votes
Article ID: iaor19941746
Country: United States
Volume: 41
Issue: 5
Start Page Number: 981
End Page Number: 993
Publication Date: Sep 1993
Journal: Operations Research
Authors: ,
Keywords: heuristics
Abstract:

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 equ1. 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 equ2 when equ3 and of equ4 when M is a multiple of 3 and equ5. The second type of heuristic uses a procedure which resembles McNaughton's preemptive scheduling algorithm. It requires equ6 time and has a worst-case performance ratio of equ7.

Reviews

Required fields are marked *. Your email address will not be published.