Self-Adaptive Genetic Algorithm For Permutation Flow Shop Scheduling Problems

Abstract

The permutation flow shop scheduling problem (PFSSP) is a well-known extensively researched and heavily applied non-polynomial (NP)-Hard combinatorial optimization problem. It is encountered in various real-life manufacturing problems such as automotive manufacturing integrated circuit fabrication and agricultural food industries. It continues to gain popularity in operational research areas as new manufacturing areas are developed. Therefore finding a solution to these NP-Hard problems attract the attention of scientists. In this paper we studied a PFSSP and proposed a new heuristic for its solution: The Self-Adaptive Genetic Algorithm (GA). This proposed algorithm uses a conventional GA with cycle crossover and random swap mutation. Its novelty on the other hand lies in incorporating an adaptive mechanism in the GA. The proposed algorithm uses three different local searches (i.e. 2-Opt Greedy Insert and Greedy Swap local searches) based on their successes. In other words the proposed algorithm evaluates the performance of each local search at each generational iteration and makes a decision on which one to use based on their previous performances. The more successful local searches increase their probability of selection and vice versa. This way Self-Adaptive GA hence the name adapts and directs its exploitation by the information it obtains in its previous generations. The proposed algorithm was applied to a subset of well-known Taillard problem instances. The experimental studies show its successful performance. Self-Adaptive GA obtained the optimum results for 7 out of 18 benchmark instances. In the rest of the 11 instances the differences between the results of the proposed method and the optimum values are less than 2%. © 2023 Elsevier B.V. All rights reserved.