论文部分内容阅读
本文给出了极小化时间表长带这种称为机器不可用时间限制的不允许等待柔性流水车间排序问题的模型。作为研究求解该类问题算法的基础，本文首先指出，即使是最简单的仅有一个不可用时间段的柔性流水车间排序问题也是强NP-困难的。进一步，本文分析了该类问题的可逼近性。分析的结果表明，在柔性流水车间某个加工中心的所有机器上都附加不可用时间约束后，除非P=NP，几乎所有情况下都不存在具有有限最坏比的多项式时间算法(优化问题的这种性质在部分文献中称为APX-困难性)。鉴于该问题的这种APX-困难性，本文给出一个基于分支定界法的启发式算法。