APPROXIMATION ALGORITHMS FOR 2-MACHINE FLOW-SHOP SCHEDULING WITH BATCH SETUP TIMES

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-machi ne flow shop with the objective of minimizing the makespan. Jobs are g rouped into batches. A sequence independent batch setup time on each m achine is required before the first job is processed, and when a machi ne switches from processing a job in some batch to a job of another ba tch. Besides irs practical interest, this problem is a direct generali zation of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algori thm. The problem under investigation is known to be NP-hard. We propos e 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-c ase 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 Mathematica l Programming Society, Inc. Published by Elsevier Science B.V.