Makespan minimization in the two-machine flowshop batch scheduling problem

In this paper we consider a practical scheduling problem commonly arising f rom batch production in a flexible manufacturing environment. Different par t-types are to be produced in a flexible manufacturing cell organized into a two-stage production line. The jobs are processed in batches on the first machine. and the completion time of a job is defined as the completion tim e of the batch containing it. When processing of all job?, in a batch is co mpleted on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch pr ocessing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batc hes so that the makespan is minimized. The problem is shown to be strongly NP-hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approxim ate solutions. We conduct computational experiments to study the effectiven ess of the proposed heuristics. (C) 2000 John Wiley & Sons, Inc.