A Knowledge-Driven Genetic Algorithm With Variable Neighborhood Search for Flexible Job Shop Scheduling Problems

The flexible job shop scheduling problem is a typical NP-hard problem, which has strong guiding significance for production scheduling in enterprises. In this paper, we propose an improved genetic algorithm based on knowledge driven and variable neighborhood search to solve the problem. On the one hand, the proposed algorithm repeatedly extracts the knowledge, which contains the information of the current best machine selection solution, from an updated elite solution set and uses it to guide the mutation of machine selection. On the other hand, a threshold on the number of iterations is set and a variable neighborhood search is employed to explore better solutions for the elite solution sets once the threshold is reached. The experimental results on benchmark test instances indicate the superiority of our proposed algorithm over those reported in recent literature.