acceptodds
Under review as a conference paper at ICLR 2027

Learning to Construct and Improve for Large-Scale Job Shop Scheduling via Deep Reinforcement Learning

Abstract

Learning-based Job Shop Scheduling Problem (JSSP) solvers have made substantial progress through graph representations, size-generalizable policies, and learned improvement. Yet learning directly on large scheduling instances remains challenging: the solver must represent complex precedence and resource dependencies over long horizons while efficiently allocating computation across large decision and search spaces. We study how to make large-scale JSSP instances first-class training states and propose Learning to Construct and Improve (L2CI), a deep reinforcement learning framework that jointly learns schedule construction and improvement at scale. For scalable representation learning, we develop a structure-aware self-attention Transformer that captures job and machine dependencies, while inducing-point compression provides fixed-size global representations. During construction, successor-state bounds supervise soft pruning of unpromising actions. After construction, an RL-guided critical-path search improves complete schedules and recycles improved solutions as demonstrations for the constructive policy. We train L2CI directly on instances with up to 12,000 operations and achieve strong performance on standard TAI and DMU benchmarks, with learned search further improving the constructed schedules.

Primary area:
reinforcement learning
Keywords:
Job Shop Scheduling, JSSP, Reinforcement Learning

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 3 reviews, above 27% of the others.
Reviewer_86TxOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes L2CI, a reinforcement learning framework for large-scale job shop scheduling that combines schedule construction with learned local improvement. It uses structure-aware attention and inducing-point compression for state representation, successor-state lower bounds to guide construction, and an RL policy to select critical-path N5 moves. Improved schedules are recycled as demonstrations for the constructor. Experiments report strong construction and improvement results on standard benchmarks, with training on up to 12,000 operations and construction evaluated on up to 25,000 operations.

Critical strengths

S1. The paper addresses the practically relevant challenge of learning directly on large scheduling instances and evaluates construction beyond the maximum training size.

S2. The framework connects structure-aware representation, constructive scheduling, and learned local search through a coherent feedback loop that reuses improved schedules as supervision.

S3. The reported results show substantial construction-quality gains and further improvements through learned search across several established benchmark families.

Critical weaknesses

W1. The admissibility of successor-state lower bounds does not establish their reliability for ranking actions, leaving the rationale for bound-based probability penalties insufficiently justified.

W2. The constructor directly optimizes initial makespan rather than makespan after budgeted improvement, creating a potential mismatch between its training objective and the complete solver’s objective.

W3. Restricting search to a selected critical path’s N5 neighborhood while rewarding only incumbent improvements may hinder exploration requiring multiple neutral or worsening moves.

W4. The substantial training investment and limited runtime and memory comparisons with learned baselines leave the framework’s computational efficiency and practical scalability insufficiently established.

W5. Missing matched traditional-search controls and incomplete reporting of reference alignment, distribution transfer, and statistical variability limit the conclusiveness of the empirical comparisons.

Questions for authors

Q1. What supports using relative successor-state lower bounds as a proxy for action quality when bound tightness can differ across successor states? Admissibility alone does not imply that a larger bound corresponds to a worse achievable schedule, and the learned predictor introduces additional error. Can the authors quantify ranking reliability and explain how misleading screening signals affect action selection?

Q2. Does any constructor update directly account for the final makespan obtained after the improvement budget is spent? A schedule with a better initial makespan may be less improvable than a worse initial schedule, so please explain how demonstration feedback addresses this distinction and aligns construction with the complete solver’s objective.

Q3. How does the improvement policy overcome exploration barriers introduced by the restricted neighborhood and incumbent-only rewards? The single-step dominance argument does not establish that excluded moves are unhelpful for longer search trajectories. Please clarify how the method handles multiple critical paths and extended sequences without incumbent improvement.

Q4. Appendix E.2 provides equal-time comparisons against CP-SAT, but comparisons with learned search baselines primarily use equal move budgets. Can the authors provide corresponding wall-clock comparisons, including initial construction, and report inference time and peak memory across instance sizes? Please also contextualize the training cost of 300 hours on eight RTX 4090 GPUs relative to the compared methods.

Q5. Can the authors compare learned N5 selection with traditional tabu search or simple N5 selection strategies under the same initialization and time budget? Although the paper states that references are shared within each comparison, please explain how published baseline results were aligned with the CP-SAT references.

8 comments

W1/Q1: Why use successor bounds for action ranking, and how are prediction errors and misleading penalties handled?

