可拆分平行机排序问题的一个启发式算法

• 作者: 刘三阳 杨尊袍 郑秋亚
• 来源期刊: 空军工程大学学报（自然科学版）
• 学科: 工学
• 关键词: 启发式算法 最大完工时间 排序 拆分 平行机
• 年，卷（期）: 2010,（4）
• 页码范围: 84-88
• 分类号: TP301
• 字数: 3225字
• 语种: 中文
• DOI: 10.3969/j.issn.1009-3516.2010.04.017

摘要

为缩短工件的完工时间,将极小化最大完工时间的平行机排序问题作为研究目标.在此问题中,允许同一工件拆分成多个子工件在不同的机器上同时加工,同一工件的任何2个子工件不可在同一台机器上加工.与以往研究不同,对工件的拆分方式进行了限制,即工件拆分后所得子工件的长度不能小于给定的阀值,且工件拆分次数尽量少,这是一个NP难问题.借助于LPT算法的思想,提出了一个求解该问题的启发式算法,实现了工件的自动拆分和工件到机器上的自动分配.通过多个实例对文中算法进行了测试,数值结果表明:该算法可行、稳定性良好,适用于工件拆分方式具有类似限制的平行机排序问题的方案决策.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘三阳	西安电子科技大学理学院	662	5562	32.0	51.0
2	郑秋亚	西安电子科技大学理学院	18	149	5.0	12.0
6	杨尊袍	空军工程大学理学院	9	59	3.0	7.0