2025年5月18日 星期日

FJSP

 

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 DesignMS-relative (MOPSL), OS-guidedDefines coordinate system of the space, controls densitySearch Space Embedding for GA-based FJSP
2️⃣ InitializationGreedy / Random / Load-basedDetermines seed distribution within the geometric spaceMulti-Perspective Initialization in Embedded Space
3️⃣ GA EvolutionCP-aware crossover / mutationLocal differential operators in tension fieldDifferentiable Operators for Critical Path Evolution
4️⃣ Objective FunctionsCmax, tardiness, energy, etc.Scalar field shaping the evolution gradientObjective Field Shaping in Scheduling Geometry
5️⃣ Memory / ReuseElite pool, restart, learning-based recall

沒有留言: