A Variable Neighborhood Search Enhance Genetic Algorithm for Flexible Job-Shop Scheduling Problem

The flexible job-shop scheduling problem (FJSP) is a typical mixed-integer linear programming problem, which plays an important role in operation research. A variable neighborhood search (VNS) enhance genetic algorithm (VNSeGA) is presented to minimize makespan of FJSP in this paper. In VNSeGA, genetic algorithm (GA) is used for the global exploration and VNS module for local search at the solutions obtained by GA. In order to get a better solution for GA, three strategies including encoding and decoding scheme, initialization and genetic operators are introduced in VNSeGA to improve its performance for solving FJSP. Furthermore, based on the encoding scheme, it is analyzed that the VNS module with the corresponding neighborhood structures improves the solution obtained by GA. Numerical experiments are done to evaluate and validate the performance and effectiveness of VNSeGA. The computational results show that VNSeGA is able to reach high quality solutions for the FJSP compared with GA, VNS and other several heuristic algorithms