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

摘要：

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

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

所属期刊栏目：41

分类号：TP301(计算技术、计算机技术)

资助基金：国家重点基础研究发展计划973计划G1998030600

在线出版日期：2005-04-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：53-55,59