摘要: 针对差异工件(工件尺寸不同)两阶段流水车间的批处理机调度问题,提出一种以最小化加工时间跨度为目标的蚁群优化算法。根据批中工件在每阶段加工时间的相似程度(标准差衡量),得到一个能够提高批中工件加工时间相似水平的启发式信息。同时,改进蚁群算法的编码方案,并引入局部优化算法来提高优化性能。仿真结果表明,与现有算法相比,该算法在工件规模较大的情况下具有较好的求解性能。
关键词:
流水车间,
批处理机,
调度,
蚁群优化算法,
组合优化,
启发式
Abstract: 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.
Key words:
flow shop,
batch processing machine,
scheduling,
Ant Colony Optimization(ACO) algorithm,
combinatorial optimization,
heuristic
中图分类号:
陈成栋, 陈华平, 朱颀, 李小林. 两阶段流水车间批调度问题的蚁群优化算法[J]. 计算机工程, 2012, 38(19): 137-141.
CHEN Cheng-Dong, CHEN Hua-Beng, SHU Ken, LI Xiao-Lin. Ant Colony Optimization Algorithm for Batch Scheduling Problem of Two-stage Flow Shop[J]. Computer Engineering, 2012, 38(19): 137-141.