acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
optimization
Keywords:
graph diffusion model, job shop scheduling, combinatorial optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 2 reviews, above 27% of the others.
Reviewer_hAdPOpenReview ↗
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
  1. This paper expands the application of non-autoregressive diffusion-based generative models in COP from the traditional routing problems (TSP) to a scheduling problem.

  2. 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.

  3. The performance of DiffTP outperforms most learning-based scheduling methods.

Critical weaknesses
  1. 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.

  2. 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.

  3. The abbreviation “TA” and “DMU” are not explained when they first appear in Section 1.

Questions for authors
  1. Why does the transitive closure only consider the precedence relationship among machines? Can the precedence relationship among the jobs be considered?

  2. Regarding the representations proposed in this article, is its convergence still consistent with the existing discrete DDIM framework?

11 comments
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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:

GroupJob / machine relationsTA gap (%)DMU gap (%)
AAdjacent / successor231.904 ± 1.893289.508 ± 2.385
BAdjacent / transitive16.584 ± 0.05129.991 ± 0.197
CClosure / successor191.896 ± 0.874200.854 ± 1.116
DClosure / transitive6.237 ± 0.05215.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, bi=∑j≠iPijb_i=\sum_{j\ne i}P_{ij}. For an exact order with one-based rank rir_i, bi=J−rib_i=J-r_i. If each row score differs from its exact value by at most ϵ\epsilon, any pair whose rank separation exceeds 2ϵ2\epsilon 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.

ShapePre-repair feasibility C / D (%)
15×1598.75 / 99.69
20×1587.81 / 100.00
30×1525.31 / 100.00
50×150.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 UU have uniform binary rows and Qˉt=αˉtI+(1−αˉt)U\bar Q_t=\bar\alpha_t I+(1-\bar\alpha_t)U. For any clean target,q(Et,p=1∣E0,p)=αˉtE0,p+1−αˉt2.q(E_{t,p}=1\mid E_{0,p})=\bar\alpha_t E_{0,p}+\frac{1-\bar\alpha_t}{2}.

Thus, corruption approaches uniform binary noise as αˉt→0\bar\alpha_t\to0. 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 s<ts<t, the composed transition is Qs,t=(αˉt/αˉs)I+(1−αˉt/αˉs)UQ_{s,t}=(\bar\alpha_t/\bar\alpha_s)I+(1-\bar\alpha_t/\bar\alpha_s)U. The corresponding posterior is q(Es,p=b∣Et,p=c,E0,p=a)=[Qˉs]ab×[Qs,t]bc[Qˉt]ac.q(E_{s,p}=b \mid E_{t,p}=c,E_{0,p}=a)=\frac{[\bar Q_s]_{ab}\times [Q_{s,t}]_{bc}}{[\bar Q_t]_{ac}}.

This is normalized because QˉsQs,t=Qˉt\bar Q_s Q_{s,t}=\bar Q_t (for positive-probability conditioning events and αˉs>0\bar\alpha_s>0). 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.

Reviewer_gvMnOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes DiffTP, a graph diffusion framework for the job shop scheduling problem (JSSP). Its central idea is to represent machine sequences using transitive precedence heatmaps rather than only consecutive-operation relations. The method employs a Graph Transformer that alternates message passing over job and machine relations, uses categorical diffusion with self-conditioning to predict precedence heatmaps, and applies a heatmap-guided Giffler–Thompson (GT) decoder to construct feasible schedules. Multiple candidates are generated, and the schedule with the smallest makespan is selected. The authors evaluate DiffTP on synthetic training datasets and standard Taillard (TA), Demirkol (DMU), and Lawrence (LA) benchmarks. The reported results show competitive solution quality among constructive methods, and the ablation studies suggest that transitive precedence modeling, the Graph Transformer, self-conditioning, and GT decoding all contribute to performance. The main limitations are the computational cost of multi-step diffusion, incomplete isolation of the effect of transitive supervision from decoder compatibility, and limited evidence concerning training-seed robustness and performance under matched wall-clock budgets.

