基于NSGA-III算法求解柔性作业车间调度问题

Solving Flexible Job Shop Scheduling Problem Based on NSGA-III Algorithm

针对多目标柔性作业车间调度问题,提出一种改进NSGA-Ⅲ算法,以完工时间、机器总负荷、瓶颈机器负荷为目标建立调度模型。首先,为提高种群的多样性,提出一种基于惩罚的边界相交距离定义关联操作中种群个体与参考向量之间的距离;其次,为提高环境选择的计算效率,利用基于惩罚的边界相交距离消除机制来保护个体,降低了个体保护策略的计算成本;最后,为避免种群陷入局部最优,在遗传算子中采用一种改进的变异策略。运用两个评价指标与NSGA-Ⅲ算法进行比较,其收敛性与多样性均由于NSGA-Ⅲ算法。同时在4个Kacem算例上进行测试得出改进NSGA-Ⅲ算法解的质量较高,最后通过实际的生产实例证明改进的NSGA-Ⅲ算法优于或等同于现存在的方法,也证明了该方法在解决多目标柔性作业车间调度难题上的可操作性。

An improved NSGA-III algorithm is proposed for multi-objective flexible job shop scheduling problems,with completion time,total machine load,and bottleneck machine load as the objectives to establish a scheduling model.Firstly,to improve the diversity of the population,a penalty based boundary intersection distance is considered to define the distance between the individual population and the reference vector in association operations;secondly,in order to improve the computational efficiency of environmental selection,a penalty based boundary intersection distance elimination mechanism is used to protect individuals,reducing the computational cost of individual protection strategies;compared with the NSGA-III algorithm using two evaluation indicators,its convergence and diversity are both due to the NSGA-III algorithm.At the same time,the improved NSGA-III algorithm is tested on four Kacem examples and found to have higher quality solutions.Finally,practical production examples are used to prove that the improved NSGA-III algorithm is superior to or equivalent to existing methods,and the operability of this method in solving multi-objective flexible job shop scheduling problems is also demonstrated.