一类求解作业车间调度问题的动态平衡自适应蚁群算法  

Dynamic balance adaptive colony algorithm solving Job-Shop scheduling

作　　者：王艳红[1] 王文霞[1] 于洪霞[1] 陈丽[1] 

机构地区：[1]沈阳工业大学信息科学与工程学院,辽宁沈阳110870

出　　处：《计算机集成制造系统》2013年第10期2521-2527,共7页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(61100091);辽宁省重点实验室资助项目(LS2010112)~~

摘　　要：为了解决作业车间调度问题,针对蚁群算法容易陷入局部最优且搜索时间较长的缺陷,提出一种动态平衡自适应蚁群算法。提出挥发系数自适应调整策略,根据算法陷入局部最优倾向的程度动态调整挥发系数,避免算法早熟;提出搜索路径动态平衡机制,当算法收敛系数大于设定的阈值时,根据解分布的"集中度"对解的分布进行动态调整,以提高解的全局搜索能力,加快收敛速度。采用该算法分别对一些经典的Benchmark调度问题进行100次运行仿真测试,并与已有文献中4种蚁群算法在相同条件下的运行结果进行对比,结果表明,算法的收敛速度、解的质量以及解的稳定性均有明显提高。Aiming at the defect that ant colony optimization easily fell into local optimal solution and had long search time, a Dynamic Balance Adaptive Colony Algorithm （DB-ACA） was proposed to solve Job-Shop scheduling prob- lem. An adaptive adjustment strategy of volatility coefficient was introduced to overcome premature convergence, which adjust the evaporation coefficient proactively according to the tendencies of the intermediate solution towards to a local optimum. A dynamic equilibrium mechanism was also put forward to improve the global search capability and the search speed of the algorithm, which changed the distribution of the solution dynamically according to the concentration of solutions distribution when the convergence coefficient was greater than the set threshold. 100 sim- ulation tests on the classic benchmark scheduling problems were run separately, and compared with other four typi- cal algorithms from literatures. The simulation results showed that the proposed algorithm had better performance than others in the convergence speed, the solution quality and the solution stability.

关 键 词：蚁群算法 动态平衡 自适应 作业车间调度 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]