Studies On Permutation Flow Shop Scheduling Using Genetic Algorithm Variable Neighborhood Search

Permutation flow shop scheduling problems (PFSP) is widely existed in practicalproduction process. Studies on the problems can improve the production efficiency, reducethe manufacturing costs and achieve better economic goals for the company. The PFSP is aNP-hard problem, many meta-heuristics algorithms show a good effect on solving theproblem these years.In the combination optimization problem, Genetic Algorithm (GA) is an efficientalgorithm and Variable Neighborhood Search (VNS) is an efficient local search algorithms forPFSP. In this paper, we combine the improved GA with the VNS, and then applied the hybridalgorithm to solve the PFSP and the PFSP with setup times. The explicit considerations are asfollows.To tackle the single-objective PFSP, we propose a new Hybrid Genetic Algorithm, whichcombines the improved GA with the VNS. In this algorithm, we select a part of goodindividuals from the generation and put them into the external archive. Then, we evaluate thequality of HGA on some benchmarks and obtain satisfied solutions. Comparing the solutionswith other literatures, the effectiveness of the algorithm can be proved.For the PFSP with setup times, we apply the improved GAVNS to solve thesingle-objective PFSP with setup times. Comparing the solutions with other literatures, thetest results show that the GAVNS is an efficient algorithm to the single-objective PFSP withsetup times.In the real production, multiple objectives usually need to be optimized at the same time.So we study a multi-objective PFSP with setup times. Based on the Pareto method, wepropose a Multiple Objective Hybrid Genetic Algorithm（MOHGA）with the crowdingdistance adopted. In this algorithm, we select the better non-dominated solutions of everygeneration by adopting the crowding distance and put them into the external archive. Thismethod can increase the solutions’ dispersibility. By comparing the non-dominated solutionsobtained through our algorithm with others, the effectiveness of MOHGA can be proved.Finally, we make a conclusion of this paper, and give the further research directions ofthe GAVNS algorithm and PFSP in the end of the paper.