# Approximation algorithms for two-machine flow shop scheduling with batch setup times

Chen, Bo, Potts, Chris N. and Strusevich, Vitaly A.
(1998)
*Approximation algorithms for two-machine flow shop scheduling with batch setup times.*
Mathematical Programming, 82 (1-2).
pp. 255-271.
ISSN 0025-5610 (Print), 1436-4646 (Online)
(doi:10.1007/BF01585875)

## Abstract

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

Item Type: | Article |
---|---|

Additional Information: | [1] This is the official journal of the Mathematical Optimization Society - now published by Springer-Verlag. |

Uncontrolled Keywords: | scheduling, flow shop, batch setup times, approximation algorithm, performance analysis |

Subjects: | Q Science > QA Mathematics |

Pre-2014 Departments: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |

Last Modified: | 14 Oct 2016 08:59 |

URI: | http://gala.gre.ac.uk/id/eprint/102 |

### Actions (login required)

View Item |