A1: Thank you for requesting a direct examination of this mechanism. Successor bounds encode how a decision changes machine availability, release times, and remaining resource constraints. Relative bounds compare these consequences within a state; centered regression and pairwise supervision teach the predictor these differences. To address your concerns, we test ranking against optimal completion quality, explain the bounded effect on action selection, and ablate soft pruning.

For the ranking test, we generate 100 fresh instances per size and sample states at 20%, 50%, and 80% construction progress. CP-SAT solves each action’s conditional completion problem under the fixed prefix and append-only rules. We evaluate the trained screening predictor on states for which every legal action has a proven optimum.

Table R1. Pairwise ranking accuracy against optimal completion quality.

SizeExact / sampled statesRaw bound (%)Screening predictor (%, 95% CI)
10×10300/30084.5777.03 [74.61, 79.34]
15×15285/30078.3578.71 [76.57, 80.77]
20×20203/30079.4279.33 [77.09, 81.46]

The predictor achieves 77.03%–79.33% pairwise accuracy, with all 95% confidence intervals (CI) above the 50% random-ordering baseline. Raw-bound accuracy tests tightness differences; predictor accuracy additionally incorporates prediction error. Thus, the ranking evidence comes from comparison with achievable quality, beyond admissibility alone. Appendix E.5 gives the tie handling and instance-cluster bootstrap protocol.

A misleading penalty can reduce a good action’s relative probability. Our tolerance region, smooth saturation, and 0.25 penalty cap limit that effect while retaining every legal action. Selection depends jointly on the actor scores and this adjustment; the change in any pair’s log probability ratio is bounded by 0.25 (Appendix E.5).

Finally, to test whether the guidance helps learning with these imperfections present, we retrain L2C with and without soft pruning under the same network, initialization settings, and training budget, then evaluate both with identical greedy decoding and references.

Table R2. Soft-pruning ablation: mean construction Gap (%) on TAI.

Configuration15×1520×1520×2030×1530×2050×1550×20100×20
L2C8.4810.2811.7612.3714.259.9111.457.22
w/o soft pruning9.9610.4714.0114.0816.0410.7711.696.95

Soft pruning improves construction Gap at seven of eight sizes; removing it increases mean Gap by 1.03 percentage points. Together, the exact-reference test supports ranking reliability on the verified states, and the retraining ablation confirms a useful learning contribution. These results support the intended role of the predictor as informative, bounded guidance for construction. Appendix E.4 provides the ablation details.

W2/Q2: How do constructor updates use final search outcomes when initial quality and improvability differ?

A2: Thank you for asking how the two learning objectives connect. Construction PPO optimizes initial makespan; our additional search-guided imitation update uses the best schedule retained after budgeted improvement. Topological linearization preserves its machine order and makespan, making it a feasible demonstration of how to construct the improved schedule directly.

A worse initial schedule can lead to a better final schedule under the same budget. Demonstration feedback accommodates this case because its target is the endpoint actually found: a better endpoint from a worse start provides a better demonstration. Initial and final quality rankings therefore need not agree. This connection is implemented through imitation, while the original construction PPO return remains unchanged.

Furthermore, the improver trains on initial schedules generated by constructor weights from different training stages, exposing it to changing quality and structure. The two designs complement one another: diverse starts prepare the improver for the evolving constructor, and retained search outcomes guide subsequent construction learning. Thus, search-discovered quality enters the constructor’s learning target even when the initial makespan does not reflect a schedule’s improvement potential.

W3/Q3: How does N5 search traverse neutral or worsening moves and handle multiple critical paths?

A3: Thank you for asking how these mechanisms support multi-step exploration. We distinguish the executed search trajectory from the best schedule retained. A feasible move can be executed even when it leaves makespan unchanged or increases it; the best solution is preserved separately. Consecutive zero rewards do not terminate search while budget and candidates remain.

Theorem 2 explains how learning evaluates such trajectories. With discount 1, cumulative reward equals normalized improvement in the final retained schedule:

∑k=0kend−1rki=C(I,σ0)−C(I,σ+)LI(0).\sum_{k=0}^{k_{\mathrm{end}}-1} r_k^{\mathrm{i}} = \frac{C(I,\sigma_0)-C(I,\sigma^+)}{L_I^{(0)}}.

Advantage estimates incorporate subsequent returns, so a zero-immediate-reward move can receive credit through later improvement. The objective therefore concerns the outcome of the sequence.

