带不可用时间段的不允许等待柔性流水排序问题

Minimizing the makespan in the no-wait flexible flowshop problem with availability constraint

给出了极小化时间表长带不可用时间段限制的不允许等待柔性流水车间排序问题的模型,并对其算法复杂性进行分析．分析的结果表明,该问题在几乎所有情况下都不存在具有有限最坏比的多项式时间算法．

In this paper we study the no-wait flexible flow shop scheduling problem with availability constraint to minimize the makespan. We explore the approximability of our model and prove that the problem are almost all APX-hard, i.e, none polynomial time algorithm with a finite worst case bound can be found unless P = NP.