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