A Modified Binary Particle Swarm Optimization Algorithm for Permutation Flow Shop Problem

In this paper, we proposed a modified version of binary particle swarm optimization algorithm (MBPSO) to solve combinatorial optimization problems. All particles are initialized as random binary vectors, and the Smallest Position Value (SPV) rule is used to construct a mapping from binary space to the permutation space. We also propose new formula to update the particles´ velocities and positions. The algorithm is then applied to the permutation flow shop problem (PFSP). To avoid the stagnation, local search and perturbation are employed to improve the performance. Performance of the proposed algorithm is evaluated using the benchmarks of flow shop scheduling problems given by Taillard, (1993). Experimental results show that the algorithm with local search and perturbation is more effective.