改进的粒子群算法求解置换流水车间调度问题

摘要

针对置换流水车间调度问题,提出了一种改进的粒子群算法进行求解.改进算法引入了判断粒子群早熟的方法,并在发现粒子群早熟后采用逆转策略对种群最优粒子进行变异,利用模拟退火思想概率接收新的最优粒子.种群最优粒子的改变会引导粒子群跳出局部极值的约束,从而克服粒子群的早熟状态.通过对置换流水车间调度问题中Car系列和Rec系列部分基准数据的测试,证明了该算法的有效性.%To solve permutation flowshop scheduling problem, an improved particle swarm optimization was proposed. Improved algorithm introduced a method to judge the premature state of the particle swarm, and used reversion strategy to mutate the best particle after the particle swarm being trapped in premature convergence, and used simulated annealing method to accept the new particle. The mutation for best particle can guide the particle swarm to escape from the local best value's limit and overcome the particles' premature stagnation. The simulation results based on Car and Rec benchmarks of permutation flowshop scheduling problem prove the effectiveness of the proposed algorithm.