acceptodds
Under review as a conference paper at ICLR 2027

Knowledge-Augmented RL and CP for Flexible Job-Shop Scheduling

Abstract

Job-shop scheduling (JSSP) and flexible job-shop scheduling (FJSP) are challenging combinatorial problems in which fast constructive policies may be limited by early decisions during schedule construction. We propose a knowledge-augmented reinforcement learning (RL) and constraint programming (CP) method that separates schedule construction from a hierarchical Destroy-to-Improve stage. A heterogeneous scheduling graph combines structural information with heuristic rules, Pattern Memory, and Repair-Aware Memory. The Destroy Policy determines where to search, an Operation-Selection Transformer scores the operations within the selected candidate to determine what to release, and CP determines how to reconstruct the resulting region while preserving feasibility. The models are trained on a moderate-scale curriculum of synthetic JSSP/FJSP instances up to , yet remain effective on substantially larger benchmarks, obtaining competitive gaps with favorable quality-time trade-offs. They also transfer to flexible flow-shop scheduling without additional training. Finally, through a schedule-format adapter, the frozen Destroy-to-Improve model improves 445 of 675 schedules produced by five ReSched and DANIEL variants, without further fine-tuning.

Primary area:
optimization
Keywords:
Job-Shop Scheduling, Flexible Job-Shop Scheduling, Reinforcement Learning, Constraint Programming, Graph Neural Networks, Schedule Improvement, Hybrid Optimization, JSSP, FJSP, FFSP

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_KCR3OpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes KARMS, a knowledge-augmented framework combining reinforcement learning and constraint programming (CP) for JSSP and FJSP. It first constructs a feasible schedule, then hierarchically selects candidate regions and operation subsets for local CP reconstruction, using heuristic knowledge and offline memories as contextual evidence. Experiments evaluate scheduling quality, component contributions, transfer to FFSP, and improvement of schedules generated by external methods.

Critical strengths

S1. The hierarchical separation of where to search, what to release, and how to reconstruct provides a clear mechanism for combining learned guidance with feasibility-preserving optimization.

S2. The evaluation covers multiple JSSP/FJSP benchmark families, larger instances, FFSP transfer, and externally generated schedules, demonstrating applicability across several settings.

S3. The paired factorial ablation provides useful evidence that learned selection and CP reconstruction are complementary.

Critical weaknesses

W1. The quality–time advantage remains insufficiently established because comparisons lack strong CP and CP-based neighborhood-search baselines evaluated on the same hardware under matched wall-clock budgets.

W2. Since job-tail closure can substantially expand the selected operation set, the limited analysis of effective repair regions obscures how Top-B selection controls search scope and computational cost.

W3. The complex multi-stage training procedure lacks sufficiently consolidated reporting of training costs and independent retraining results for the central Destroy-to-Improve module, limiting reproducibility and confidence in its stability.

Questions for authors

Q1. Given that CP reasoning accounts for 78.1% of end-to-end runtime, how does KARMS compare with full-instance CP and conventional CP-based large-neighborhood search under identical hardware and per-instance wall-clock budgets? Including CP initialized from the same starting schedule and reporting quality-versus-time curves would help establish whether learned guidance offers an advantage over alternative uses of the available computation.

Q2. How much does job-tail closure expand the selected sets in practice, and how frequently do different Top-B selections produce the same effective repair region? Please report effective-region sizes, closure-expansion ratios, and their relationship with CP runtime; comparisons controlling the effective region size would help distinguish the benefit of learned operation selection from differences in the resulting search scope.

Q3. Could the authors consolidate the training budget for each stage, including CP supervision generation, memory construction, and total training time, and report results from independently trained Destroy-to-Improve models? Appendix N.3 varies Construct seeds while keeping Improve fixed, so it does not establish the training stability of the paper’s central improvement mechanism.

3 comments

We thank the reviewer for prompting improvements regardless of the ICLR outcome. Matched-budget baselines, effective-region accounting, and independent Improve training are important; our new evaluations clarify findings and limitations.

