A variable neighborhood search based genetic algorithm for flexible job shop scheduling problem

Production scheduling problems are typically combinational optimization problems named bases on the processing routes of jobs on different machines. In this paper, the flexible job shop scheduling problem aimed to minimize the maximum completion times of operations or makespan is considered. To solve such an NP-hard problem, variable neighborhood search (VNS) based on genetic algorithm is proposed to enhance the search ability and to balance the intensification and diversification. VNS algorithm has shown excellent capability of local search with systematic neighborhood search structures. External library is improved to save the optimal or near optimal solutions during the iterative process, and when the objective value of the optimal solutions are the same, the scheduling Gantt charts need to be considered. To evaluate the performance of our proposed algorithm, benchmark instances in different sizes are optimized. Consequently, the computational results and comparisons illustrate that the proposed algorithm is efficiency and effectiveness.