Minimizing the Makespan in the 3-Machine Assembly-Type Flowshop Scheduling Problem
研究三机装配型流水车间调度问题，证明其强NP完全性，给出多项式可解情形、分支定界算法及三种启发式方法并分析误差界，适合生产调度与运筹优化研究者。
This paper considers minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. After problem formulation, we present a proof to show that the general version of this problem is strongly NP-complete. We then discuss a few polynomially solvable cases of the problem and present the solution algorithms. Next, a branch and bound solution scheme is suggested. Finally, three heuristics to find approximate solutions to the general problem are proposed and their error bounds are analyzed.