Abstract:

The job-shop scheduling problem (JSSP) is a classic NP-hard combinatorial optimization problem with broad applications in manufacturing, logistics, and related domains. Due to its exponential computational complexity with increasing jobs and machines, traditional exact algorithms struggle with large-scale instances, while existing heuristic and deep learning-based methods often inadequately exploit global information. Furthermore, these approaches typically generate solutions from a single distribution, failing to capture the inherent multi-modality of combinatorial optimization problems. To address these limitations, we propose a novel global information prediction method based on diffusion probabilistic models. Our approach adapts the diffusion model to the structural constraints of JSSP, predicting a heatmap that represents the distribution of optimal solutions. Leveraging this heatmap, we perform constrained optimization and local search, effectively harnessing the model’s multi-modal generation capability and global information encoding. This results in high-quality, constraint-satisfying scheduling solutions. For enhanced computational efficiency, we implement our framework on the domestic deep learning platform Jittor, developing an optimized JSSP solving pipeline that achieves up to 40% faster inference than PyTorch. Extensive experiments on mainstream benchmarks demonstrate that our method outperforms existing approaches across varying problem scales, delivering state-of-the-art solution quality. To the best of our knowledge, this work presents the first diffusion-based solver for JSSP.

Key words: Job-shop scheduling problem, diffusion probabilistic model, graph neural network, combinatorial optimization, Jittor