流水线调度问题探究

• 作者: 程远方 蔡之华
• 来源期刊: 微机发展
• 学科: 工学
• 关键词: 流水线调度 Johnson算法 启发式算法
• 年，卷（期）: 2005,（9）
• 所属期刊栏目: 智能、算法、软件技术
• 页码范围: 29-31
• 页数: 3页
• 分类号: TP301.6
• 字数: 2797字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2005.09.011

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蔡之华	中国地质大学计算机科学与技术系	78	1452	22.0	35.0
2	程远方	中国地质大学计算机科学与技术系	2	52	1.0	2.0