极小化总完工时间批调度问题的两种蚁群算法

摘要：

针对考虑工件尺寸不同,求解目标为极小化总完工时间的批调度问题,考虑不同的编码方式,提出了基于工件序列的蚁群算法和基于批序列的蚁群算法.基于工件序列的蚁群算法算法采用传统的工件序列编码,需要启发式规则进行分批;基于批序列的蚁群算法算法利用蚁群算法构建性编码的特点,不需要启发式规则,而采取直接分批的方式编码,充分发挥蚁群算法自身的搜索能力.针对总完工时间的优化目标,基于批序列的蚁群算法算法引入批权重构建启发式信息;针对批调度特有性质,基于批序列的蚁群算法算法加入新的信息素更新变量,设置不同的信息素初始值,并采用局部优化技术等改进措施,以克服传统蚁群算法收敛速度慢,易陷入局部最优的缺点,通过对比实验验证了所提算法的有效性.

关键词：批调度、工件尺寸、总完工时间、蚁群算法、启发式算法

所属期刊栏目：16

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

资助基金：国家自然科学基金资助项目70671096,70821001;国家杰出青年基金B类资助项目70629002;中国科学技术大学研究生创新基金资助项目KD2008073

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

页数：共10页

页码：1255-1264