求解作业车间调度问题的广义粒子群优化算法

General particle swarm optimization algorithm for job-shop scheduling problem

为克服传统粒子群优化算法在解决组合优化问题上的局限性,分析了其优化机理,并在此基础上提出了广义粒子群优化模型。按照此模型提出了一种求解作业车间调度问题的广义粒子群优化算法。在本算法中,利用遗传算法中的交叉操作作为粒子间的信息交换策略,利用遗传算法中的变异操作作为粒子的随机搜索策略,而粒子的局部搜索策略则采用禁忌搜索来实现。为了控制粒子的局部搜索以及向全局最优解的收敛,迭代过程中交叉概率以及禁忌搜索的最大步长都是动态变化的。实验结果表明,本算法可有效地求解作业车间调度问题,验证了广义粒子群优化模型的合理性。

To overcome the limitations of traditional Particle Swarm Optimization （PSO） on solutions to the combinatorial optimization problems, a General PSO （GPSO） model was proposed after analyzing the optimization mechanism of the traditional PSO. Based on this model, a GPSO algorithm was presented to solve the Job-shop Scheduling Problem （JSP）. In GPSO, crossover and mutation operations in genetic algorithm were respectively utilized by particles to exchange information and search randomly. Besides, Tabu Search was used for particles＂ local search. To control the local search and ensure its convergence to the global optimum solution, time-varying crossover probability and time-varying maximum step size of Tabu Search were introduced. The experimental results showed that JSP could be solved by GPSO effectively. The feasibility of the proposed GPSO model was also demonstrated.