摘要
调度问题是一类典型的NP-hard问题,传统粒子群优化算法在解决该类问题上具有一定的局限性.通过分析其优化机理,提出了改进粒子群算法,结合了粒子群优化算法的全局搜索能力和交换粒子位置的局部搜索能力,提出了新的粒子编码方法——基于粒子坐标值排列编码(PPP),发展了一种快速、易实现的新的混合启发式算法.大量实验仿真结果表明本算法可以有效求解作业车间调度问题,通过与遗传算法比较,验证了改进粒子群算法是求解Job-shop调度问题可行而高效的方法.
Traditional particle swarm optimization has some limitations in solving the typical NP-hard prohlem and Job-shop scheduling problem(JSP). This paper proposes the improved particle swarm optimization(IPSO) via the analysis of its optimization mecha- nism. In the IPSO, global search and local search are combined and a new particle coding method, particle position permutation (PPP) , is proposed to develop a fast and viable hybrid algorithm. Lots of experiments prove that the algorithm can effectively solve JSP problem, which verifies the effectiveness and efficiency of the IPSO in comparison with the genetic algorithm.
出处
《四川师范大学学报(自然科学版)》
CAS
CSCD
北大核心
2009年第1期139-142,共4页
Journal of Sichuan Normal University(Natural Science)
基金
国家自然科学基金(70671057)
教育部高等学校博士点专项科研基金(20051065002)资助项目
关键词
粒子群优化
作业车间调度
混合优化
Particle swarm optimization
Job-shop scheduling
Hybrid optimization