- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes DiffTP, a diffusion-based generative solver for Job Shop Scheduling Problem (JSSP). The key design is the transitive precedence and machine precedence heatmaps that directly supervise non-consecutive ordering relations. The authors further develop a diffusion-based network for JSSP. It applies discrete graph diffusion to generate the conditional heatmaps. The experiments shows that the DiffTP achieves the lowest average gaps among the evaluated constructive methods on TA and DMU at the reported sampling budgets.
Critical strengths
-
This paper expands the application of non-autoregressive diffusion-based generative models in COP from the traditional routing problems (TSP) to a scheduling problem.
-
This paper designs a specific representation for JSSP. A transitive closure and machine precedence heatmap enables both learnable diffusion target and feasible solution decoding for JSSP. I believe this is the key to migrate the non-autoregressive diffusion-based generative model from solving TSPs to JSSP. The ablation results in Table 3 and Table 9 (in Appendix F) also show that using this representation achieves the most significant performance gains, demonstrating the effectiveness of the representation design in this paper.
-
The performance of DiffTP outperforms most learning-based scheduling methods.
Critical weaknesses
-
Compared to the contributions in terms of its representation of JSSP, the technical contributions in terms of network framework and training are relatively weaker. The overall framework largely reuses existing methods, such as the graph embedding network, the optimization-consistency training and GT decoder, although the same amount of space is allocated in the main text of this paper.
-
The representation and decoding designs are coupled in this paper. Although they are introduced separately in the paper, they are not analyzed independently. For example, the feasibility of the generated solution is enforced by the decoding procedure, so it is unknown whether the network has learned the probability distribution of the solution, or has learned a distribution that can be repaired to a good solution by the decoding procedure. Similarly, there lacks a further systematic analysis about why such representation works for JSSP solution generation.
-
The abbreviation “TA” and “DMU” are not explained when they first appear in Section 1.
Questions for authors
-
Why does the transitive closure only consider the precedence relationship among machines? Can the precedence relationship among the jobs be considered?
-
Regarding the representations proposed in this article, is its convergence still consistent with the existing discrete DDIM framework?
11 comments
representation–decoder compatibility is isolated
W2: We thank the reviewer for this suggestion. We added four target-specific decoder controls experiments. The results show that the transitive model retains useful ordering information without GT and produces more jointly feasible machine orders at larger tested job counts. We address the concern in three parts.
1. Representation–decoder compatibility. We added four controls combining adjacent/closure job graphs with successor/transitive machine targets. Successor models use path merging, while transitive models use Borda, for both validation and testing; neither uses GT. With training seed 12345 and three evaluation seeds (12345, 23456, and 34567) at K=32/S=50, the results are:
| Group | Job / machine relations | TA gap (%) | DMU gap (%) |
|---|---|---|---|
| A | Adjacent / successor | 231.904 ± 1.893 | 289.508 ± 2.385 |
| B | Adjacent / transitive | 16.584 ± 0.051 | 29.991 ± 0.197 |
| C | Closure / successor | 191.896 ± 0.874 | 200.854 ± 1.116 |
| D | Closure / transitive | 6.237 ± 0.052 | 15.261 ± 0.103 |
Here ± denotes the sample standard deviation across evaluation-seed dataset means. Thus, the transitive design remains effective with target-specific decoding, beyond compatibility with GT. In particular, B→D holds the machine target and decoder fixed and demonstrates the benefit of job closure. We also added this experiment in our revised paper in Appendix J.
2. What has the network learned? Three observations support learned precedence structure rather than only GT-specific preferences. First, group D achieves useful performance without GT, including using Borda for checkpoint selection. Second, the original same-model Non-GT ablation replaces GT with Borda and feasibility repair: TA/DMU gaps change from 5.2%/12.0% to 5.6%/14.0% (Table 3). Useful ordering information therefore remains accessible to a different decoder. Third, Appendix H shows increasingly structured precedence patterns along denoising trajectories, alongside reference heatmaps. Together, these observations support learning meaningful transitive-order preferences.
3. Why does transitive precedence help? JSSP requires multiple machine permutations to be jointly compatible with fixed job precedences: a valid order on each machine alone does not guarantee a feasible schedule. Transitive supervision specifies each operation's relation to every other operation on its machine, whereas consecutive-successor supervision specifies local successor links. Exact predictions determine the same complete order; the practical distinction is how prediction errors affect operation placement.
With transitive predictions, an operation’s position can be recovered by aggregating its precedence scores, . For an exact order with one-based rank , . If each row score differs from its exact value by at most , any pair whose rank separation exceeds retains its score ordering. This illustrates how multiple comparisons can stabilize nonlocal placement. However, consecutive successor recovery relies on connecting local paths. If a connecting relation is incorrect, a correctly ordered fragment can still be placed in the wrong part of the sequence. Such displacement may remain a valid machine permutation but conflict with fixed job precedences and other machines’ orders. We evaluated C and D on 40 TA instances (10 per size), with K=32, S=50 and evaluation seed 12345. The following metrics are measured on native machine orders before global feasibility repair, averaging candidates within each instance and then instances within each size.
| Shape | Pre-repair feasibility C / D (%) |
|---|---|
| 15×15 | 98.75 / 99.69 |
| 20×15 | 87.81 / 100.00 |
| 30×15 | 25.31 / 100.00 |
| 50×15 | 0.00 / 100.00 |
Our experiments show that these joint conflicts become substantially more frequent for the successor model at larger tested job counts: at 30×15, C and D pre-repair feasibility rates are 25.31% and 100%; at 50×15, the rates are 0% and 100%. These results support the value of transitive-precedence representation for JSSP: by explicitly supervising nonlocal ordering relations, it provides multiple references for operation placement and supports more globally consistent machine orders in our experiments.
W3: We thank the reviewer for identifying this omission. We expand TA as the Taillard benchmark and DMU as the Demirkol–Mehta–Uzsoy benchmark at their first occurrence in Section 1 and include the corresponding references in our revised paper.
Q1: Job precedence can also be represented by transitive closure, and we added an explicit comparison showing that it improves performance. These fixed job edges condition message passing; the model predicts the uncertain machine relations.
Holding the transitive machine target and Borda decoder fixed, adjacent job edges yield TA/DMU gaps of 16.584 ± 0.051% / 29.991 ± 0.197%, versus 6.237 ± 0.052% / 15.261 ± 0.103% with job closure. Both settings use training seed 12345 and evaluation seeds 12345/23456/34567 at K=32/S=50. Here ± is the sample SD across the three evaluation-seed dataset means for each fixed trained model.
Thus, job closure is both compatible with the framework and beneficial in this controlled comparison.
Q2: We thank the reviewer for this question. The transitive-precedence representation remains compatible with categorical corruption and timestep-subsampled reverse updates. The formulation below explains this compatibility, and Appendix H visualizes the learned denoising process.
1. Formulation. We diffuse one binary variable per unordered same-machine pair and obtain the opposite direction by complementation. Let have uniform binary rows and . For any clean target,
Thus, corruption approaches uniform binary noise as . The same binary corruption rule also applies to consecutive-successor variables, although those models use independently predicted directed pairs rather than complementary directions. Corruption is independent conditional on the clean heatmap, not requiring independence of the clean relations or feasibility of intermediate noisy states.
For selected times , the composed transition is . The corresponding posterior is
This is normalized because (for positive-probability conditioning events and ). Mixing these posteriors with the network's predicted clean-state probabilities defines the reverse update. Therefore, the transitive target does not invalidate the subsampled categorical diffusion formulation in Appendix C.1–C.2.
2. Denoising visualizations. Appendix H shows machine-wise heatmap predictions along denoising trajectories at multiple DMU scales, with fixed operation-indexed axes and reference heatmaps for comparison. The predictions develop more structured precedence patterns as denoising proceeds, providing qualitative evidence that the network learns ordering information through the reverse process. Thus, transitive precedence changes the clean target without invalidating the categorical diffusion updates.
transitive representation is critical
Thank you for your valuable feedback.
W1: We sincerely thank the reviewer for pushing us to clarify our core contribution. The transitive representation is itself our central methodological contribution and is critical for JSSP: Transitive precedence provides a more redundant representation of the overall machine order: each operation’s position is supported by comparisons with multiple other operations. Consequently, a few incorrect predictions need not erase its relative position in the sequence. Consecutive-successor representations instead rely on local connections; errors in these connections can fragment the predicted sequence and make the relative placement of the resulting segments ambiguous. In JSSP, such misplaced segments can also conflict with job precedence constraints. The target-specific decoding comparisons in Appendix A support the benefit of the transitive design.
More broadly, our findings suggest that the choice of supervised relations—not only the generative backbone—is an important design dimension for scheduling models. Explicitly learning non-local precedence may offer a useful direction for other precedence-constrained scheduling problems. We will emphasize this broader contribution in the revision.