Two-stage hybrid flow shop scheduling with dynamic job arrivals

Motivated by applications in semiconductor manufacturing industry, we consider a two-stage hybrid flow shop where a discrete machine is followed by a batching machine. In this paper, we analyze the computational complexity of a class of two-machine problems with dynamic job arrivals. For the problems belonging to P we present polynomial algorithms. For the NP-complete problems we propose the heuristics, and then establish the upper bounds on the worst case performance ratios of the heuristics. In addition, we give the improved heuristics that can achieve better performances.