A Branch and Bound Algorithm for Three-Machine Flow Shop with Overlapping Waiting Time Constraints

Abstract

This paper focuses on a three-machine flow shop scheduling problem with overlapping waiting time constraints for makespan minimization. In the problem, waiting times of each job between the first two machines and between the first and third machines are constrained by two distinctive time limits, respectively. Such overlapping waiting time constraints are one of the common scheduling requirements in semiconductor manufacturing since up to 20% of whole process steps are controlled with waiting time limits for better quality. For example, wafers completed with chemical treatment on a diffusion machine must be cleaned on a cleaning machine and then should be processed on another diffusion machine. In this case, two waiting time limits are independently applied between diffusion and cleaning machines and between two diffusion machines, respectively. We first identify several dominance properties of the problem and develop a branch and bound algorithm using the properties. We use heuristic algorithms to obtain a good initial solution and derive five different lower bounds. Computational tests are performed for evaluating the performance of the algorithm.