论文研究 作业车间调度转换瓶颈算法可行性研究.pdf

讨论了转换瓶颈( SB) 算法在解作业车间调度问题时需要解决的子问题。转换瓶颈算法是解决作业车间调度最小makespan( 完工时间) 问题的有效启发式算法。它是基于反复地解决某些单机调度问题这样的子问题。然而所解决的单机调度问题的解可能会导致算法最终得不到可行解, 即使是单机调度最优解也可能得到不可行解。为此, 给出了一个简单的反例证明了产生不可行解的情况, 并对产生不可行解的原因作了详细分析。该研究有利于对转换瓶颈技术进行更好的理解和应用。