A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

Technical Summary: A Genetic Algorithm with Critical‑Path‑Driven Dual‑Neighborhood Search for Flexible Job Shop Scheduling

Problem Definition
The paper addresses the Flexible Job Shop Scheduling Problem (FJSP), a strongly NP-hard optimization challenge prevalent in modern manufacturing. Unlike the classical Job Shop Scheduling Problem (JSP), where operations have fixed machine assignments, FJSP allows each operation to be processed on any machine from a set of alternative candidates, often with varying processing times. The primary objective is to minimize the makespan ($C_{max}$), defined as the maximum completion time of all jobs. The problem involves determining both the machine selection for each operation and the processing sequence on each machine while satisfying precedence constraints and machine availability.

Methodology: HGVNSA
The authors propose a Hybrid Genetic Variable Neighborhood Search Algorithm (HGVNSA) that integrates a Genetic Algorithm (GA) for global exploration with a Critical-Path-Driven Variable Neighborhood Search (VNS) for local exploitation.

1. Encoding and Decoding: The solution is represented using a two-layer encoding: an Operation Sequence (OS) vector and a Machine Selection (MS) vector. An active decoding strategy is employed to generate feasible schedules.
2. Population Initialization: To balance quality and diversity, the initial population is generated using a hybrid strategy: Global Selection (60%, minimizing global load increment), Local Selection (30%, balancing load within jobs), and Random Selection (10%).
3. Genetic Operations:
   • Crossover: A Path-Relinking (PR) based crossover operator is introduced. Instead of random gene swapping, it systematically transforms one parent solution into another, recording and evaluating intermediate solutions to exploit the search space between parents.
   • Mutation: An adaptive mutation mechanism adjusts probabilities based on individual fitness and generation count. Two mutation types are used: OS mutation (shuffling operation order) and MS mutation (changing machine assignments).
   • Diversity Preservation: A Hamming distance-based strategy is employed to maintain population diversity and prevent premature convergence.
4. Critical-Path-Driven Dual-Neighborhood VNS: Embedded within the GA framework, this local search focuses on operations located on the critical path (the longest path in the disjunctive graph). It utilizes two complementary neighborhood structures:
   • N8 Neighborhood: Optimizes the sequence of operations on the same machine. It extends traditional N5-N7 moves by allowing critical operations outside critical blocks to be moved to block endpoints or pre/post-block positions.
   • k-Insertion Neighborhood: Reallocates critical operations to different machines. This involves traversing alternative machines and inserting the operation at feasible positions, checking for cyclic dependencies.
   • Search Strategy: The VNS process prioritizes the N8 neighborhood (lower computational cost) and switches to k-insertion (higher cost, broader search) only if no improvement is found, ensuring a balance between efficiency and exploration depth.

Key Contributions
The paper outlines five principal contributions:

1. Hybrid Framework: It establishes a synergistic "global exploration first, local exploitation thereafter" framework, effectively balancing solution accuracy and computational efficiency.
2. Dual-Neighborhood Integration: It is the first to integrate the N8 and k-insertion neighborhoods within a unified VNS framework for FJSP. This combination addresses both intra-machine sequencing and inter-machine reallocation, significantly enhancing local search capability.
3. Enhanced Genetic Operators: The introduction of Path-Relinking crossover and adaptive mutation probabilities strengthens the algorithm's ability to explore the solution space and maintain convergence stability.
4. Benchmark Performance: On the Brandimarte MK benchmark set, HGVNSA consistently reaches known optimal solutions in 6 out of 10 instances (MK01-MK04, MK08-MK09) and achieves the lowest average Relative Percentage Deviation (RPD) of 0.06% among compared algorithms (HGWO, HLO-PSO, HA, SLGA, ISLGA).
5. Real-World Application: The algorithm was applied to a gear shaft processing scenario at Company A. Compared to a traditional Genetic Algorithm, HGVNSA improved production efficiency by 8.81%, demonstrating its engineering practicality.

Results and Validation

• Benchmark Testing: Extensive experiments on the MK01-MK10 instances showed that HGVNSA outperformed comparison algorithms in terms of solution quality and stability. Ablation studies confirmed that removing the VNS component, the dual-neighborhood structure, or the adaptive mechanisms led to significant performance degradation (e.g., removing VNS increased the average makespan on MK02 from 26 to 30.4).
• Case Study: In the Company A case study involving 10 jobs and 59 operations across 15 machines, the algorithm reduced the makespan from 522 (traditional GA) to 476.
• Convergence: Convergence analysis indicated that while other algorithms stagnated after initial rapid convergence, HGVNSA continued to refine solutions through its local search mechanisms, breaking through local optima in later iterations.

Significance
The paper claims that HGVNSA provides an efficient and robust solution framework for the FJSP, effectively addressing the challenges of balancing global and local search and designing effective neighborhood structures. The study validates that combining critical-path-driven local search with genetic evolution yields superior results in both theoretical benchmarks and practical industrial settings. The authors suggest that this work lays a foundation for future research into distributed scheduling and the use of deep reinforcement learning for intelligent neighborhood selection, though they do not claim these extensions have been implemented in the current study.