Critical strengths
  1. The paper identifies an important distinction between routing and scheduling: consecutive machine relations do not explicitly supervise the full pairwise precedence structure of a schedule. Representing machine sequences through transitive precedence heatmaps is a plausible approach to providing denser supervision for diffusion models. The small-scale representation study offers initial evidence supporting this design choice.

  2. The paper evaluates DiffTP on several established JSSP benchmarks and includes ablations of the representation, network architecture, self-conditioning, and decoding strategy. It also reports inference-time measurements and scaling results. These experiments provide useful evidence about the behavior of the overall method and make the computational trade-offs more visible than solution-quality results alone would.

Critical weaknesses
  1. The benefit of transitive precedence is not fully isolated from representation–decoder compatibility. The main ablation replaces transitive machine-precedence targets with consecutive-successor targets while retaining GT decoding. Since GT is designed to exploit pairwise precedence preferences, this change may disadvantage the consecutive-relation representation independently of its supervision quality. The authors acknowledge this limitation. Although the small-scale experiments provide additional evidence, stronger controlled comparisons with representation-appropriate decoders and matched training protocols are needed to establish how much of the improvement is attributable specifically to transitive supervision.

  2. The solution-quality comparisons do not establish competitive performance under matched computational budgets. With K = 32 and S = 50, DiffTP reports an average runtime of approximately 21.2 seconds per instance across the evaluated sizes, compared with 1.55 seconds for SLIM and 1.32 seconds for BOPO using 512 candidates, according to Appendix G. These results show that DiffTP can be effective despite using fewer candidates, but they do not establish an advantage under equal wall-clock budgets. Runtime also grows substantially with problem size, reaching approximately 120 seconds per instance for 100 × 20. Time-budgeted comparisons and anytime performance curves would better characterize its practical value.

  3. Robustness and statistical evidence are limited. The main experiments use a fixed random seed, and the paper does not establish that the reported improvements are robust across independent training runs. Instance-level standard deviations do not quantify variation across training seeds. Moreover, DiffTP is not the strongest constructive method on every reported benchmark size. Multiple training seeds, paired instance-level comparisons, and confidence intervals would make the empirical claims more reliable.

Questions for authors
  1. Can the authors provide a controlled comparison that isolates the effect of transitive precedence supervision from decoder compatibility? In particular, how does the consecutive-successor model perform with an appropriately matched decoder under the same training data, optimization budget, candidate count, and evaluation protocol?

  2. How does DiffTP compare with SLIM and BOPO under equal wall-clock inference budgets? Could the authors provide anytime solution-quality curves and clarify which preprocessing, model inference, decoding, and candidate-selection costs are included for every method?

  3. Are the main improvements consistent across independent training seeds? Could the authors report results from multiple independently trained models, together with paired comparisons and confidence intervals on the same test instances?

  4. How sensitive is DiffTP to the number of reverse diffusion evaluations S and the candidate budget K at a fixed inference-time budget? In particular, can fewer denoising evaluations or adaptive candidate allocation preserve solution quality on larger instances?

4 comments
AuthorsOpenReview ↗

isolation of representation–decoder compatibility

Thank you for your valuable feedback.

W1 & Q1: We thank the reviewer for this suggestion. Following the reviewer's suggestions, we conducted four controlled experiments with representation-appropriate decoders, to examine whether the benefit of transitive precedence persists beyond compatibility with GT. The transitive-precedence variants achieve consistent lower gaps on both TA and DMU.

Specifically, consecutive-successor targets use path merging, while transitive-precedence targets use Borda; both are followed by the same schedule evaluator/repair. We follow the original staged training path, with common prescribed datasets, backbone, objective and optimizer settings. Training uses seed 12345; testing uses seeds 12345/23456/34567 at K=32/S=50 on TA and DMU (80 instances each). The four configurations and results are:

GroupJob graphMachine targetDecoderTA gap (%)DMU gap (%)
AAdjacent arcsConsecutive successorPath merging231.904 ± 1.893289.508 ± 2.385
BAdjacent arcsTransitive precedenceBorda16.584 ± 0.05129.991 ± 0.197
CTransitive closureConsecutive successorPath merging191.896 ± 0.874200.854 ± 1.116
DTransitive closureTransitive precedenceBorda6.237 ± 0.05215.261 ± 0.103

