Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes L-RHO, a learning-guided rolling horizon optimization that uses a neural network to fix machine assignments of overlapping operations across RHO iterations, accelerating long-horizon FJSP solving with CP-SAT subproblems.
Problem
Rolling horizon optimization for long-horizon combinatorial problems such as flexible job-shop scheduling wastes computation re-optimizing overlapping operations whose machine assignments rarely change between consecutive subproblems.
Approach
Train a neural network to predict which overlapping operations keep their previous machine assignment (imitating a look-ahead oracle) and fix those assignments, yielding smaller restricted subproblems solved by CP-SAT; also gives a probabilistic analysis of when learning beats heuristic fixing (random/first).
Key results
- On makespan FJSP with 600-2000 operations, L-RHO (450) reduces solve time versus Default RHO (e.g., 259s vs 545s at 1200 ops) and improves makespan (e.g., 3011 vs 3136 at 1200 ops).
- Under the total start delay objective, L-RHO achieves 35%-53% time improvement and 13%-21% objective improvement over Default RHO across horizons.
- L-RHO accelerates RHO by up to 54% while improving solution quality, outperforming heuristic fixing (Random, First) and warm-start RHO.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP makespan, 600 operations | Time (s): 244 ± 21 -> 126 ± 19 | Helped |
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP makespan, 600 operations | Makespan: 1558 ± 73 -> 1513 ± 70 | Helped |
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP makespan, 800 operations | Time (s): 348 ± 26 -> 160 ± 23 | Helped |
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP makespan, 1200 operations | Makespan: 3136 ± 91 -> 3011 ± 106 | Helped |
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP makespan, 2000 operations transfer | Time (s): 862 ± 42 -> 473 ± 52 | Helped |
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP makespan, 2000 operations transfer | Makespan: 5207 ± 114 -> 4982 ± 132 | Helped |
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP start delay, 600 operations | TI %: +53.0% ± 1.0% | Helped |
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP start delay, 600 operations | OI %: +16.0% ± 1.9% | Helped |
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP start delay, 1050 operations | OI %: +21.0% ± 2.4% | Helped |
| Use learned assignment-based restrictions instead of unrestricted RHO | RHO · FJSP start delay, 1600 operations | TI %: +47.3% ± 2.2% | Helped |
| Provide previous machine assignments as warm-start hints rather than fixing operations (ablation) | RHO · FJSP start delay, 1050 operations | TI %: -12.9% ± 1.6% | Hurt |
| Provide previous machine assignments as warm-start hints rather than fixing operations (ablation) | RHO · FJSP start delay, 600 operations | OI %: -7.5% ± 2.8% | Hurt |
Surprising findings
- Warm Start RHO, using previous assignments as CP-SAT hints, does not significantly outperform Default RHO.
- Oracle-LNS, which uses look-ahead selection of LNS subproblems, still underperforms Default RHO on makespan, suggesting RHO suits long-horizon FJSP better than LNS.
Limitations
- L-RHO alone may not achieve state-of-the-art performance when extended to other long-horizon COPs.
- Restriction is limited to assignment-based fixing; other restriction methods are left for future work.
- Simple MLP architecture; more advanced architectures showed no significant improvement in preliminary tests and were not explored.
Experimental setup
Datasets: synthetic FJSP instances generated following prior procedure
Benchmarks: synthetic FJSP makespan instances (600-2000 operations) start-delay FJSP instances (600-1600 operations) end-delay / combined delay FJSP machine breakdown and observation-noise FJSP variants
Metrics: makespan total start delay solve time time improvement (TI%) objective improvement (OI%)
Baselines: CP-SAT Genetic Algorithm DRL-20K DRL-Echeverria DRL-Ho ARD-LNS (Time-based) ARD-LNS (Machine-based) Oracle-LNS Default RHO Warm Start RHO Random First
Builds on: rolling horizon optimization CP-SAT adaptive randomized decomposition
Closest papers by meaning
- Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling (NeurIPS 2025 · similarity 0.86)
- Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems (AAAI 2025 · similarity 0.86)
- DynaSchedBench: Calibrated Dynamic Scheduling Benchmarks and Observability Paradox in LLM-based Scheduling Agents (ICML 2026 · similarity 0.86)
- BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.84)
- Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling (ICLR 2024 · similarity 0.83)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.