Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times

The problem of makespan minimization in a flow shop with two-machines when the input buffer of the second machine can only host a limited number c of parts is known to be NP-hard for any c > 0 and c less than or equal to n, where n is the number of jobs. In this paper we analyze this problem in the context of batch scheduling, i.e. when identical parts must be processed consecutively. In particular we study the case in which each batch requires sequence independent setup times and removal times. We then show that, if the size of the ith batch is larger than a value b(i)(*), then the makespan minimization problem can be formulated as a special case of TSP and solved in polynomial time. The cost structure of this TSP can be reduced to the one defined for the two-machine no-wait flow shop. Hence, we give a closed form expression for b(i)(*). Then, we prove that when the same algorithm is applied to batch sizes smaller than b(i)(*), the error goes to zero as the batch sizes approach the values b*. (C) 2003 Elsevier B.V. All rights reserved.