计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (5): 227-231.

• 工程与应用 • 上一篇    下一篇

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

毛 帆,傅 鹂,蔡 斌   

  1. 重庆大学 软件工程学院,重庆 400044
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-02-11 发布日期:2011-02-11

Particle swarm genetic annealing algorithm for job-shop scheduling

MAO Fan,FU Li,CAI Bin   

  1. School of Software Engineering,Chongqing University,Chongqing 400044,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-02-11 Published:2011-02-11

摘要: 标准微粒群算法(PSO)通常被用于求解连续优化的问题,很少被用于离散问题的优化求解,如作业车间调度问题(JSP)。因此,针对PSO算法易早熟、收敛慢等缺点提出一种求解作业车间调度问题(JSP)的混合微粒群算法。算法将微粒群算法、遗传算法(GA)、模拟退火(SA)算法相结合,既增强了算法的局部搜索能力,降低了算法对参数的依赖,同时改善了PSO算法和GA算法易早熟的缺点。对经典JSP问题的仿真实验表明:与标准微粒群算法相比,该算法不仅能有效避免算法中的早熟问题,并且算法的全局收敛性得到了显著提高。

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

Abstract: 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.

Key words: particle swarm optimization algorithm, genetic algorithm, job-shop scheduling, simulated annealing