可拆分平行机排序问题的一个启发式算法
郑秋亚1
刘三阳2
杨尊袍3
1.西安电子科技大学,理学院,陕西,西安,710071;长安大学,理学院,陕西,西安,7100642.西安电子科技大学,理学院,陕西,西安,7100713.空军工程大学,理学院,陕西,西安,710051
摘要：为缩短工件的完工时间,将极小化最大完工时间的平行机排序问题作为研究目标.在此问题中,允许同一工件拆分成多个子工件在不同的机器上同时加工,同一工件的任何2个子工件不可在同一台机器上加工.与以往研究不同,对工件的拆分方式进行了限制,即工件拆分后所得子工件的长度不能小于给定的阀值,且工件拆分次数尽量少,这是一个NP难问题.借助于LPT算法的思想,提出了一个求解该问题的启发式算法,实现了工件的自动拆分和工件到机器上的自动分配.通过多个实例对文中算法进行了测试,数值结果表明:该算法可行、稳定性良好,适用于工件拆分方式具有类似限制的平行机排序问题的方案决策.
关键词：启发式算法最大完工时间排序拆分平行机
分类号：TP301(计算技术、计算机技术)
资助基金：国家自然科学基金(60574075)
论文发表日期：2010-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：5( 84-88 )
英文信息