基于自适应蚁群算法的动态作业车间调度问题的求解方法

作者：李保1,王长华1,熊婧2 日期：2009-08-18/span> 浏览：3896 查看PDF文档

基于自适应蚁群算法的动态作业车间调度问题的求解方法

李保1,王长华1,熊婧2
(1.浙江省机电设计研究院有限公司，浙江 杭州 310003; 2.上海广电NEC液晶显示器有限公司,上海 201108)

摘要：针对目前大多数作业车间调度算法都是静态调度，而实际工业生产中调度任务都是动态变化的问题，提出了一种求解动态作业车间调度问题的自适应蚁群算法。算法采用事件驱动调度策略，当调度任务发生变化时根据上次调度结果重新调度，并且对每次调度采用自适应蚁群算法优化调度方案。最后，通过实例仿真验证了算法的有效性。仿真结果表明，该算法自适应性表现在算法针对“搜索结果是否陷入局部收敛”分别对各路径上的信息素进行了自适应调整，有助于算法快速跳出局部收敛，继续向全局最优解进行搜索。
关键词：蚁群算法；动态作业车间调度；自适应蚁群算法
中图分类号：TM383.5文献标识码：A文章编号：1001-4551(2009)07-0093-04

Solution method of dynamic Job-Shop scheduling problem based on adaptive ant colony algorithm
LI Bao1, WANG Chang-hua1, XIONG Jing2
(1. Zhejiang Institute of Mechanical & Electrical Engineering Co.,Ltd., Hangzhou 310003, China;
2. Shanghai SVA NEC Liquid Crystal Display Co., Ltd., ShangHai 201108, China)
Abstract: Aiming at most static scheduling Job-Shop problem, in reality the Job-Shop scheduling is dynamic, a solution method of dynamic Job-Shop scheduling problem based on adaptive ant colony algorithm was advanced. When scheduling assignment changed, this algorithm event-driven rescheduling strategies based on last scheduling result was used. And for each rescheduling, the adaptive ant colony algorithm was used. In the end, the simulation results show that this algorithm has good performance. This algorithm adjust pheromone based on whether algorithm get into part convergence, this can help algorithm to obtain best solution faster.
Key words: ant colony algorithm; dynamic Job-Shop scheduling; adaptive ant colony algorithm
参考文献(References):
［1］杨晓梅,曾建潮.采用多个体交叉的遗传算法求解作业车间调度问题［J］.计算机集成制造系统，2004，10(9):1114-1119.
［2］王常青，操云甫，戴国忠.用双向收敛蚁群算法解作业车间调度问题［J］.计算机集成制造系统，2004，10(7):820-824.
［3］LIN S, GOODMAN E D, PUNCH W E. A Genetic Algorithm Approach to Dynamic Job-Shop Scheduling Problems［C］.The Seventh International Conference on Genetic Algorithm, San Francisco,1997.
［4］BIERWIRTH C, MATTFELD D C. Production Scheduling and Rescheduling with Genetic Algorithms［J］.Evolutionary Computation,1999,7(1):1-17.
［5］CHURCH L, UZSOY R. Analysis of periodic and event-driven rescheduling policies in dynamic shops［J］.International Journal of Computer Integrated Manufacturing,1992,5(3):153-163.
［6］王志亮，汪惠芬，张友良.动态Job-Shop调度问题的一种自适应遗传算法［J］.中国机械工程，2004，15(11):995-999.
［7］阎志华，丁秋林.用蜂群算法实现动态作业车间调度［J］.组合机床与自动化加工技术，2004(2):47-50.
［8］NASR N, ELSAYED E A. Job shop scheduling with alternative machines［J］.International Journal of Production Research,1990,28(9):1595-1609.