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

• 作者: 胡卫军 黄志
• 来源期刊: 计算机应用研究
• 关键词: 作业车间调度 NP-难 转换瓶颈
• 年，卷（期）: 2008,（10）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2932-2933
• 页数: 2页
• 分类号: TP301
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2008.10.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡卫军	华中科技大学计算机学院	15	61	5.0	7.0
2	黄志	华中科技大学计算机学院	8	132	6.0	8.0