An improved memetic algorithm based on a dynamic neighbourhood for the permutation flowshop scheduling problem

Abstract

The permutation flowshop scheduling problem (PFSP) has been extensively studied in the scheduling literature. In this paper, we present an improved memetic algorithm (MA) to solve the PFSP to minimise the total flowtime. In the proposed MA, we develop a stochastic local search based on a dynamic neighbourhood derived from the NEH method. During the evolution process, the size of the neighbourhood is dynamically adjusted to change the search focus from exploration to exploitation. In addition, we introduce a new population generation mechanism to guarantee both the quality and diversity of the new populations. We also design a diversity index for the population to monitor the diversity of the current population. If the diversity index is less than a given threshold value, the current population will be replaced by a new one with good diversity so that the proposed MA has good ability to overcome local optima. We conduct computational experiments to test the effectiveness of the proposed algorithm. The computational results on randomly generated problem instances and benchmark problem instances show that the proposed MA is effective and superior or comparable to other algorithms in the literature.

Keywords:

• permutation flowshop scheduling
• discrete particle swarm optimisation
• self-adaptive diversity control
• makespan
• total flowtime

Acknowledgement

We are grateful to the Editor and two anonymous referees for their constructive comments on earlier versions of our paper.

Funding

This paper was supported in part by the NSC of Taiwan under grant number NSC 102-2410-H-034-035; in part by National Natural Science Foundation of China under grant number NSFC 71301022.