具有机器适用性约束的相同工件平行机近似调度算法

• 作者: 展勇 徐建安 曲东越
• 来源期刊: 中国科技论文
• 学科: 工学
• 关键词: 制造工程 平行机 相同工件 机器适用性 半匹配 近似算法
• 年，卷（期）: 2017,（22）
• 页码范围: 2575-2580
• 页数: 6页
• 分类号: TB491
• 字数: 6007字
• 语种: 中文

摘要

针对考虑机器适用性的相同工件平行机调度问题,提出1种二阶段近似调度算法.算法建立了问题的半匹配模型G=[J∪M,E,W],将原问题转化为最优半匹配搜索问题,然后通过初始解构造和优化得到问题的近似解.通过分析G=[J∪M,E,W]的拓扑统计信息对机器均载的影响,设计了初始解构造启发式规则.在此基础上,采用贪心原理,提出了基于启发式规则的初始解构造算法.初始解优化算法以初始解为起点,采用基于交错路径的局部优化方法得到近似解.通过交错路径树,搜索最优交错路径是影响初始解优化算法的重要因素.为提高搜索效率,限定交错路径的最大长度为4.最后,从理论上分析了算法的最坏情况界和时间复杂度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐建安	哈尔滨工程大学机电工程学院	24	232	9.0	14.0
2	曲东越	哈尔滨工程大学机电工程学院	8	12	3.0	3.0
3	展勇	哈尔滨工程大学机电工程学院	5	18	3.0	4.0