求解作业车间调度问题的微粒群遗传退火算法  

Particle swarm genetic annealing algorithm for job-shop scheduling

作　　者：毛帆[1] 傅鹂[1] 蔡斌[1] 

机构地区：[1]重庆大学软件工程学院,重庆400044

出　　处：《计算机工程与应用》2011年第5期227-231,共5页Computer Engineering and Applications

基　　金：重庆市科委科技计划攻关项目(No.102074920080018)

摘　　要：标准微粒群算法(PSO)通常被用于求解连续优化的问题,很少被用于离散问题的优化求解,如作业车间调度问题(JSP)。因此,针对PSO算法易早熟、收敛慢等缺点提出一种求解作业车间调度问题(JSP)的混合微粒群算法。算法将微粒群算法、遗传算法(GA)、模拟退火(SA)算法相结合,既增强了算法的局部搜索能力,降低了算法对参数的依赖,同时改善了PSO算法和GA算法易早熟的缺点。对经典JSP问题的仿真实验表明:与标准微粒群算法相比,该算法不仅能有效避免算法中的早熟问题,并且算法的全局收敛性得到了显著提高。The Standard Particle Optimization algorithm（PSO） generally is used to solve continuous optimization problems, and is used rarely to solve discrete problems such as Job-shop Scheduling Problem（JSP）.So,based on the problem of premature convergence and slow search speed of PSO,this paper proposes a hybrid particle swarm optimization algorithm to solve JSP.By combining PSO,Genetic Algorithm（GA） and Simulated Annealing（SA） algorithm,this algorithm not only enhances the global search ability,but also reduces the algorithm’s dependence on the parameters,and at the same time,overtakes the premature convergence of GA and PSO algorithm.The experimental results indicate that this algorithm not only has great advantage of convergence property over PSO,but also can avoid the premature convergence problem effectively.

关 键 词：微粒群算法 遗传算法 作业车间调度 模拟退火 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]