Journal of Frontiers of Computer Science and Technology ›› 2016, Vol. 10 ›› Issue (3): 433-444.DOI: 10.3778/j.issn.1673-9418.1511041

Previous Articles     Next Articles

Multi-Search Mechanism Particle Swarm Optimization Algorithm for Solving FFS Problem

ZHANG Haiyue, QIN Yongbin, XU Daoyun+   

  1. College of Computer Science and Technology, Guizhou University, Guiyang 550025, China
  • Online:2016-03-01 Published:2016-03-11

求解FFS问题的混合搜索机制粒子群算法

张海月,秦永彬,许道云+   

  1. 贵州大学 计算机科学与技术学院,贵阳 550025

Abstract: For the flexible flow shop scheduling (FFS) problem, this paper proposes a multi-search mechanism particle swarm optimization algorithm (MMPSO) in order to obtain a better optimal solution. Based on the analysis of the characteristics of flexible flow shop scheduling problem, this paper designs a particle information encoding scheme for the problem, then proposes the bottleneck machine elimination algorithm to improve the quality of initial population, while using NEH-Greedy search algorithm in the individual extremum search and SADA (simulated annealing disturb algorithm) search algorithm in all extremum search, which are both used to widen the search scope, improve the quality of feasible solutions and speed up the convergence process, in the iterative search RPA (random perturbation algorithm) operations are used to avoid plunging local optimum for all extremum. The experimental results show that the proposed algorithm can obtain a good optimal solution of this flexible flow shop scheduling problem by a faster convergence rate.

Key words: flexible flow shop, scheduling algorithm, particle swarm, simulated annealing algorithm

摘要: 针对柔性流水车间调度(flexible flow shop scheduling,FFS)问题,提出了一种混合搜索机制粒子群算法(multi-search mechanism particle swarm optimization algorithm,MMPSO),以期获得柔性流水车间调度问题的优化解。在分析柔性流水车间调度问题特点的基础上,设计了针对该问题的粒子信息编码方案,提出了瓶颈机器消除算法以提升初始种群的质量;同时在个体极值搜索中采用NEH-Greedy搜索算法,在全体极值搜索中采用SADA(simulated snnealing disturb algorithm)搜索算法以扩大搜索范围,提高可行解质量,加快收敛速度,在算法迭代搜索过程中对全体极值进行RPA(random perturbation algorithm)操作以避免算法陷入局部最优。实验结果表明,MMPSO算法能够以较快的收敛速度获得柔性流水车间调度问题的一个较好的优化解。

关键词: 柔性流水车间, 调度算法, 粒子群, 模拟退火算法