Here ± is the sample SD of three evaluation-seed dataset means. These results show that the benefit of transitive precedence persists without GT and with target-specific decoding, as our group D still shows robost results on both TA and DMU benchmarks. We revised our paper and present detailed performance across each shape in Appendix I, and our transitive design D outperforms other assets consistently. Thus, the observed advantage of the transitive design is not merely a consequence of compatibility with GT.

AuthorsOpenReview ↗

wall-clock comparison

W2 & Q2: We thank the reviewer for this suggestion. Following the reviewer's suggestions, we added equal-time evaluations and anytime curves on all 80 TA and 80 DMU instances, using three evaluation seeds. Under the time-budgeted inference protocol described below, DiffTP achieves lower dataset-average gaps than the tested SLIM/BOPO configurations.

We test performances of each method on a single RTX 4090 GPU with evaluation seeds 12345/23456/34567 and a maximum budget of 120 seconds per instance. Under the budget, we sample a fixed batch solutions each time and change the sampling seed to resample until the time budget is exhausted, retaining the best solution found. As DiffTP samples slower, we retain the intermediate predicted heatmap during the denoising process to obtain anytime results.

For SLIM and BOPO, we evaluate three sampling-batch settings: 512, 1024 and 2048, to examine whether larger batches improve their equal-time performance. DiffTP uses a fixed logical batch of 32 trajectories and S=50. At 120s, mean gap (%) ± sample SD across the three evaluation-run means is:

Method / sampling batchTA gap (%)DMU gap (%)Overall gap (%)
SLIM (512)5.688 ± 0.02210.956 ± 0.0228.322 ± 0.016
SLIM (1024)5.546 ± 0.04010.770 ± 0.0908.158 ± 0.064
SLIM (2048)5.507 ± 0.03710.729 ± 0.0238.118 ± 0.010
BOPO (512)5.618 ± 0.04410.897 ± 0.0418.258 ± 0.002
BOPO (1024)5.386 ± 0.04310.627 ± 0.0178.006 ± 0.029
BOPO (2048)5.250 ± 0.04210.470 ± 0.0357.860 ± 0.027
DiffTP (32)3.942 ± 0.01310.060 ± 0.0247.001 ± 0.018

We select {30, 60, 120} seconds as reporting times, at which all configurations cover every instance. Each entry is the mean TA / DMU gap (%) over the three evaluation seeds.

Method / sampling batch30s: TA / DMU60s: TA / DMU120s: TA / DMU
SLIM (512)6.181 / 11.5465.944 / 11.2635.688 / 10.956
SLIM (1024)6.028 / 11.3175.827 / 11.0875.546 / 10.770
SLIM (2048)5.947 / 11.3025.719 / 10.9885.507 / 10.729
BOPO (512)6.082 / 11.3875.864 / 11.1115.618 / 10.897
BOPO (1024)5.821 / 11.1195.608 / 10.8475.386 / 10.627
BOPO (2048)5.643 / 10.9205.441 / 10.6775.250 / 10.470
DiffTP (32)4.675 / 10.6394.250 / 10.3023.942 / 10.060

We also report the runtime breakdown averaged over 160 instances evaluation below, including preprocessing, model inference, decoding and candidate selection:

Method / sampling batchPreprocessingModel inferenceDecodingCandidate selection
SLIM (512)0.094120.755——
SLIM (1024)0.086120.937——
SLIM (2048)0.088122.165——
BOPO (512)0.093120.585——
BOPO (1024)0.086120.590——
BOPO (2048)0.087120.646——
DiffTP (32)0.025116.0024.140—

Preprocessing includes data transfer. For SLIM/BOPO, the recorded inference time includes the native autoregressive construction and cost evaluation. For DiffTP, inference includes diffusion updates, and decoding includes GT recovery and makespan evaluation. Candidate selection is included in end-to-end timing but not separately measured, as its overhead averages less than 0.02s per instance for every configuration.

DiffTP has the lowest TA and DMU mean gaps among the tested configurations at 30, 60 and 120s. At 120s, its improvements over BOPO-2048 are 1.308 and 0.410 percentage points, respectively. These results demonstrate competitive performance under the reported time budgets. We revised our paper and added Appendix J/K to report per-size anytime curves and tables.

AuthorsOpenReview ↗

multi-seed experiments and stastical analysis

