两阶段流水车间批调度问题的蚁群优化算法  

Ant Colony Optimization Algorithm for Batch Scheduling Problem of Two-stage Flow Shop

作　　者：陈成栋[1] 陈华平[1,2] 朱颀[1] 李小林[1] 

机构地区：[1]中国科学技术大学管理学院,合肥230026 [2]中国科学技术大学计算机科学与技术学院,合肥230027

出　　处：《计算机工程》2012年第19期137-141,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(70821001;71171184)

摘　　要：针对差异工件(工件尺寸不同)两阶段流水车间的批处理机调度问题,提出一种以最小化加工时间跨度为目标的蚁群优化算法。根据批中工件在每阶段加工时间的相似程度(标准差衡量),得到一个能够提高批中工件加工时间相似水平的启发式信息。同时,改进蚁群算法的编码方案,并引入局部优化算法来提高优化性能。仿真结果表明,与现有算法相比,该算法在工件规模较大的情况下具有较好的求解性能。This paper proposes an Ant Colony Optimization（ACO） approach to minimize the makespan in a two-stage flow shop with two batch processing machines and non-identical job sizes.Based on the similarities（measured by standard deviation） of job processing time in every stage,heuristic information is suggested to improve the level of similarities of jobs in the same batch.Simultaneously,for better performance,an improved encoding scheme of ACO and a local search algorithm are presented.Experimental results show that ACO has better effectiveness than other approaches,especially for the cases with large job number.

关 键 词：流水车间 批处理机 调度 蚁群优化算法 组合优化 启发式 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]