The circular discrete particle swarm optimization algorithm for flow shop scheduling problem

摘要

A circular discrete particle swarm optimization algorithm CDPSO is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. A particle similarity and swarm activity metric are defined. In order to preserve the diversity of the swarm, an order strategy is introduced. The threshold of the particle similarity changes adaptively with the swarm evolving degree. When the swarm activity is below a specified threshold, the obtained useful information is used to make the swarm evolve circularly. Furthermore, in order to improve the performance of CDPSO algorithm further, a neighborhood structure is defined and a neighborhood search strategy is proposed and introduced into it. Finally, the CDPSO algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The result shows that the solution quality and the stability of the CDPSO both precede the other two algorithms. It can be used to solve large scale flow shop scheduling problem.