For multiple critical paths, the policy encodes the full schedule graph and recomputes the selected critical path and N5 candidates after each move. The selected path can change; modifying one of several critical paths may initially leave makespan unchanged, and that move remains executable.

The classical critical-block argument [1] supplies a one-step basis for N5 candidates; it does not determine excluded moves’ long-term utility. Within this neighborhood, executable neutral/worsening moves, subsequent-return learning, and dynamic candidate updates jointly support multi-step exploration. Immediate improvement is therefore not required at every step.

References

  • [1] E. Nowicki and C. Smutnicki. A Fast Taboo Search Algorithm for the Job Shop Problem. Management Science, 1996.
Reviewer_aH1WOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Learning to Construct and Improve (L2CI), a reinforcements-learning framework for large-scale job-shop scheduling. A constructive policy builds machine orderings using a structure-aware Transformer, while inducing-point attention compresses the state representation for value estimation. Successor-state lower bounds supervise a learned screening function that adjusts construction probabilities. Experiments demonstrate the effectiveness of the proposed method.

Critical strengths
  • The construction-improvement loop is coherent and practically motivated. Construction provides an initial solution, learned N5 search improves it, and the resulting machine ordering supplies additional supervision for construction. Topological reconstruction handles the fact that several dispatch sequences can represent the same schedule.
  • The reported solution-quality gains are substantial across multiple benchmarks.
  • The reward design and feasibility treatment are carefully specified. The incumbent-based improvement reward telescopes to the improvement in the returned schedule, while the construction shaping term preserves the makespan objective when its terminal value is zero. The screening bound is supported by a reasonable admissibility argument, and finite screening penalties retain every legal construction action. These choices make the optimization objectives and the limitations of screening relatively transparent.
Critical weaknesses
  • The paper lacks the component ablations needed to establish its methodological contributions. In particular, an admissible lower bound does not imply that ordering actions by their bounds orders their achievable final makespans, so the usefulness of the learned penalty needs empirical validation.
  • The motivation for direct large-scale training is not sufficiently established by the scale-reversal argument. Increasing instance size does not change the underlying JSSP objective or constraints, and a size-generalizable policy can learn reusable scheduling principles while adapting its decisions to the full input. Theorem 1 correctly shows that extending an instance can reverse the optimal action, but the input state also changes: the same policy can select different actions in the original and extended instances. A reversal of the optimal action therefore does not establish a limitation of small-scale-trained policies or imply that large-scale training is necessary, as suggested in the conclusion. Larger instances may introduce harder dependencies or distribution shifts, but these possibilities require empirical investigation.
  • The baseline coverage and comparison budgets leave uncertainty about the claimed state of the art. Relevant recent methods such as BOPO and COMPASS are absent, and the evaluation does not include a strong conventional N5/tabu-search baseline.
  • The scalability contribution needs a more complete computational analysis. Training the constructor takes 300 hours on eight RTX 4090 GPUs, approximately 2,400 GPU-hours. This cost is not inherently unacceptable, but its relationship to baseline training costs and deployment savings is unclear.
Questions for authors

Please refer to the weaknesses.

7 comments

W1: Are the components useful, and do successor bounds reliably rank achievable completion quality?

A1: Thank you for requesting empirical support. Successor bounds encode changes in machine availability, release times, and remaining workload. To test whether this information provides useful guidance, we examine component learning benefits and action-ranking accuracy.

First, we retrain L2C and variants removing soft pruning or demonstration recycling under the same network, initialization settings, and training budget. Greedy decoding and TAI references are shared; results measure construction alone.

Table R1. Component ablations: mean construction Gap (%) on TAI.

Configuration15×1520×1520×2030×1530×2050×1550×20100×20
L2C8.4810.2811.7612.3714.259.9111.457.22
w/o soft pruning9.9610.4714.0114.0816.0410.7711.696.95
w/o recycling11.6812.5412.1214.2117.4811.5111.857.16

L2C leads at seven of eight sizes. Removing soft pruning or recycling increases mean Gap by 1.03 or 1.60 percentage points, respectively, showing that both contribute before test-time search.

Second, we compare raw bounds and the learned predictor against CP-SAT-certified conditional optimal makespans under fixed prefixes and append-only rules. This test uses states for which every legal action has a proven optimum.

Table R2. Pairwise ranking accuracy against optimal completion quality.

SizeExact / sampled statesRaw bound (%)Screening predictor (%, 95% CI)
10×10300/30084.5777.03 [74.61, 79.34]
15×15285/30078.3578.71 [76.57, 80.77]
20×20203/30079.4279.33 [77.09, 81.46]

