改进NSGA2算法求解柔性作业车间调度问题

An Improved NSGA2 Algorithm for Solving Flexible Workshop Scheduling

文章主要研究多目标柔性作业车间的调度问题,以完工时间、机器总负载、生产成本为优化目标,建立多目标柔性作业车间调度模型。针对传统的非支配排序遗传算法(non-dominated sorting genetic algorithm II,NSGA2)在求解多目标柔性作业车间调度中出现的过早收敛或局部收敛问题,提出了改进的NSGA2算法。将传统算法精英保留过程中直接选取前N个最优个体作为新一代种群改为先选取前N×α个个体,然后在次优前沿面上随机选择剩余个体,避免了种群多样性降低导致的算法陷入局部收敛,同时加入了邻域搜索,弥补了传统算法在局部搜索上的不足。通过实验仿真验证了算法的有效性。

This paper mainly studies the scheduling problem of multi-objective flexible job shop,and establishes a multi-objective flexible job shop scheduling model with the optimization objectives of completion time,total machine load and production cost.To solve the problem of premature convergence or local convergence in multi-objective flexible job shop scheduling by traditional non-dominant sorting genetic algorithm(non-dominated sorting genetic algorithm II,NSGA2),an improved NSGA2 algorithm is proposed.In the process of elite retention,the first N optimal individuals are replaced by the first N×αindividuals,and then the remaining individuals are randomly selected on the sub-optimal front surface.The algorithm caused by the decrease of population diversity is avoided to fall into local convergence.At the same time,neighborhood search is added to make up for the deficiency of traditional algorithm in local search.The effectiveness of the algorithm is verified by experimental simulation.