W3 and Q3: We thank the reviewer for this suggestion. Following the reviewer's suggestions, we added two independently trained models, repeated sampling evaluations and paired instance-level confidence intervals. All three available DiffTP models achieve lower TA and DMU mean gaps than both baselines under the paper's fixed-candidate protocol.

The original model uses training seed 12345, and the two additional models use 23456 and 34567. Each model and baseline is evaluated with seeds 12345/23456/34567 on the same 160 instances, using K=32/S=50 for DiffTP and K=512 for the baselines:

Training seed / methodTA gap (%)DMU gap (%)
DiffTP 123455.174 ± 0.06311.917 ± 0.107
DiffTP 234565.450 ± 0.02911.687 ± 0.067
DiffTP 345675.510 ± 0.04812.528 ± 0.037
SLIM7.676 ± 0.04113.244 ± 0.082
BOPO7.425 ± 0.08813.117 ± 0.062

Here ± is the sample SD of three evaluation-seed dataset means for a fixed model. Across the three observed models, the mean gaps range from 5.174% to 5.510% on TA and 11.687% to 12.528% on DMU.

For each model and baseline, we average the three evaluation seeds per instance and bootstrap paired instances within each shape 10,000 times. The mean DiffTP-minus-baseline gap differences and 95% confidence intervals (percentage points) are:

DatasetTraining seedDiffTP − SLIM [95% CI]DiffTP − BOPO [95% CI]
TA12345−2.502 [−2.782, −2.222]−2.251 [−2.496, −2.007]
TA23456−2.226 [−2.501, −1.952]−1.975 [−2.211, −1.746]
TA34567−2.166 [−2.440, −1.892]−1.914 [−2.145, −1.690]
DMU12345−1.327 [−1.761, −0.886]−1.200 [−1.662, −0.741]
DMU23456−1.557 [−1.943, −1.175]−1.431 [−1.840, −1.029]
DMU34567−0.716 [−1.176, −0.259]−0.589 [−1.072, −0.101]

All intervals are below zero, supporting a lower mean gap for each observed DiffTP model on these benchmarks. These intervals quantify paired instance variation conditional on the trained models. Appendix K reports paired instance-level statistical comparisons and confidence interval

AuthorsOpenReview ↗

sensitivity of DiffTP

Q4: We thank the reviewer for this question. We added an evaluation varying S and allocating K under the same per-shape time budget, and the results show that choosing too few denoising evaluations markedly degrades performance. This trend also holds on the examined large instances.

We set a range of S={1,10,20,30,50,100}, and fixing time-budget 10s for 15×15, 20×15, 20×20 and 30×15; 30s for 30×20, 40×15, 40×20, 50×15 and 50×20; and 120s for 100×20. For each shape and S, K is calibrated first according to the time-budget. The results are as follows:

SMean completed KTA gap (%)DMU gap (%)Overall gap (%)
1783.0412.56922.08317.326
10222.976.70114.30710.504
20124.505.47312.3388.906
3085.685.15711.8158.486
5053.114.94911.6948.321
10026.355.02011.5978.308

Across S=30/50/100, the overall mean gap varies only from 8.308% to 8.486% (a 0.178-percentage-point range), despite mean completed K ranging from 26.35 to 85.68. By contrast, reducing S to 10 or 1 raises the gap to 10.504% or 17.326%, respectively, even with more candidates.

We further report the results on larger instances below. Each cell reports the mean gap (%) / mean number of completed candidates.

DatasetShapeBudgetS=1S=10S=20S=30S=50S=100
TA50×1530 s11.973 / 5795.960 / 1684.747 / 954.573 / 664.323 / 414.260 / 21
TA50×2030 s13.585 / 4357.672 / 1246.294 / 695.694 / 475.404 / 295.362 / 15
TA100×20120 s7.646 / 4564.967 / 1324.378 / 744.268 / 513.804 / 313.967 / 16
DMU50×1530 s19.096 / 57912.890 / 16811.758 / 9511.340 / 6611.285 / 4111.486 / 21
DMU50×2030 s27.046 / 43518.564 / 12416.716 / 6915.753 / 4715.838 / 2915.477 / 15

Thus in large instances, we could still maintain a stable performance under fixed-budget runtime.

Comments on the paper

4 comments

Thank you for your valuable feedback.

W1: We thank the reviewer for this observation. To better understand the contribution of transitive representation to our full design, we added controls examining job and machine relations alongside decoder choice.

