流水线调度问题探究

摘要：

流水线作业是现代生产线最常用的技术,流水线调度问题是具有很强工程背景的典型NP完全问题.文中介绍了特殊情况下流水线调度的有效算法:Johnson算法;对于一般情况,介绍了两种启发式算法:CDS算法和Palmer算法.对这两种启发式算法的分析表明,在时间复杂度上,CDS算法比Palmer算法复杂.但大量实验测试表明,CDS算法的结果比Palmer算法更佳.所以,当需要快速获得一个近似解的时候,可以采用Palmer算法;当对解的结果要求比较高的时候,可以采用CDS算法.

关键词：流水线调度、Johnson算法、启发式算法

所属期刊栏目：15

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

资助基金：湖北省自然科学基金2003ABA043

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

页数：共3页

页码：29-31