改进粒子群算法在作业车间调度问题中的应用

Application of Improved Particle Swarm Optimization to Job-shop Scheduling Problem

调度问题是一类典型的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.