KTNSGA-II: An Enhanced Hybrid Heuristic Algorithm for Multi-Objective Flexible Job Shop Scheduling with Makespan Workload Balance and Energy Consumption

The Multi-Objective Flexible Job Shop Scheduling Problem (MOFJSSP) represents a core challenge in modern manufacturing: achieving synergistic optimization of multiple conflicting objectives while pursuing production efficiency and energy sustainability. To address this, this study proposes an enhanced hybrid heuristic algorithm—KNN–Tabu Search NSGA-II (KTNSGA-II)—for simultaneously optimizing completion time, machine load, and total energy consumption. First, a three-objective mathematical model is established. Subsequently, four key strategies are integrated: (1) workload balancing initialization rapidly generates high-quality initial solutions; (2) an adaptive job-level crossover mechanism dynamically adjusts subset sizes during iterations to balance global exploration and local exploitation; (3) K-nearest neighbor-based congestion distance calculation maintains population diversity; (4) tabu search applied to non-dominated solutions on the Pareto front for local refinement. Extensive experiments on standard benchmark instances demonstrate that KTNSGA-II significantly outperforms representative algorithms in terms of convergence and diversity. For large-scale Behnke benchmark instances, KTNSGA-II achieves an average hypervolume (HV) improvement of 32.32% compared to other comparison algorithms. Furthermore, this method substantially enhances solution diversity: the Spacing Performance (SP) metric improved by 39.72%, indicating more uniform distribution of Pareto optimal solutions; the Diversity Metric (DM) increased by 57.54%, reflecting broader coverage and more even distribution along the Pareto frontier boundary. These results confirm that KTNSGA-II generates higher-quality, better-distributed Pareto fronts, achieving a more optimal trade-off between completion time, machine load, and energy consumption.