W1 / Q1. Matched wall-clock CP and neighborhood search. This comment gives us a nice opportunity for comparison. We evaluated 145 frozen JSSP/FJSP instances (65/80) from the same feasible K256/CP-lookahead parent, using the same hardware, one CP worker per solver, and predeclared wall-clock allowances of 20, 60, or 120 seconds according to instance size. The controls include full-instance CP, conventional CP-LNS, and adaptive LNS. KARMS with one repair branch improved 130/145 parents (mean gain 140.5; 8.14 s mean Improve wall time; 4.85 CP calls). As expected, full CP improved 138/145 (gain 186.3; 32.4 s), CP-LNS 134/145 (gain 126.6; 38.4 s), and adaptive LNS 141/145 (gain 171.3; 38.7 s). KARMS thus delivers substantial improvements in considerably less time on average, while full CP and adaptive LNS achieve higher final solution quality through longer searches. In paired final outcomes, KARMS beat/tied/lost to Full CP on 20/14/111 instances, and to adaptive LNS on 20/10/115. Thus, strong methods attain better final quality when allowed to search longer. The allowances are matched, not the CPU-seconds consumed. The key question here is whether learned CP-guided repair can deliver substantial improvements within a limited computational budget.

Our aim is not to question the effectiveness of CP-LNS, but to examine whether learned CP-guided repair can achieve substantial improvements within a limited computational budget. KARMS leads in early gains at 1–3 s (see below) These findings complement prior work on the effectiveness of RL-guided optimization and learned scheduling improvement (Wu et al., 2021; Tassel et al., 2023; Zhang et al., 2024) and offer learned repair that sustains a time-quality tradeoff (see next paragraph in this). Main p. 9 (Table 5); Appendix M.1, p. 46 (Table 27 and matched-budget protocol).

We now record the best feasible incumbents at common elapsed times on all 145 parents. At 1 s, mean gains were 29.4 for KARMS, 9.7 for full CP, 5.8 for corrected CP-LNS, and 21.5 for adaptive LNS; at 2 s they were 43.2, 17.5, 10.6, and 34.3; and at 3 s they were 54.6, 22.8, 15.9, and 49.0. Thus, KARMS has the largest average gain during the first three seconds of these trajectories. At 20 s, the gains are 130.2, 100.1, 98.4, and 141.6: adaptive LNS then leads. These are recorded within-run anytime slices; they should not be read as independent 1–3 s deadline experiments or as universal superiority. The revised main paper shows the quality–time curve, and Appendix M.1 reports the stronger final-quality outcomes of full CP and adaptive LNS Main p. 9 (Figure 2); Appendix M.1, p. 46 (Table 28)

W2 / Q2. Closure, effective neighborhoods, and Top-B. This is valid indeed, thanks. On four measured development parents, job-tail closure expanded selected regions by approximately 1.57–2.20 times (e.g., 40 selected operations became 81 or 88 released operations).

We additionally measured effective repair-region sizes across all 145 matched parents. Learned selection with closure releases 229 operations on average (expansion factor 2.03) and achieves a mean gain of 132.1, compared with 227 operations and gain 123.7 for random selection with the same initial selection size. Criticality selection with closure achieves a gain of 82.0, while learned selection without closure releases 101 operations and achieves a gain of 87.5.

These results support the roles of both closure and learned selection. However, equal initial selection size does not guarantee identical effective regions or CP costs. We therefore do not attribute all gains to ranking or claim a universal monotonic runtime effect. Appendix provides expansion statistics, effective-region collisions, and six-arm comparisons.
Main p. 9 (Table 4); Appendix O.6, pp. 55–56 (Tables 42–43 and effective-region diagnostics).

W3 / Q3. Training budget. Full Construct training took approximately 336 hours, its repair-oriented refinement another 336 hours, the Improve training stages about 270 hours (including the original final-stage continuation), and offline data-pool and memory construction about 36 hours. These add to approximately 978 hours of stage-level elapsed work. We then repeated the final Improve training stage with two additional random seeds, taking 10.0 and 9.8 hours. We further evaluated the original frozen Improve checkpoint and both additional training continuations on 500 common starting schedules. Their mean final makespans were 1961.924, 1964.570, and 1965.316, respectively, with identical outcomes across all three checkpoints on 388/500 schedules. These results provide broader evidence of stability for the final Improve continuation. Appendix J.7, pp. 37–38 (Tables 13–14); J, pp. 35–38 (training stages)

