An exact algorithm for the batch sequencing problem in a two-machine flow shop with limited buffer

This paper deals with 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 of parts. Here we analyze the problem in the context of batch processing, i.e., when identical parts must be processed consecutively. We propose an exact branch-and-bound algorithm, in which the bounds exploit the batching nature of the problem. Extensive computational results show the effectiveness of the approach, and allow us to compare it with a previous heuristic approach. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 141–164, 1998