自适应蚁群算法在Job Shop调度问题中的研究  

Research of Self-adaptive Ant Colony Algorithm in the Job Shop Scheduling Problem

作　　者：张家兴[1,2] 夏筱筠[2] 蒋焕军[1,2] 

机构地区：[1]中国科学院研究生院,北京100049 [2]中国科学院沈阳计算技术研究所,沈阳110171

出　　处：《组合机床与自动化加工技术》2010年第9期99-103,共5页Modular Machine Tool & Automatic Manufacturing Technique

基　　金：国家科技部科技支撑计划课题(2007BAP20B01)

摘　　要：研究了Job Shop调度问题,分析了蚁群算法(ACA)与最大最小蚁群系统(MMAS)算法在解决Job Shop调度问题中的不足,提出了一种解决Job Shop调度问题的自适应蚁群算法(SACA)。此算法根据蚂蚁群体寻找路径的阶段性,使用了参数在各阶段自适应变化的策略和关键工序块邻域搜索策略,加快了蚁群算法的收敛速度,避免了早熟现象和陷入局部最优调度解,提高了蚁群算法的灵活性和鲁棒性。通过仿真实验验证了自适应蚁群算法在解决Job Shop调度问题中的性能优于蚁群算法和MMAS算法。The paper studied the Job Shop scheduling problem,analyzed the deficiencies of ant colony algorithm（ACA） and the max-min ant system（MMAS） algorithm on solving the Job Shop Scheduling Problems and proposed self-adaptive ant colony algorithm（SACA）.According to the stage of ant colony to find the path,the algorithm speeded up the convergence rate of the ant colony algorithm,avoided the premature phenomena and to fall into local optimal scheduling solution,improved the flexibility and robustness of ant colony algorithm,employing the strategy of the parameters＇ self-adaptive changes and neighborhood searching strategy of the key process block.The simulation results verify that the self-adaptive ant colony algorithm on solving the Job Shop Scheduling Problems is better than ant colony algorithm and MMAS algorithm.

关 键 词：蚁群算法 最大最小蚁群系统 自适应蚁群算法 JOB Shop调度 

分 类 号：TH16[机械工程—机械制造及自动化] TG65[金属学及工艺—金属切削加工及机床]