Thank you for the detailed responses and additional experiments. The comparisons at common elapsed times and the effective-region analysis substantially alleviate my first two concerns and clarify the scope of the quality–time benefits. The consolidated training-cost report is also helpful, although repeating only the final Improve continuation does not establish the stability of the full training procedure, and effective-region sizes and repair costs remain only partially controlled. I will raise my rating to reflect these improvements and the remaining limitations.

We thank the Reviewer for the constructive reassessment and recognition of the improvements. We have further strengthened the evidence on anytime performance, effective neighborhood size, computational cost, and training reproducibility. Anytime performance (Appendix M.1–M.2, pp. 47–50). A unified seven-method comparison on 500 common starting schedules, with a 20-second allowance and one CP worker, shows that KARMS achieves the largest mean improvement at 1–3 seconds (52.90 at 3 seconds, versus 24.30 for full CP, 17.10 for CP-LNS, and 46.80 for adaptive LNS). At 20 seconds, full CP and adaptive LNS achieve better final quality, while KARMS significantly outperforms random repair (+53.88, 95% CI [42.19, 66.59]) and uses less actual wall time (7.49 seconds versus 15.20, 19.60, and 19.80 seconds, respectively). The original 145-instance comparisons remain separately documented.

Effective neighborhood size and repair cost (Appendix O.6, pp. 58–61). On same 500 common starting schedules, learned, random, and criticality-based selection have closely matched effective neighborhood sizes (280/276/276 operations) and CP times (3.25/3.33/3.42 seconds). Nevertheless, learned selection achieves larger mean gains (89.23/58.43/66.18), with paired advantages of +30.80 [27.11, 34.54] and +23.05 [19.65, 26.55]. These advantages also persist in a stricter 171-instance subset with effective-size differences of at most two operations.

Training reproducibility (Appendix J.7, pp. 37–39; O.3, pp. 55–56). Beyond shared-checkpoint continuations, we completed two additional Improve training runs from independent random initializations, without reusing pretrained Improve-policy weights. Both were evaluated on 500 job-shop/flexible job-shop instances, 3,000 flexible flow-shop instances, and 675 external schedules. One closely matches the original job-shop quality (1961.562 versus 1961.924 mean makespan), while the other differs by 3.44%; both improve aggregate flow-shop results.

Reviewer_JmPBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes KARMS, a knowledge-augmented framework combining reinforcement learning and constraint programming for job-shop scheduling. Its main contributions are hierarchical selection of regions and operation subsets for CP-based repair, CP-guided training, and complementary construction and repair memories. Across 500 benchmark instances, KARMS reduces the average gap from 22.71% for its initial constructor to 10.34% for the full pipeline; overall, the methodology is clearly structured, but its novelty beyond existing approaches and the benefits of its added complexity remain insufficiently established

Critical strengths
  1. The paper’s contributions is clear, particularly its combination of learned selection and CP-based repair. The results across standard scheduling benchmarks are promising, and the ablation studies provide useful evidence that the proposed components improve schedule quality.

  2. Frozen improvement module can refine schedules produced by other schedulers without retraining is useful. This suggests that its value is not limited to correcting weaknesses in its own constructor and makes it potentially useful as a reusable component in existing scheduling pipelines.

Critical weaknesses
  1. My main concern is that the contribution appears to lie more in integrating existing techniques than in introducing a substantial methodological advance. CP-based large neighborhood search has already been applied to flexible job-shop scheduling (Pacino & Van Hentenryck, 2011) and learning which variables to release for solver-based repair has been explored in integer programming (Wu et al., 2021). While KARMS adds hierarchical selection and memory mechanisms, its novelty beyond these established ideas is not yet sufficient.
  2. The benefits of the framework’s added complexity are not consistent across benchmarks. On the 162 common JSSP instances, KARMS reports an average gap of 9.00%, compared with 6.90% for L2S-5000; on Hurink, its gap is 4.29%, compared with 2.87% for NDS-S. Although differing computational budgets prevent a direct efficiency comparison, these results leave unclear when hierarchical selection, memory, and CP repair offer sufficient benefits to justify their added complexity.
