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

Clyde L. Monma and Chris N. Potts
Additional contact information
Clyde L. Monma: Bell Communications Research, Morristown, New Jersey
Chris N. Potts: University of Southampton, Southampton, United Kingdom

Operations Research, 1993, vol. 41, issue 5, 981-993

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 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} .

Keywords: production/scheduling: identical parallel machines; preemption; batch setup times; heuristics; worst-case analysis (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.5.981 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:5:p:981-993

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().