The four groups use target-specific decoders for both checkpoint selection and testing: path merging for consecutive-successor targets and Borda for transitive-precedence targets, without GT. All follow the same staged training protocol with training seed 12345 and evaluation seeds 12345/23456/34567 at K=32/S=50.

GroupJob graphMachine targetDecoderTA gap (%)DMU gap (%)
AAdjacent arcsConsecutive successorPath merging231.904 ± 1.893289.508 ± 2.385
BAdjacent arcsTransitive precedenceBorda16.584 ± 0.05129.991 ± 0.197
CTransitive closureConsecutive successorPath merging191.896 ± 0.874200.854 ± 1.116
DTransitive closureTransitive precedenceBorda6.237 ± 0.05215.261 ± 0.103

Here ± denotes the sample SD across the three evaluation-seed dataset means. The transitive machine-target configurations B/D outperform A/C with their respective decoders. B→D further shows the benefit of job closure while holding the machine target and decoder fixed.

We also evaluated the same A checkpoints with GT, changing only the test decoder:

ConfigurationDecoderTA gap (%)DMU gap (%)
A: adjacent job / consecutive machinePath merging231.904289.508
A: adjacent job / consecutive machineGT28.63938.006
D: transitive job / transitive machineBorda6.23715.261

GT substantially improves A, but D remains better even without GT. These results support transitive representation as a key component of our full design.

W2 & Q1: We added shared-time evaluations, two independent retrainings to test DiffTP stability and updated our supplementary materials to provide detailed configuration assets.

To assess performance under a shared elapsed-time budget, we evaluate all 80 TA and 80 DMU instances on RTX 4090 GPUs with sampling seeds 12345/23456/34567 and a maximum budget of 120 seconds per instance. BOPO repeatedly samples batches with new sampling seeds and retains the best solution found. We evaluate sampling-batch settings of 512, 1024 and 2048. DiffTP uses a logical batch of 32 trajectories with S=50; to obtain anytime results, we also decode and retain intermediate clean-heatmap predictions from the same trained model.

At 120 seconds, the mean gaps (%) are:

Method / sampling batchTA gap (%)DMU gap (%)Overall gap (%)
BOPO (512)5.618 ± 0.04410.897 ± 0.0418.258 ± 0.002
BOPO (1024)5.386 ± 0.04310.627 ± 0.0178.006 ± 0.029
BOPO (2048)5.250 ± 0.04210.470 ± 0.0357.860 ± 0.027
DiffTP (32)3.942 ± 0.01310.060 ± 0.0247.001 ± 0.018

DiffTP achieves lower TA and DMU mean gaps under this time-budgeted protocol. We updated our Appendix J and included per-size anytime curves and runtime breakdowns.

To assess training stability, we additionally trained DiffTP with seeds 23456 and 34567. We evaluate the original model and both retrainings on the same 160 instances with sampling seeds 12345/23456/34567, with K=32/S=50 for DiffTP and K=512 for BOPO:

Training seed / methodTA gap (%)DMU gap (%)
DiffTP 123455.174 ± 0.06311.917 ± 0.107
DiffTP 234565.450 ± 0.02911.687 ± 0.067
DiffTP 345675.510 ± 0.04812.528 ± 0.037
BOPO7.425 ± 0.08813.117 ± 0.062

In both tables, ± denotes the sample SD across three evaluation-seed dataset means. All three DiffTP models retain lower dataset-average gaps than BOPO. This demostrate that our design and experiment results are stable. To facilitate independent reproduction, We provide detailed experimental configurations, per-instance evaluation results, ablation assets and inference checkpoints for the original models in supplementary materials. The training datasets are planned for release upon acceptance.

On the same hardware RTX 4090 GPUs, we added shared end-to-end time comparisons between DiffTP and BOPO, using three evaluation seeds. The mean TA / DMU gaps (%) are:

Method / sampling batch30 s: TA / DMU60 s: TA / DMU120 s: TA / DMU
BOPO (512)6.082 / 11.3875.864 / 11.1115.618 / 10.897
BOPO (1024)5.821 / 11.1195.608 / 10.8475.386 / 10.627
BOPO (2048)5.643 / 10.9205.441 / 10.6775.250 / 10.470
DiffTP (32, S=50)4.675 / 10.6394.250 / 10.3023.942 / 10.060