The predictor achieves 77.03%–79.33% pairwise accuracy, with all 95% confidence intervals (CI) above the 50% random-ordering baseline. This test includes both bound-tightness differences and prediction error. A tolerance region, smooth saturation, and a 0.25 penalty cap further limit the probability adjustment while retaining all legal actions. Together, the ranking test supports the signal’s reliability on verified states, and the ablations establish its learning benefit. Appendices E.4–E.5 provide details.

W2: What does Theorem 1 imply for state-adaptive policies and the motivation for large-scale training?

A2: Thank you for asking us to clarify the connection between Theorem 1 and our training design. Small-scale learning and exposure to larger scheduling states play complementary roles in our curriculum. As Section 3.2 notes, useful inductive biases may support extrapolation. Theorem 1 identifies a concrete dependency that optimal decisions must accommodate: while preserving the original operations and construction prefix, instance extension can reverse the optimal decision for the same machine conflict, even with optimal subsequent choices.

Our curriculum builds on small-scale learning by progressively exposing the policy to more diverse scheduling states and direct feedback on their decisions. This provides a training mechanism for learning how additional dependencies affect construction quality. The theorem supplies the structural motivation for this mechanism, whose practical value we assess empirically.

Appendix E.1 tracks learning through the curriculum with unchanged architecture and greedy decoding on the same eight-size TAI panel. Mean Gap decreases from 12.14% to 5.94%, a 51.1% reduction, with improvements at all eight sizes. Appendix E.3 further shows L2C leading at all 16 TAI/DMU sizes and L2CI at all eight synthetic sizes, up to 25,000 operations. These results demonstrate the learning progress and large-scale performance achieved by our framework.

W3 (1/2): How do BOPO and COMPASS compare across benchmark sizes?

A3 (1/2): Thank you for suggesting these baselines. We add BOPO [1] and COMPASS [2], and compare their mean Gap and runtime with L2C across the 16 TAI/DMU sizes in Appendix E.3 using common per-instance references.

Table R3(a). Mean Gap (%) and time (s): TAI.

Method15×15 Gap15×15 Time20×15 Gap20×15 Time20×20 Gap20×20 Time30×15 Gap30×15 Time30×20 Gap30×20 Time50×15 Gap50×15 Time50×20 Gap50×20 Time100×20 Gap100×20 Time
BOPO13.510.1914.260.2815.130.3716.660.4817.220.639.811.0011.771.324.933.98
COMPASS-16009.1933.5112.8443.3812.4955.4614.4265.7116.8286.669.69129.4711.42152.404.19432.06
L2C6.270.326.320.408.100.596.040.657.610.920.561.192.062.220.257.24

Table R3(b). Mean Gap (%) and time (s): DMU.

Method20×15 Gap20×15 Time20×20 Gap20×20 Time30×15 Gap30×15 Time30×20 Gap30×20 Time40×15 Gap40×15 Time40×20 Gap40×20 Time50×15 Gap50×15 Time50×20 Gap50×20 Time
BOPO17.460.2920.290.3819.190.4725.710.6416.000.7222.450.9614.541.0025.351.33
COMPASS-160015.9899.8515.54124.3718.46150.9219.38197.3614.56205.4617.91259.1012.57293.8717.49364.30
L2C9.370.399.610.568.360.6411.340.937.720.9410.931.296.891.188.802.22

L2C achieves lower Gaps than both added baselines at all 16 sizes, using one construction, versus COMPASS’s 1,600 trajectories. Appendix E.3 provides the complete baseline comparison.

References

  • [1] Z. Liao et al. BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization. ICML 2025.
  • [2] F. Chalumeau et al. Combinatorial Optimization with Policy Adaptation using Latent Space Search. NeurIPS 2023.
Reviewer_P75JOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a deep reinforcement learning framework (L2CI) for large-scale JSSP, combining constructive policy with RL-guided local search and demonstration recylling to iterativeley improve scheduling solutions. The proposed method is evaluated on established JSSP benchmarks, including classical heuristics and learning based construction and improvement methods. The results demonstrate strong solution quality, successfully training on instances with up to 12000 operations, with generalization to instances with up to 25000 operations without fine-tuning.

Critical strengths

The large-scale applicability is practically relevant, with meaningful empirical evidence demonstrating the strong performance of the proposed constructive policy on large-scale JSSP instances.