Questions for authors
  1. What is KARM’s advantage compared with traditional CP-LNS solver under the same initial schedules and total wall-clock budget? A comparison would help establish whether the learned components offer an advantage under matched computational budgets.
  2. Moving Figure 1 from the appendix to the main text would make the overall framework easier to follow. Additional figures would also improve readability for human, as the main text currently contains no figure.
  3. Could the authors explain why the improvement stage reduces the gap by only 0.66 percentage points on 100×20 instances, while the end-to-end runtime on Taillard 100×20 reaches approximately 21.1 minutes, and discuss what may limit the framework’s scalability?
3 comments

We thank the Reviewer for the detailed comments and the references to Pacino and Van Hentenryck (2011) and Wu et al. (2021). We agree that combining learning with CP repair is not, by itself, novel, and the revised Introduction and Related Work sharpen the contribution and its experimental qualifications accordingly.

W1. Methodological contribution and related work. We agree that CP-based LNS and learned variable-release policies are established approaches. KARMS introduces hierarchical selection and memory mechanisms. The main methodological distinction lies in their scheduling-specific integration: candidate ranking determines where to search, structured operation selection with job-tail closure determines what to release, and bounded CP determines how to reconstruct the schedule. Structural, heuristic, and historical memory information provide context for these decisions rather than imposing fixed rules. We have clarified this contribution and its relationship to Pacino and Van Hentenryck (2011) and Wu et al. (2021) in the revised Introduction and Related Work. Main pp. 3–4 (Contributions, Related Work).

W2. L2S, NDS-S. NDS-S achieves a lower mean gap on the 120 Hurink instances (2.87% versus 4.29%). Nevertheless, the paired per-instance comparison shows that KARMS achieves a lower gap on 31 instances (25.8%) and ties on another 10 (8.3%), while NDS-S performs better on the remaining 79. This highlights instance-dependent strengths, rather than overall superiority, despite the difference in aggregate performance. The NDS-S gaps are recomputed from its official validation-selected per-instance outputs using the same reference values as KARMS. For L2S-5000, the cited 6.90% on 162 JSSP instances is reconstructed from the authors' published, instance-count-weighted family means, whereas our 9.00% is the mean of per-instance gaps on the corresponding 162. We contacted the authors but did not obtain the evaluated model checkpoints, so an exact same-hardware, same-search-budget rerun was not possible. The revised comparison retains the published values, labels the different protocols and timing scopes, and makes no state-of-the-art or matched-compute claim. Main pp. 7–8 (benchmark comparisons); Appendix N.1–N.2, pp. 48–50; L.7, pp. 43–46 (Table 24, paired statistics).

Q1. Comparison with conventional methods. We evaluated KARMS, full-instance CP, corrected CP-LNS, and adaptive LNS on 145 common initial schedules, using the same hardware, one solver worker, and predeclared per-instance time allowances (20, 60, or 120 s). KARMS achieved a mean gain of 140.5 in just 8.14 s (4.85 CP calls), compared with 126.6 in 38.4 s for CP-LNS. Full CP and adaptive LNS achieved higher final gains (186.3 and 171.3) but required substantially more time on average (32.4 and 38.7 s, respectively). Thus, KARMS provides faster improvements, although stronger solvers achieve better final quality with longer search.

To examine early performance, we recorded the best feasible solution found by each method after 1, 2, and 3 seconds of the same execution. At these times, mean gains were 29.4/43.2/54.6 for KARMS, 9.7/17.5/22.8 for full CP, 5.8/10.6/15.9 for CP-LNS, and 21.5/34.3/49.0 for adaptive LNS. KARMS therefore achieves the highest average gains during the first three seconds, while adaptive LNS overtakes it later (141.6 versus 130.2 at 20 s). These measurements come from the original runs, not separate experiments restarted with shorter deadlines. Common time allowances do not imply equals actual computation time. Main p. 9 (Table 5 and Figure 2); Appendix M.1, p. 46 (Tables 27–28)

