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