Approximation algorithms for two-machine flow shop scheduling with batch setup times |
| |
Authors: | Bo Chen Chris N Potts Vitaly A Strusevich |
| |
Institution: | (1) Warwick Business School, University of Warwick, CV4 7AL Coventry, UK;(2) Faculty of Mathematical Studies, University of Southampton, S0117 1BJ Southampton, UK;(3) School of Computing and Mathematical Sciences, University of Greenwich, SE 18 6PF London, UK |
| |
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. |
| |
Keywords: | Scheduling Flow shop Batch setup times Approximation algorithm Performance analysis |
本文献已被 SpringerLink 等数据库收录! |
|