What question did this study set out to answer?

This research aims to develop an efficient solver for the Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W).

May 19, 2026Open Access

Problem Floors and State Memory for Flexible Job Shop Scheduling

Key Points

This research aims to develop an efficient solver for the Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W).
Introduced a lightweight solver that decomposes FJSSP-W into sequence optimization and worker allocation problems.
Implemented a state memory structure to track explored configurations and prevent repeated evaluations.
Tested the solver on 30 benchmark instances from the IEEE WCCI 2026 FJSSP-W competition.
The solver converged in a mean of 91 evaluations across 30 benchmarks, outperforming greedy baselines in all instances.
Observed Spearman correlation between makespan and gap percentage was ρₛ = −0.21, suggesting minimal impact from instance size.
Achieved results using only 0.002% of available evaluations, demonstrating significant efficiency.

Abstract

Problem Floors and State Memory for Flexible Job Shop Scheduling A Lightweight Solver for the FJSSP-W Problem We present a lightweight, memory-guided solver for the Flexible Job Shop Scheduling Problem with Worker Flexibility (FJSSP-W). The method decomposes FJSSP-W into two sub-problems: a Hamiltonian Path on the job interleaving graph for sequence optimisation, and a congestion-aware greedy assignment for machine and worker allocation. A state memory structure records every explored configuration to prevent repeated evaluation of failed states. A floor detector terminates the search at the structural problem floor — the point where the remaining gap is entangled with satisfied constraints. Across 30 benchmark instances from the IEEE WCCI 2026 FJSSP-W competition, the solver converges in 43–159 evaluations (mean 91), reducing makespan over greedy baselines in every instance. Results are cross-validated on two independent machines (Raspberry Pi 4 and Apple M4) across 10 deterministic seeds (300 total runs). The central finding: the Spearman rank correlation between makespan and gap percentage is ρₛ = −0.21 — near zero. The gap is driven by structural entanglement, not instance size. The floor is where the problem stops, not where the solver gives up. The competition allocates 5,000,000 evaluations per run. This solver uses 0.002% of that budget. Five million evaluations is not a budget. It is an apology for not knowing where the floor is. Keywords 1. Flexible Job Shop Scheduling 2. Wavelength Convergence 3. Frequency Decomposition 4. Hamiltonian Path 5. Problem Floors 6. Ouroboros Engine 7. FJSSP-W 8. Meta-heuristic 9. Combinatorial Optimization 10. IEEE WCCI 2026 Companion: On Problem Floors (DOI: 10.5281/zenodo.20113182) License: CC BY 4.0

Read Full Paperexternally

AI से पूछें

Bookmark

View Full Paper