用双向收敛蚁群算法解作业车间调度问题  

Bi-directional convergence ACO for job-shop scheduling

作　　者：王常青[1] 操云甫[1] 戴国忠[1] 

机构地区：[1]中国科学院软件所智能工程实验室,北京100080

出　　处：《计算机集成制造系统》2004年第7期820-824,共5页Computer Integrated Manufacturing Systems

基　　金：国家863/CIMS主题资助项目(2001AA414610;2002AA414020;2002AA111080)。~~

摘　　要：为了合理高效地调度资源,解决组合优化问题,在Job-Shop问题图形化定义的基础上,借鉴精英策略的思路,提出使用多种挥发方式的双向收敛蚁群算法,提高了算法的效率和可用性。最后,通过解决基准问题的实验,比较了双向收敛蚁群和蚁群算法的性能。实验结果表明,在不明显影响时间、空间复杂度的情况下,双向收敛蚁群算法可以加快收敛速度。To properly and efficiently schedule resources and solve the combinatorial optimization problem, an improved algorithm named Bi-directional Convergence Ant Colony Optimization (ACO) algorithm was proposed. Using the graphic definition of Job-shop problem and the elitist strategy, the Bi-directional Convergence ACO algorithm was designed to improve efficiency and usability of original ACO by different evaporated means. Finally, the Bi-directional Convergence ACO algorithm was tested on a benchmark Job-shop scheduling problem. The performance of the Bi-directional Convergence ACO was also compared with that of the original ACO. The simulation result illustrates that the bi-directional convergence ACO algorithm accelerates the convergence without affecting the temporal and spatial complexity much.

关 键 词：作业车间调度 蚁群算法 双向收敛 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]