Critical weaknesses

The omission of Residual Scheduling (Ho et al., 2024) is concerning, as this method also employs a residual-state representation and demonstrates competitive performance on large JSSP instances. Given the conceptual similarity, its absence makes it difficult to assess the improvements of the proposed constructive policy over closely related prior work.

Literature: Ho, Kuo-Hao & Cheng, Jui-Yu & Wu, Ji-Han & Chiang, Fan & Chen, Yen-Chi & Wu, Yuan-Yu & Wu, I-Chen. (2024). Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem. IEEE Access. 12. 14703-14718. 10.1109/ACCESS.2024.3357969.

Questions for authors
  1. While the experiments demonstrate the effectiveness of the constructive policy, the contributions of individual mechanisms remain unclear. In particular, could the authors evaluate L2C with and without bound-supervised soft pruning to substantiate its claimed benefit for large-scale exploration? Similarly, an ablation of demonstration recycling would help clarify its contribution beyond the combination of construction and improvement policies.

  2. A central contribution of the paper is enabling direct training on large-scale JSSP instances. However, the computational efficiency during inference remains unclear. While Appendix E.2 shows that L2CI outperforms CP-SAT under 30- and 60-minute time budgets, the wall-clock time required for a single greedy construction is not reported. Could the authors provide construction inference times and total solving times across different instance sizes? Furthermore, how do the runtimes of L2CI, L2S, and TBGAT compare under the matched N5-move budgets in Table 2, given that equal move budgets do not necessarily imply comparable computational costs?

  3. Could the authors further justify their selection of constructive baselines? For instance, Ho et al. (2024) propose a residual scheduling approach with strong performance on large JSSP instances, yet this method is not included. In contrast, ReSched primarily targets FJSP, and its authors acknowledge limitations on JSSP benchmarks. Furthermore, SLIM proposes a self-labeling training strategy evaluated with a pointer network, raising the question of how it would perform with a comparably scaled architecture. This is particularly relevant given the substantial differences in training budgets (120 hours on one RTX 3090 for SLIM versus 300 hours on eight RTX 4090 GPUs for L2CI). To what extent might these differences in architecture and computational resources account for the reported performance improvements?

4 comments

As no rebuttal has been submitted by the authors, I stay with my initial assessment.

We sincerely apologize for the delayed response. We have prepared point-by-point replies to your three questions, supported by additional experiments and clarifications. We would appreciate your reconsideration in light of this evidence.

Q1: What do soft pruning and demonstration recycling contribute to construction learning?

A1: Thank you for requesting these ablations. Soft pruning guides construction decisions using successor-state information, while demonstration recycling teaches the constructor from schedules improved by search. To test their individual contributions, we retrain L2C and two variants, removing one component at a time, with the same network, initialization settings, and training budget. All use the same greedy decoding and TAI references; the evaluation measures construction alone.

Table R1. Component ablations: mean construction Gap (%) on TAI.

Configuration15×1520×1520×2030×1530×2050×1550×20100×20
L2C8.4810.2811.7612.3714.259.9111.457.22
w/o soft pruning9.9610.4714.0114.0816.0410.7711.696.95
w/o recycling11.6812.5412.1214.2117.4811.5111.857.16

L2C achieves the lowest Gap at seven of eight sizes. Removing soft pruning increases the eight-size mean Gap by 1.03 percentage points, and removing recycling increases it by 1.60 points. Crucially, these gains arise before any test-time improvement: recycling improves what the constructor learns, beyond simply combining construction and search at inference. The ablations therefore support the usefulness of both components for construction learning. Appendix E.4 provides the protocol and results.

Q2: How much time do construction and complete solving take across sizes and move budgets?

A2: Thank you for requesting these timings. To distinguish move counts from computational cost, Appendix E.3 reports separate construction times and pairs Gap with total runtime for cached L2CI at all four budgets. The following tables cover all 13 sizes at 5,000 steps, with RS construction times also included.

Table R2(a). Mean construction and solving time (s): all eight TAI sizes.

Timing15×1520×1520×2030×1530×2050×1550×20100×20
RS construction0.130.230.260.490.601.231.605.37
L2CI construction stage0.080.090.160.140.260.280.551.64
L2CI total8.309.1212.479.6316.252.2514.995.29
L2S total132.60151.20168.99179.48204.43257.28294.33589.43
TBGAT† reported time126.00138.00162.00162.00174.00234.00234.00402.00

