An improved memetic algorithm based on a dynamic neighbourhood for the permutation flowshop scheduling problem |
| |
Authors: | Jianyou Xu Yunqiang Yin TCE Cheng Chin-Chia Wu Shusheng Gu |
| |
Affiliation: | 1. College of Information Science and Engineering, Northeastern University, Shenyang, Chinaxujianyou@ise.neu.edu.cn;3. State Key Laboratory Breeding Base of Nuclear Resources and Environment, East China Institute of Technology, Nanchang, China;4. School of Sciences, East China Institute of Technology, Fuzhou, China;5. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Hong Kong;6. Department of Statistics, Feng Chia University, Taichung, Taiwan;7. College of Information Science and Engineering, Northeastern University, Shenyang, China |
| |
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 |
|
|