Research map / Reinforcement learning / Visual and representation RL

Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling

NeurIPS 2025 · Reinforcement learning › Visual and representation RL · approach: RL for combinatorial routing · 1 citations (OpenAlex)

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 MIStar, a DRL-based improvement heuristic for flexible job shop scheduling that uses a directed heterogeneous disjunctive graph, a memory-enhanced heterogeneous GNN, and parallel greedy search trained with n-step PPO.

Problem

Flexible job shop scheduling (FJSP) with flexible machine assignment; prior DRL methods are mostly constructive and improvement-based DRL methods were designed for non-flexible JSP, struggling with state representation, action design, and local optima.

Approach

Represent complete FJSP solutions as a directed heterogeneous disjunctive graph with machine nodes and directed hyper-arcs for machine sequences, use a memory of past states and actions (similarity by Frobenius inner product of operation-machine order matrices, soft-voted historical actions) inside the GNN policy, and act on Nopt2 moves with parallel greedy selection of P candidates per step.

Key results

• On SD2 small instances at 100 iterations, MIStar achieves lower makespan gaps than DANIEL and HGNN greedy/sampling and rule-based GD/FI/BI (e.g., 5.77% vs 10.40% GD on SD2 10x5).
• On Brandimarte mk, MIStar-100 achieves 3.07% gap versus 3.44% for BI-100 and 6.84-15.94% for DRL construction methods.
• On 50x30 instances, OR-Tools found no feasible solution within 60 minutes while MIStar-200 produced a solution (objective 1040.1).

Measured effects reported in the paper

Surprising findings

• On SD2 40x10 generalization, BI slightly beats MIStar at 100 iterations and 0.06% gap-level differences appear, while MIStar continues improving with more iterations where rule-based methods stagnate.
• Improvement from DRL-sampled initial solutions is still notable even when starting from near-optimal DANIEL(S) solutions; on SD1 initial solutions are near-optimal, limiting gains.

Limitations

• Improvement from random or weak initial solutions depends on initialization quality; sensitivity to initial solution.
• Parallel scale P must be tuned per instance; optimal value depends on instance characteristics.
• Only incremental local moves (Nopt2); does not explore disruptive moves in larger neighborhoods.

Experimental setup

Datasets: SD1 SD2 Hurink Brandimarte

Benchmarks: SD1 SD2 Hurink (edata, rdata, vdata) Brandimarte (mk) larger synthetic instances up to 1500 operations

Metrics: makespan (objective) relative gap to best-known runtime

Baselines: DANIEL HGNN greedy improvement (GD) first-improvement (FI) best-improvement (BI) Google OR-Tools 2SGA MARCO-style memory (discussed)

Builds on: PPO Graph Isomorphism Network Graph Attention Network Nopt2 neighborhood DANIEL HGNN

Closest papers by meaning

• Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling (ICLR 2024 · similarity 0.92)
• Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling (ICLR 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.85)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-Based Imitation Learning (AAAI 2024 · similarity 0.85)
• Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.84)