改进的转换瓶颈算法在作业车间调度中的应用

"本文主要探讨了一种改进的作业车间调度转换瓶颈算法，即Modified Shifting Bottleneck Procedure (MSBP)，用于解决最小完工时间的Job Shop Scheduling问题。作者黄志指出，Schrage算法作为单机调度的转换瓶颈算法可以确保为任何实例提供可行解。同时，他揭示了Carlier的一机排序算法在某些情况下可能得出不可行解，并指出了Carlier定理中的错误。通过修正这些错误，黄志提出了改良版的转换瓶颈算法MSB，该算法能确保为Job Shop Scheduling问题的任何实例得到可行解。实验结果显示，MSB在一组基准实例上进行了测试，显示出了良好的性能和可行性。" 在作业车间调度问题中，Job Shop Scheduling是一个典型的复杂优化问题，涉及到多个工序和多台机器的协同工作，目标是最小化所有作业的完工时间（即makespan）。本文的核心是对Shifting Bottleneck Procedure (SBP)的改进，这是一种策略性的调度方法，通过识别并优先处理瓶颈工序来优化整体流程。 原文中，作者简洁地证明了Schrage算法结合SBP可以在任何情况下产生有效的解决方案。Schrage算法是一种单机调度策略，它通过动态调整作业顺序来减少总体完成时间。然而，当使用Carlier的一机排序算法时，文章提供了一个反例，表明该组合可能无法产生可行解，这挑战了原先关于Carlier算法的普遍认知。 为了解决这个问题，黄志提出了Modified Shifting Bottleneck Procedure (MSBP)。MSBP不仅克服了SBP可能出现的不可行性弱点，而且有望获得更好的性能。通过理论证明和实证测试，MSBP被证实能够确保对Job Shop Scheduling问题的任何实例都能找到可行解。这种改进的算法对于实际生产环境中的作业调度具有重要的理论和应用价值，因为它能更有效地安排作业，减少等待时间和提高生产效率。