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

Note on infeasibility problem of shifting bottleneck procedure for job shop scheduling

作　　者：黄志[1] 胡卫军[1] 

机构地区：[1]华中科技大学计算机学院,武汉430074

出　　处：《计算机应用研究》2008年第10期2932-2933,共2页Application Research of Computers

基　　金：国家"973"计划资助项目(2004CB318000)

摘　　要：讨论了转换瓶颈(SB)算法在解作业车间调度问题时需要解决的子问题。转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的有效启发式算法。它是基于反复地解决某些单机调度问题这样的子问题。然而所解决的单机调度问题的解可能会导致算法最终得不到可行解,即使是单机调度最优解也可能得到不可行解。为此,给出了一个简单的反例证明了产生不可行解的情况,并对产生不可行解的原因作了详细分析。该研究有利于对转换瓶颈技术进行更好的理解和应用。This paper discussed the subproblem in job shop scheduling problem solved by shifting bottleneck procedure. Shifting bottleneck （SB） algorithm was 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 problem might 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.

关 键 词：作业车间调度 NP-难 转换瓶颈 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]