作业车间调度转换瓶颈算法的不可行解问题

• 作者: 黄志 黄文奇
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 作业车间调度 NP-难 启发式 转换瓶颈
• 年，卷（期）: 2005,（5）
• 所属期刊栏目: 学术探讨
• 页码范围: 53-55,59
• 页数: 4页
• 分类号: TP301
• 字数: 4137字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2005.05.019

摘要

文章讨论了作业车间调度问题转换瓶颈算法的一个缺陷.转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的很有效的启发式算法.它是基于反复的解决某些单机调度问题.然而在转换瓶颈算法中用Carlier算法解单机调度问题并不总能得到可行解,文中给出了一个反例证明了有产生不可行解的情况.另外,文章还以简洁的方法证明了转换瓶颈算法若用Schrage算法替代Carlier算法解单机调度问题不会产生不可行解.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄文奇	华中科技大学计算机学院	88	1090	21.0	27.0
2	黄志	华中科技大学计算机学院	8	132	6.0	8.0