Q2. Presentation. Figure 1 now appears in the Introduction (p. 2), providing an overview of the KARMS workflow. We also added Figure 2 (p. 9), illustrating the quality–time trade-off between KARMS and the CP/LNS baselines. Main p. 2 (Figure 1); p.9 (Figure 2)

Q3. Large-instance quality and runtime. On the ten Taillard 100×20 instances, the full pipeline reduces mean gap from 11.657% to 10.994%. CP lookahead contributes 0.172 percentage points (11.657% to 11.485%) at a mean cost of 940 s, while Improve contributes a further 0.491 points in only 44 s. Thus, although the absolute improvement remains modest, learned repair provides additional quality at relatively low incremental cost. Its bounded local neighborhoods cannot necessarily correct decisions outside the released regions, which may limit improvements on large instances. The 21.14-minute mean end-to-end runtime is dominated by construction (284 s) and CP lookahead (940 s), rather than Improve (44 s). We acknowledge the remaining quality gap and computational cost as limitations, discussed in Appendix N.3 (pp. 49–50) and L.6 (pp. 42–45).

Thank you for your rebuttal. I will maintain my score.

We thank the Reviewer for their time and careful consideration of our rebuttal. We appreciate their feedback and respect their assessment. We have made every effort to address the concerns raised in the review through detailed responses and additional experimental evidence. If any questions or concerns remain insufficiently addressed, we would be happy to provide further clarification, analysis, or experimental results where feasible.

Thank you for your consideration.

Reviewer_XnKJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Job-shop (JSSP) and flexible job-shop scheduling (FJSP) are hard combinatorial problems where fast constructive heuristics can make early greedy choices. This paper presents a knowledge-augmented framework that combines reinforcement learning (RL) and constraint programming (CP) by separating initial construction from a hierarchical Destroy-to-Improve phase. A heterogeneous scheduling graph captures problem structure, heuristic guidance, Pattern Memory, and Repair-Aware Memory. A learned Destroy Policy chooses \emph{where} to search; an Operation-Selection Transformer ranks operations to decide \emph{what} to release; and CP determines \emph{how} to repair the subproblem while preserving feasibility.

Critical strengths

This paper can achieve cross-scale generalization and cross-problem (FFSP) transfer without retraining for specific sizes, and can be used as a plug-and-play module to optimize scheduling methods generated by third-party algorithms.

Critical weaknesses
  1. High runtime overhead: The CP solver accounts for up to 78% of the end-to-end runtime, sacrificing computational efficiency.

  2. Unfair baseline comparison: KARMS uses single-step deterministic inference, while most baseline comparisons rely on multiple sampling (Best-of-N).

  3. Generalization risk of static offline memory: The historical patterns and repaired memories used in the paper remain frozen during testing after offline clustering, potentially failing when faced with unknown distribution shifts.

  4. Exaggerated external repair effects: Claims to improve third-party algorithms, but the "zero degradation" is primarily attributed to a strict greedy acceptance criterion, rather than the universal error-correcting ability of the learning module itself.

Questions for authors

See the Critical Weaknesses.

2 comments

We thank the Reviewer for the careful assessment. We clarify computational cost, baseline protocols, offline memory, and non-degradation

W1. CP accounts for 78.1% of mean end-to-end time: 65.7% is Construct lookahead and 12.3% is local Improve repair in our 500-instance evaluation (67.3% and 10.5%, respectively, on JSSP-242). Lookahead improves parent quality by only 2.92 percentage points, thus could be turned off. The no-lookahead Construct produces a 22.71% mean gap in approximately 18.5 s; bounded lookahead improves the parent gap to approximately 19.79%, while a separate component-level audit measures approximately 63.1 s of Construct CP-lookahead time. Bounded lookahead complements the actor's learned decisions with constraint-based local refinement, improving the quality of the constructed schedule without requiring global optimality. Quality–cost trade-off is reported separately from the subsequent Improve stage Main p. 9 (component results); Appendix L.6, pp. 42–44 (Table 22); O.4, pp. 53–54 (Table 40, stage-wise pipeline)

