一种求解变速机调度问题的混合蚁群优化算法  

Hybrid ant colony optimization algorithm for unrelated parallel machine scheduling problem

作　　者：周泓[1] 李政道[1] 吴学静[1] 

机构地区：[1]北京航空航天大学经济管理学院,北京100083

出　　处：《计算机集成制造系统》2008年第9期1733-1741,1758,共10页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(70771003;70521001);教育部新世纪优秀人才支持计划资助项目(NCET-04-0175);北京市科委博士生论文专项资助项目(ZZ0762);北京航空航天大学博士研究生创新基金资助项目(430264)~~

摘　　要：针对一类变速机总加权拖期调度问题,提出一种混合蚁群优化算法。引入单机拖期调度问题中性能良好的修正预计完成时间的一种修改版本启发式规则,计算信息素初值,有利于算法跳出局部极值,并在局部搜索阶段,采用单亲遗传算法基因移位算子,有效优化当代最优解。通过均匀试验设计和统计分析,确定算法的关键参数组合,将算法应用于随机生成的不同规模的40个算例,并将其结果与同类文献中算法的优化结果进行对比分析。结果表明,在相同迭代次数下,混合算法优于对比算法。Aiming at the total weighted tardiness scheduling problem of unrelated parallel machine, a kind of hybrid ant colony optimization algorithm was proposed. Variation of Modified Due Date （ VMDD ） heuristic rules were in troduced for pheromone initialization to help escape from 1.ocal optimal, and Partheno-Genetic Algorithms （ PGA ） gene transfer operator was incorporated into local search to optimize the currently found best solution. Key parameters of the algorithm were defined by the uniform experimental design ＆ statistic analysis. The algorithm was applied in 40 stochastic generation problems with different scale, and results were compared. Results demonstrated that the hybrid algorithms significantly outperformed the competitor with the same iteration.

关 键 词：变速机 总加权拖期 调度 启发式规则 蚁群优化 单亲遗传算法 

分 类 号：F406.6[经济管理—产业经济]