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

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

Note on infeasibility problemof shifting bottleneck procedure for job shop scheduling

This paper discussed the subproblemin job shop scheduling problemsolved by shifting bottleneck procedure. Shifting bottleneck ( SB) algorithmwas a prominent algorithm for the minimum makespan problem of job shop scheduling. It was based on solving a series of one-machine scheduling problem. However the solution to the one-machine problemmight result in the infeasible solution for the job shop scheduling problem. Even the solution was optimal, infeasibility could still be reached. This paper gave a simple counterexample to illustrate the infeasible case. It analyzed the reason of the infeasibility in details. The research is helpful in understanding and utilizing the shifting bottleneck technique.