SchedDiff: Diffusion-Based Priority Refinement for Job Shop Scheduling

Neural combinatorial optimization methods for the Job Shop Scheduling Problem (JSSP) face a fundamental trade-off between solution quality and inference efficiency: constructive methods build high-quality schedules through sequential decisions whose computational cost scales with problem size, whereas one-shot methods offer highly efficient single-pass inference at the expense of solution quality. We propose SchedDiff, the first diffusion-based framework for JSSP, which bridges this gap by iteratively refining operation priorities through a fixed number of denoising steps. Unlike existing diffusion models for combinatorial optimization that operate in a binary space, SchedDiff operates directly in a discrete ordinal space, introducing a forward process and learning objective specifically tailored to ranking structures. To decode the refined priorities into feasible schedules, we introduce active list scheduling, which provably produces more compact schedules than standard list scheduling. Extensive experiments on TA, DMU, and LA benchmarks demonstrate that SchedDiff achieves state-of-the-art performance among learning-based methods, with efficiency advantages that become more pronounced on large-scale instances. SchedDiff further exhibits strong generalization, scaling to instances significantly larger than those seen during training, generalizing across unseen problem distributions, and transferring zero-shot to flexible JSSP.