DiffTP: Graph Diffusion for Job Shop Scheduling with Transitive Precedence Modeling

Graph diffusion models have shown strong potential for routing problems, where routes are converted into heatmaps of consecutive node connections and solutions are generated through iterative denoising. However, directly applying graph diffusion to the Job Shop Scheduling Problem (JSSP), by encoding each machine sequence as a heatmap of consecutive operation pairs, does not yield satisfactory results. Our analysis reveals that the key lies in a fundamental difference between routes and schedules: while a route is defined by connections between consecutive nodes, a schedule is characterized by precedence relations that must satisfy transitivity. This leads to our key insight: diffusion learning for JSSP should explicitly capture the transitive precedence relations among operations, rather than only their consecutive relations. Based on this insight, we propose DiffTP, a graph Diffusion framework for JSSP with Transitive Precedence modeling. DiffTP consists of two components: (1) a Graph Transformer denoiser that alternates message passing over job and machine relations to model the scheduling constraints in JSSP; and (2) a diffusion learning scheme that uses precedence heatmaps derived from the transitive closure of machine sequences as denoising targets. During inference, DiffTP iteratively denoises the precedence heatmap to predict machine precedence relations, which are then used to guide feasible schedule construction. Experiments on standard JSSP benchmarks demonstrate that DiffTP achieves competitive performance against state-of-the-art constructive baselines.