变邻域遗传算法求解考虑维修时间的柔性作业车间调度问题

Flexible job shop scheduling is a combinatorial optimization problem frequently encountered in the process of workshop production. Combining with the actual situation, this paper considers the preventive maintenance time of the machine and combines it with the processing procedure to generate a scheduling scheme with the optimization goal of minimizing the makespan. This paper introduces the idea of variable neighborhood search algorithm and designs a variable neighborhood genetic algorithm which has the advantages of both genetic algorithm and variable neighborhood algorithm. Three population initialization methods are used to generate initial solutions. In the crossover operation, the similarity betweVariable Neighborhood Genetic for Flexible Job Shop Scheduling Problem Considering Maintenance Timeen individuals was considered, and the individuals with low similarity were paired as the parent of the crossover operation. A neighborhood structure based on critical path was designed, and individuals were classified according to fitness value, and then the neighborhood search range was set equal to individual level value, which made the search more effective. Finally, an example is given to prove the necessity of considering the maintenance time and the effectiveness of the proposed algorithm.