Enhanced PSO Based on Population Initialization and Exploration for the Permutation Flow Shop Scheduling Problem

Abstract

In this paper, a hybrid PSO (NLPSO*) is adapted to improve the obtained local optimal solution for the Permutation Flow Shop Scheduling Problem (PFSP) with minimizing the makespan. In this method, an improved NEH heuristic called -NEH+ is used to generate a good initial population. Then the PSO is triggered, followed by Iterated Local Search (ILS) to increase the coverage of exploration and exploitation search in the solution space. Both of the -NEH+ and ILS  are simple and efficient algorithms.  A computational study is performed to show the efficiency of the proposed technique. Several of well-known PFSP instances of small, medium, and large sizes were used in this study. The experimental study shows that the NLPSO* algorithm is significantly efficient in reaching better local optimal solutions.