蚁群算法在单级多时段多资源约束的生产批量问题中的应用研究

中国机械工程 ›› 2012, Vol. 23 ›› Issue (19): 2326-2331.

蚁群算法在单级多时段多资源约束的生产批量问题中的应用研究

李英俊;陈志祥

中山大学,广州,510275

出版日期:2012-10-10 发布日期:2012-10-17
基金资助:
国家自然科学基金资助项目(70972079)
National Natural Science Foundation of China（No. 70972079）

Application of an Improved Ant Colony Optimization Algorithm for Solving Single-level Multi-period Capacitated Dynamic Lot-sizing Problem

Li Yingjun;Chen Zhixiang

Sun Yat-sen University,Guangzhou,510275

Online:2012-10-10 Published:2012-10-17
Supported by:
National Natural Science Foundation of China（No. 70972079）

摘要/Abstract

摘要：

设计了一个用于求解具有多时段连续与整数混合规划问题的算法结构,并以单级多时段多资源约束的生产批量问题（CLSP）的模型为背景进行了应用研究,根据此类问题的特点设计了新颖的蚁群算法,阐明了算法的具体实现过程。通过对其他文献中的例子进行计算和结果比较,表明提出的改进蚁群算法在寻优方面比退火惩罚混合遗传算法和传统的遗传算法要好,验证了所提算法对解决此类问题的可行性和适用性。



关键词: 生产批量计划, 多资源约束, 蚁群算法, 混合整数规划

Abstract:

One algorithm structure of an ant colony optimization(ACO) for solving multi-periods continuous and mixed integer programming problem was first designed herein and then its application in the single-level multi-period capacitated dynamic lot-sizing problem(CLSP) was introduced.The algorithm was based on the model characteristics of CLSP and improvements of traditional ant colony algorithm.Compared with other algorithms of other literature,the algorithm presented herein performs better than that the traditional genetic algorithm and the hybrid of simulated annealing penalty and genetic algorithm do;it has higher ability of obtaining optimal value.The application results show the method is feasible and effective for solving this kind problem.

Key words: dynamic lot-sizing problem, multiple resource constraint, ant colony algorithm, mixed integer programming

中图分类号:

F406
TP29

李英俊, 陈志祥. 蚁群算法在单级多时段多资源约束的生产批量问题中的应用研究[J]. 中国机械工程, 2012, 23(19): 2326-2331.

LI Yang-Dun, CHEN Zhi-Xiang. Application of an Improved Ant Colony Optimization Algorithm for Solving Single-level Multi-period Capacitated Dynamic Lot-sizing Problem[J]. China Mechanical Engineering, 2012, 23(19): 2326-2331.

参考文献

[1]Dorigo M,Stutzle T. Ant Colony Optimization[M]. Boston : The MIT Press, 2004.
[2]Bahl H C, Ritzman L P, Gupta J N D. Detemining Lot--sizing and Resource Requirements Review[J]. Operational Research, 1987,35 (3) : 329-345.
[3]Florian M, Lenstra J K,Rinnooy Kan A H G. Deter- ministic Production Planning:Algorithms and Com- plexity[J]. Management Science, 1980,26:12-20.
[4]许志兴[1],丁运亮[1],熊仲宇[1],陆金桂[2].基于退火惩罚混合遗传算法求解生产批量计划问题[J].南京航空航天大学学报,2001,33(1):91-95.
[5]熊红云[1],何钺[2].多级退火遗传算法解MRPⅡ有限能力批量计划问题[J].系统工程与电子技术,2001,23(2):58-59.
[6]马佳[1],高立群[1],李丹[1],刘佳[1].求解单级多资源约束生产批量计划问题的免疫遗传算法[J].东北大学学报：自然科学版,2007,28(9):1233-1237.
[7]唐立新,祁慧.CIMS中带多资源的CLSP问题的遗传启发式算法[J].系统工程理论与实践,1997,17(4):39-44.
[8]马慧民[1],柳毅[1],叶春明[1].基于改进粒子群算法求解单级多资源约束生产批量计划问题[J].工业工程与管理,2005,10(6):66-70.
[9]任雪洁[1],叶春明[1].利用量子粒子群算法求解单级多资源约束生产批量计划问题[J].现代制造工程,2010(4):39-42.
[10]韩毅[1],唐加福[1],王立岩[1],周根贵[2].单级有资源约束的生产批量计划问题的元算法[J].东北大学学报：自然科学版,2009(8):1111-1114.
[11]Pitakaso P, Almeder C,Doerner K F,et al. A MAX --MIN Ant System for Unconstrained Multi--lev el Lot Sizing Problems[J]. Computers Opera- tions Research, 2007,34 (9): 2533-2552.
[12]Almeder C. A Hybrid Optimization Approach for Multi--level Capacitated Lot Sizing Problems[J]. European Journal of Operational Research, 2010, 200(2) : 599-606.
[13]马艳[1],黄玲[2],苏守宝[1].含再制造的受限批量问题求解的蚁群算法[J].计算机应用与软件,2011,28(2):96-99.
[14]Wolsey L A, Nembauser G L. Integer and Combi- natorial Optimization[M]. New York: John Wiley Sons Inc. , 1988.
[15]唐立新著.CIMS下生产批量计划理论及其应用[M],1999:143.