The result shows that increasing the timebudget demonstrates average better performance compared with BOPO.

Q2 : We thank the reviewer for this suggestion. We repeated group C with an additional training seed, 23456, and completed all TA/DMU evaluations. Its poor large-scale performance persists across the two training runs.

Both C models use job transitive closure, consecutive-successor machine targets, and path merging for validation-based checkpoint selection and testing, without GT. Each is evaluated on all 80 TA and 80 DMU instances using sampling seeds 12345/23456/34567, K=32 and S=50.

ConfigurationTraining seedTA gap (%)DMU gap (%)
C: successor / path merging12345191.896 ± 0.874200.854 ± 1.116
C: successor / path merging23456191.310 ± 1.683192.429 ± 4.031
D: transitive / Borda (reference)123456.237 ± 0.05215.261 ± 0.103

Here ± is the sample SD across the three evaluation-seed dataset means for each fixed trained model. The additional C run remains far worse than the transitive reference on both datasets, supporting that the observed failure is not specific to the original C training seed.

Dear Area Chair and Reviewers,

We sincerely thank the Area Chair for coordinating the review process and all reviewers for their careful evaluation and constructive feedback.

Our central contribution is a transitive-precedence representation for diffusion-based job shop scheduling. While graph diffusion for routing typically predicts connections between neighboring nodes, JSSP requires machine execution orders that jointly respect job precedence constraints. This motivates learning the broader ordering structure of a schedule, rather than supervising only adjacent-operation connections. DiffTP explicitly encodes these relations through transitive-precedence heatmaps and learns them with a job–machine Graph Transformer. Our experiments demonstrate the importance of this scheduling-oriented representation, with substantial improvements in solution quality and benefits compared with the-state-of-art work.

We appreciate that the reviewers recognized important aspects of this contribution:

  • Reviewer gvMn and hAdP recognized the distinction between routing and scheduling and identified the JSSP-specific representation as the key contribution enabling the transfer of graph diffusion from routing to scheduling.

  • Reviewer Z7wi recognized the substantial single-candidate improvements and the technical insight provided by structure-aware supervision.

The main concerns involved representation–decoder compatibility, performance under equal computational budgets, training robustness, and understanding what the network learns. In response, we added the following evidence:

  1. Representation-appropriate decoding controls. We independently varied job connectivity and machine targets, using path merging for neighboring-operation targets and Borda ranking for transitive targets, without GT. The fully transitive configuration achieves TA/DMU mean gaps of 6.24%/15.26%, supporting benefits beyond compatibility with GT. Comparisons under a common GT decoder also favor the transitive representation.

  2. Equal-time comparisons. We evaluated all 160 TA/DMU instances with three evaluation seeds and SLIM/BOPO sampling batches of 512, 1024, and 2048. For time-budgeted evaluation, DiffTP additionally retains decoded intermediate predictions from the same trained models. At 120 seconds, its TA/DMU gaps are 3.94%/10.06%, compared with 5.25%/10.47% for BOPO-2048, and we also provided detailed analysis on solution-quality curves and runtime breakdowns.

  3. Robustness and failure analysis. Two additional independent DiffTP training runs retain consistently lower dataset-average gaps than both baselines under the original final-only protocol, supported by paired instance-level confidence intervals. We also repeated the successor-target control with another training seed and supplemented the analysis with implementation checks, training curves, heatmaps, and pre-repair feasibility measurements. These results show that decreasing denoising loss can coexist with deteriorating global ordering consistency, helping explain the poor large-scale successor-target results.

The revised manuscript incorporates the key experimental additions and clarifies the diffusion formulation and evaluation protocols. We also acknowledge the remaining limitations: multi-step diffusion is computationally expensive, transitive predictions do not guarantee feasibility, and GT remains valuable when cross-size generalization produces conflicting orders.

Taken together, the additional evidence strengthens our central finding: the choice of what to represent and denoise is crucial when transferring graph diffusion to scheduling, and transitive precedence provides a useful, more robust ordering representation. We would be grateful if the Area Chair and reviewers could consider these additional findings and clarifications in assessing our contribution.

Thank you again for your time and consideration.

Sincerely,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.