The Library
Approximation algorithms for two-machine flow shop scheduling with batch setup times
Tools
UNSPECIFIED (1998) Approximation algorithms for two-machine flow shop scheduling with batch setup times. MATHEMATICAL PROGRAMMING, 82 (1-2). pp. 255-271. ISSN 0025-5610.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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 irs 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 log n) 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. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software H Social Sciences > HD Industries. Land use. Labor > HD28 Management. Industrial Management Q Science > QA Mathematics |
||||
Journal or Publication Title: | MATHEMATICAL PROGRAMMING | ||||
Publisher: | ELSEVIER SCIENCE BV | ||||
ISSN: | 0025-5610 | ||||
Official Date: | 1 June 1998 | ||||
Dates: |
|
||||
Volume: | 82 | ||||
Number: | 1-2 | ||||
Number of Pages: | 17 | ||||
Page Range: | pp. 255-271 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |