Title: Embedding NP-Hard FJSP into Structured Geometric Evolution: A CP-Guided MOPSL Approach
Abstract
This paper proposes a novel genetic algorithm (GA) framework for solving the Flexible Job Shop Scheduling Problem (FJSP), focusing on embedding the NP-hard problem into a dense and geometrically interpretable space through a structured chromosome encoding. By decoupling machine selection (MS) and operation sequencing (OS) via a Multi-Objective Position-based Structured Learning (MOPSL) scheme, the algorithm enables adaptive evolution guided by critical path awareness. We introduce reward-based adaptive operator selection and slope-based mutation tuning to drive convergence. Experiments on MK benchmark datasets demonstrate performance reaching or surpassing current state-of-the-art results, particularly on MK10.
Introduction
FJSP is an NP-hard combinatorial optimization problem characterized by dual-level decisions: machine routing and operation sequencing. Traditional GA approaches often conflate these layers, leading to sparsity and difficulty in convergence. This work aims to decouple and embed FJSP into a structured space that supports critical path-guided learning and adaptive evolution, resulting in a new paradigm for optimization through structured geometry.
Literature Review
Key works that inform this study include:
Brandimarte (1993): Tabu search for routing and scheduling in FJSP [1].
Somohano-Murrieta et al. (2023): Encoding strategies for FJSP [2].
Sun et al. (2023): Hybrid GA with Variable Neighborhood Search [3].
These papers highlight the need for effective encoding, adaptive operators, and critical path exploitation. However, they lack a unified spatial interpretation or learning-based adaptation.
Methodology
1. MOPSL Encoding Scheme
We introduce an integer-based MS (relative machine index) and OS (ready-set-based sequencing) encoding. The OS sequence evolves through a CP-aware prioritization scheme using slack and criticality rank.
2. Critical Path-Aware Operators
MS Mutation: Machine selections on the critical path are locally optimized based on processing time and machine load.
OS Mutation: Operations are reordered via guided heuristics based on criticality and slack.
Adaptive VNS/Tabu: A dynamic strategy that adjusts the neighborhood size and tenure based on Cmax plateaus.
3. Reward-Based Adaptive Control
Each adjustment is tracked via its impact on makespan. A reward system adjusts the preference for MS or OS adjustment dynamically, reinforcing effective directions in the geometric space.
4. Dense Space Embedding
By using relative indexing and structured decoding, the MOPSL space avoids invalid individuals and ensures smooth search gradients. This enhances GA's ability to exploit and explore efficiently.
Experimental Results
Benchmark: MK01-MK10
MK10 achieves Cmax = 215, matching or improving over the best-known results.
Performance metrics include convergence speed, stability, and learning efficiency of MS/OS dynamics.
Discussion
We interpret the results through the lens of a geometric model:
The MS component adjusts the routing topology.
The OS component adjusts time-based sequencing.
The evolutionary trajectory forms a path through a manifold structured by the critical path dynamics.
Conclusion
By embedding FJSP into a structured, dense geometric space via MOPSL, and guiding evolution with critical path insights and adaptive learning, we transform an NP-hard problem into a geometry-navigable one. This enables effective, interpretable, and state-of-the-art optimization.
References
[1] Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3), 157-183.
[2] Somohano-Murrieta, J. C. B., et al. (2023). A new solution encoding scheme for solving the Flexible Job-Shop Scheduling Problem. IEEE CEC.
[3] Sun, K., et al. (2023). Hybrid genetic algorithm with variable neighborhood search. Expert Systems with Applications, 215, 119359.
Unified Model vs. Strategic Roadmap Mapping Table
| Category 🧭 | Strategy Element 🧠 | Role in Geometric Model 🔬 | Contribution-Driven Thesis 🎯 |
|---|
| 1️⃣ Search Space Design | MS-relative (MOPSL), OS-guided | Defines coordinate system of the space, controls density | Search Space Embedding for GA-based FJSP |
| 2️⃣ Initialization | Greedy / Random / Load-based | Determines seed distribution within the geometric space | Multi-Perspective Initialization in Embedded Space |
| 3️⃣ GA Evolution | CP-aware crossover / mutation | Local differential operators in tension field | Differentiable Operators for Critical Path Evolution |
| 4️⃣ Objective Functions | Cmax, tardiness, energy, etc. | Scalar field shaping the evolution gradient | Objective Field Shaping in Scheduling Geometry |
| 5️⃣ Memory / Reuse | Elite pool, restart, learning-based recall |
