Improved NSGA-III Algorithm for Solving Flexible Job Shop Scheduling Problem

Abstract

To address the high dimensionality and complexity of multi-objective optimization in the flexible job shop scheduling problem, the traditional NSGA-III(Non-dominated Sorting Genetic Algorithm III) algorithm suffers from shortcomings in global exploration and local exploitation capabilities, easily getting trapped in local optima and exhibiting slow convergence speed. Therefore, this paper proposes a hybrid optimization algorithm, SSA-NSGA-III(Sparrow Search Algorithm - Non-dominated Sorting Genetic Algorithm III), which integrates the Sparrow Search algorithm and NSGA-III. This algorithm employs a two-stage encoding to represent the process sequence and machine allocation, and designs a hybrid initialization strategy to improve the quality of the initial population. By introducing the division of labor and cooperation mechanism of the sparrow roles in SSA to replace traditional genetic operations, it enhances global search and local fine-tuning capabilities. Furthermore, it utilizes the reference point mechanism of NSGA-III to maintain the diversity and distribution of the solution set. Experiments based on the Brandimarte standard test set, with maximum completion time, total machine load, and total energy consumption as optimization objectives, show that SSA-NSGA-III outperforms the traditional NSGA-III, NSGA-II(Non-dominated Sorting Genetic Algorithm II), and SSA(Sparrow Search Algorithm) algorithms on multiple test problems. It can stably obtain a high-quality solution set with uniform distribution and approximation of the real Pareto front, verifying its effectiveness and superiority in solving the multi-objective flexible job shop scheduling problem.