Two-stage flowshop scheduling with a common second-stage machine

This article considers minimizing the makespan in a two-stage flowshop scheduling problem with a common second-stage machine. After introducing the problem, we show that it is Nn P-hard and give two special cases which are polynomially solvable. Next, we propose a heuristic algorithm and analyze its worst-case error bound. We then develop some lower bounds. Finally, we perform some computational experiments to test the average performance of the proposed heuristic.