Table R2(b). Mean construction and solving time (s): SWV, ORB, and YN.

TimingSWV 20×10SWV 20×15SWV 50×10ORB 10×10YN 20×20
L2CI construction stage0.070.110.160.050.16
L2CI total7.069.865.997.2012.64
L2S total149.88175.35263.58103.48160.07
TBGAT† reported time150.00162.00294.00102.00138.00

On TAI 100×20, L2CI construction takes only 1.64 s; initialization and improvement add 3.65 s, giving 5.29 s in total. Total time includes construction, environment initialization, improvement, and synchronization. Our neural evaluations use a single RTX 4090 GPU; TBGAT’s published times [1] are provided for reference because pretrained weights are unavailable. Appendix E.3 gives further construction timings, and the 30/60-minute budgets in Appendix E.2 also include construction.

Across all 52 size–budget comparisons, L2CI achieves both lower Gaps and shorter times than L2S. Thus, the quality advantage is accompanied by a runtime advantage even after accounting for construction, rather than relying on equal move counts alone.

References

  • [1] C. Zhang et al. Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problem. UAI 2024.

W1/Q3: Why these baselines, how does L2CI compare with RS, and what is the role of architecture and training?

A3: Thank you for highlighting RS and asking about the basis of comparison. Our expanded baselines cover residual-state modeling, graph/Transformer architectures, self-generated supervision, and latent-space search. ReSched [1] uses the released JSSP-specific model; SLIM [2] provides a self-labeling comparison. Section 4.1 now explains the selection rationale and the connection to RS.

To assess the closest residual-state baseline directly, we added RS [3] across all 16 TAI/DMU sizes and eight synthetic sizes. Table R3 uses common per-instance references.

Table R3(a). Mean construction Gap (%): all eight TAI sizes.

Method15×1520×1520×2030×1530×2050×1550×20100×20
RS13.8018.0016.5917.3318.188.4611.434.08
L2C6.276.328.106.047.610.562.060.25

Table R3(b). Mean construction Gap (%): all eight DMU sizes.

Method20×1520×2030×1530×2040×1540×2050×1550×20
RS19.6918.9120.6622.2016.4319.3913.6420.25
L2C9.379.618.3611.347.7210.936.898.80

L2C outperforms RS at all 16 sizes, reducing average Gap by 8.83/9.77 percentage points on TAI/DMU. These results establish the construction advantage over this closely related method.

For SLIM, the released model cannot determine how a capacity-matched version would perform or separate architecture from training compute. Our distinct learning mechanism recycles schedules retained after budgeted N5 improvement as construction demonstrations. Together with structure-aware attention and inducing-point compression, it supports direct training on up to 12,000 operations, compared with 400 in SLIM’s reported model.

We further evaluate whether the complete design translates into useful large-instance performance. Table R4 includes L2CI because it adds 5,000 improvement steps to the same schedules produced by cached L2C, with construction included in total time. All methods use the same paired references.

Table R4(a). Mean Gap (%) on all eight large-instance sizes (L2CI: 5,000 steps).

Method100×20100×40100×100150×100200×20200×50400×30500×50
RS1.522.123.48-2.730.10-3.11-0.53-2.27
L2C0.19-2.152.45-3.060.76-2.320.04-0.76
L2CI0.00-3.912.14-3.370.00-4.85-0.72-2.47

Table R4(b). Mean time (s) on all eight large-instance sizes (L2CI: 5,000 steps).

Method100×20100×40100×100150×100200×20200×50400×30500×50
RS8.2720.0761.45223.7531.52187.05352.451622.18
L2C0.832.9524.7560.172.6620.2626.95154.52
L2CI1.6171.80190.90320.563.43182.9660.40465.87

L2CI achieves the best quality at all eight sizes. On all four sizes with at least 200 jobs, it reverses RS’s construction-quality lead while still taking less total time. At 25,000 operations, it improves on the strongest quality baseline, RS, and is 3.48× faster. This demonstrates the value of learning construction and improvement together: the complete solver delivers a stronger quality–time balance on these large instances. Appendix E.3 provides the full comparison.

References

  • [1] X. Xiao et al. RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States. ICLR 2026.
  • [2] A. Corsini et al. Self-Labeling the Job Shop Scheduling Problem. NeurIPS 2024.
  • [3] K. H. Ho et al. Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem. IEEE Access, 2024.

Comments on the paper

1 comment

Reviewers, the authors have provided the rebuttal, please respond to them if you have not done so. Thanks.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.