Article ID: | iaor2000170 |
Country: | Netherlands |
Volume: | 82 |
Issue: | 1/2 |
Start Page Number: | 255 |
End Page Number: | 271 |
Publication Date: | Jun 1998 |
Journal: | Mathematical Programming |
Authors: | Potts Chris N., Chen Bo, Strusevich Vitaly A. |
Keywords: | programming: mathematical |
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(