An alternate two phases particle swarm optimization algorithm for flow shop scheduling problem

An alternate two phases particle swarm optimization algorithm called ATPPSO is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It includes two processes, the attractive process and the repulsive process which execute alternatively. In order to refrain from the shortcoming of premature convergence, a two point reversal crossover operator is defined and in the repulsive process each particle is made to fly towards some promising areas which can introduce some new information to guide the swarm searching process. In order to improve the algorithm speed, a fast makespan computation method based on matrix is designed. Finally, the proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the solution quality and the convergence speed of the ATPPSO algorithm both precede the other two algorithms. It can be used to solve large scale flow shop scheduling problem effectively.