Research map / Optimization / Optimizers

Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems

AAAI 2025 · Optimization › Optimizers · approach: Differentiating through embedded optimization · 2 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 an attention-based scenario processing module (SPM) that embeds sampled processing-time scenarios and plugs into the DAN neural combinatorial optimization policy, trained with PPO to minimize expected makespan or VaR for the stochastic flexible job shop.

Problem

Neural combinatorial optimization methods target deterministic scheduling; stochastic flexible job shop scheduling with uncertain processing times needs a one-time robust schedule optimizing expected makespan or Value-at-Risk.

Approach

An inducing-point multi-head attention module (SPM) encodes sampled scenario states into a stochasticity embedding that is concatenated with deterministic features of a base NCO network (DAN), with a training paradigm using scenario-based rewards from independent samples to optimize VaR or mean makespan.

Key results

• SPM-DAN with sampling inference achieves about -7.1% gap to CP-SAT on SD3 20x10 instances under VaR95 (vs. 0.00% for CP-SAT and -2.27% for DAN with sampling).
• On 40x10 SD3 generalization from 20x10-trained policies, SPM-DAN greedy reaches -6.06% gap vs. DAN greedy -0.17%.
• On public benchmark vdata, SPM-DAN sampling is up to 8% better than CP-SAT under the reported setting.

Measured effects reported in the paper

Surprising findings

• DAN-stoch (DAN with the stochastic reward but no SPM) does not consistently outperform the deterministic DAN, showing that the scenario reward alone is insufficient.
• Training with more scenarios (200) does not always improve performance over 100 scenarios, especially on smaller instances.

Limitations

• Greedy-constructed policies still lag sampling-based inference, and sampling is considerably slower (about 3x runtime).
• CP-stoch is not scalable to larger instances due to memory limits.
• No reported comparison to other stochastic NCO methods besides DAN variants; SD1 small-instance gains are not significant.

Experimental setup

Datasets: SD1 synthetic FJSP SD3 synthetic FJSP (new) mk benchmark rdata edata vdata

Benchmarks: SD1 synthetic FJSP SD3 synthetic FJSP mk rdata edata vdata beta/mixed distribution SD3 sets

Metrics: VaR95 makespan expected makespan gap to CP-SAT inference time t-test significance

Baselines: FIFO MOR MWKR SPT DAN DAN-stoch OR-tools CP-SAT CP-stoch

Builds on: DAN PPO L2D multi-head attention set transformer inducing points

Closest papers by meaning

• Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.87)
• BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization (ICML 2025 · similarity 0.87)
• Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling (ICLR 2025 · similarity 0.86)
• Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling (NeurIPS 2025 · similarity 0.86)
• Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.85)
• Probing Neural Combinatorial Optimization Models (NeurIPS 2025 · similarity 0.85)