W2. The inference protocols could be separated but without improvement, as shown by our revised results. The initial KARMS evaluation uses deterministic candidate selection and a three-branch CP repair choice; L2S-5000 and TBGAT-5000 use iterative search, while several other published baselines use sampling. We now offer two additional evaluations on the same 500 instances. Five sampled trajectories with one repair branch achieved a mean gap of 10.425%, compared with 10.339% for the submitted deterministic configuration (99/334/67 sampled wins/ties/losses). When retaining three CP branches per sampled trajectory, the mean gap decreased to 10.387% (136/322/42 wins/ties/losses), remaining slightly above the deterministic result. Thus, additional sampling can improve individual instances but does not improve the overall mean gap under the evaluated configurations, despite requiring a larger test-time search budget. These results suggest that KARMS achieves competitive quality with deterministic inference and limited repair iterations, without extensive test-time search, highlighting the effectiveness of its learned guidance.Both sampling protocols, their computational costs, and solution diversity. Main pp. 7–8 (baseline protocols); Appendix M.3, p. 47 (Tables 29–30, both sampling protocols)

W3. We never claimed that frozen offline memory adapts to arbitrary distribution shifts. Now we stipulate this further: in the submitted 55-instance matched ablation, the mean gap is 3.98% with both memory sources, 4.23% without Repair-Aware Memory, 4.45% without Pattern Memory, and 6.39% without either. These results support the usefulness of the memory context in that submitted configuration, but do not establish online adaptation. The additional evaluation shows that a frozen Improve model can successfully repair schedules generated by independent algorithms, strictly improving 631/675 DANIEL/ReSched schedules without retraining or online memory updates. FFSP transfer also uses no online adaptation. These results support transfer across scheduling settings, but do not establish memory adaptation to arbitrary distribution shifts

Structural features, heuristic recommendations, and offline-memory statistics are integrated as contextual inputs to learned scoring modules; memory remains advisory and cannot enforce an action, while the actor retains the final decision based on the current scheduling state. We distinguish these evidence scopes in the appendix and identify online Pattern Memory updates as future work. Main pp. 2–3 (two memories); Appendix C.2–C.3, pp. 21–22; M.2, p. 47; O.9, p. 58 (Table 49)

W4. We agree that non-degradation is guaranteed by the feasible-incumbent mechanism and the CP bound Cmax(child) ≤ Cmax(parent), not by a universal error-correcting ability of the network. Neutral feasible changes can be used during search, but the returned best incumbent is not worse. In the additional external-repair evaluation, 631/675 DANIEL/ReSched schedules improved strictly, and none worsened. Under a common strict-improvement acceptance control and approximately five CP calls per parent, learned selection improved 625/675 schedules (mean gain 60.7), versus 291/675 (11.8) for random-bank repair and 88/675 (2.4) for size-matched nonlearned repair. We further allowed the two nonlearned controls up to 8.35 s per schedule, matching KARMS's previously observed mean runtime. Random-bank and size-based repair then improved 613/675 and 611/675 schedules, with mean gains of 36.6 and 44.7, respectively, compared with 625/675 and 60.7 for KARMS. Despite using approximately 250 and 209 CP calls on average, both controls remained below learned selection in mean gain. The revised discussion separates the incumbent-safety guarantee from the empirical contribution of learned selection. Main p. 10 (external repair); Appendix H, pp. 31–33 (feasible CP repair); O.12, pp. 60–61 (Tables 53–54)

We thank the Reviewer for their time and thoughtful feedback. We have carefully addressed the points raised in our rebuttal, including additional experimental evidence. If any questions or concerns remain before discussion deadline, we would be happy to provide further clarification.

We appreciate your consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.