- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2(+1)
Read review
Paper summary
This paper proposes Resource-Capacity Reasoning (RCR), a framework for incorporating analytical capacity information into reinforcement learning for flexible job-shop scheduling. RCR augments action representations with a Balanced-Capacity Descriptor (BCD) and introduces a Completion-Loss Certificate (CLC) as an auxiliary reward penalty. Experiments integrating RCR into three scheduling backbones show improvements across synthetic and public FJSP benchmarks, with additional evaluations on JSSP.
Critical strengths
S1. RCR incorporates explicit resource-capacity information into existing scheduling policies without modifying their underlying encoders, facilitating integration across different neural architectures.
S2. BCD and CLC provide complementary guidance for action evaluation and policy learning through a shared foundation of analytical capacity conditions.
S3. Evaluation across three backbones, two decoding strategies, and multiple synthetic and public benchmarks demonstrates broadly consistent improvements in scheduling quality.
Critical weaknesses
W1. The alignment between cumulative CLC penalties and makespan minimization is insufficiently established, since the auxiliary penalty can change policy preferences beyond the original scheduling objective.
W2. Dependence on the heuristic reference horizon is only partially evaluated, as Appendix G considers mild test-time horizon relaxations without examining training-time sensitivity or different reference-schedule qualities.
W3. The certificate assumes that subsequent operations cannot start before each machine’s current ready time, but compatibility of this assumption with all integrated backbones is insufficiently documented.
W4. Aggregate counts of improved configurations provide limited evidence about the statistical significance and practical consistency of the gains, particularly for marginal improvements and settings exhibiting degradation.
Questions for authors
Q1. Under what conditions does reducing accumulated CLC penalties improve the final makespan? Equations (17)–(18) penalize violations at every step, so trajectories with similar final makespans may receive different cumulative penalties depending on when violations occur. Please clarify the intended optimization bias and provide analysis or comparisons with incremental or terminal violation penalties.
Q2. How sensitive is RCR to the quality of the reference schedule used to construct H, during both training and inference? Appendix G evaluates only test-time relaxations of the default horizon; comparisons using alternative feasible reference schedules, together with CLC activation rates and performance relative to the reference schedules themselves, would help establish how informative this guidance remains.
Q3. Do all three backbone environments enforce the assumption that newly assigned operations start no earlier than the machine’s current ready time? If any backbone permits insertion into earlier idle intervals, please explain how the capacity calculation and certificate remain valid, and whether integrating RCR required changes to the original scheduling transition.
Q4. Could the authors provide paired confidence intervals or significance tests for performance differences, together with instance-level win/tie/loss statistics? For example, HGNN improves only from 15.53% to 15.51% on Edata, while greedy RESCHED deteriorates from 9.08% to 10.81% on Brandimarte. These analyses would help distinguish reliable improvements from small fluctuations and clarify the circumstances in which RCR is detrimental.
7 comments
(2/4) Author Response: We clarify CLC alignment, horizon sensitivity, transition validity, and statistical reliability.
A1 (continued): About CLC penalties and makespan minimization:
To assess this temporal formulation, we retain BCD and compare four penalty variants: Dense, the proposed RCR penalty, None, without the CLC penalty, Incremental, using signed certificate differences, and Terminal, applying the penalty only at episode completion. Let and write the auxiliary reward as . We have added this discussion to Appendix I.1 of the revised manuscript.
The table reports mean instance-wise gaps on SD1 under greedy decoding. All variants use identical backbone configurations, training budgets, and test instances. The nonzero penalties use the same coefficient .
| Variant | DANIEL gap (%) | RESCHED gap (%) | |
|---|---|---|---|
| Dense (RCR) | 0.18 | −0.95 | |
| None | 1.01 | 0.38 | |
| Incremental | 0.77 | 0.03 | |
| Terminal | 0.91 | −0.08 |
For , signed increments telescope to , giving the terminal penalty up to an initial-state constant. Their learning effects can nevertheless differ through temporal credit assignment. This equivalence need not hold for discounted returns. Dense CLC retains information about intermediate violations that these two cumulative penalties discard when .
Dense CLC achieves the lowest mean gap on both backbones. Relative to BCD alone, it reduces the gap by 0.83 percentage points for DANIEL and 1.33 for RESCHED. Incremental and terminal penalties also improve over BCD alone, but yield smaller gains. Table 3 further shows that removing CLC worsens RCR-RESCHED on all four SD1 sizes. These results support CLC as a substantive training component with a role distinct from BCD and benefits beyond capacity-feature augmentation in the evaluated settings.
Q2: How sensitive is RCR to the quality of the reference schedule used to construct H, during both training and inference? Appendix G evaluates only test-time relaxations of the default horizon; comparisons using alternative feasible reference schedules, together with CLC activation rates and performance relative to the reference schedules themselves, would help establish how informative this guidance remains.
A2: About reference-horizon quality during training and inference:
Appendix G.1 evaluates inference-time horizon changes using fixed checkpoints, with , where and . The maximum gap increase is 1.13 percentage points. We have additionally retrained RCR-RESCHED under four reference rules on SD1 , with the results reported in Appendix G.2 of the revised manuscript.
Each model uses the same horizon rule for training and evaluation, with backbone configurations, RCR hyperparameters, training budgets, and test instances fixed. This assesses the combined training and inference effects. The portfolio selects the best of SPT, MWKR, and 14 randomized dispatch schedules. Reference schedules follow the evaluated environment’s transition and feasibility masks, with each horizon fixed throughout the episode. Training activation is averaged over the entire training process, covering all training iterations. Results use greedy decoding.
| Horizon rule | Reference gap (%) | RCR gap (%) | Training CLC activation (%) | Test CLC activation (%) | Gap to reference horizon (%) |
|---|---|---|---|---|---|
| SPT | 0.65 | 0.17 | 74 | 69 | −0.44 |
| MWKR | 0.81 | 0.23 | 75 | 72 | −0.69 |
| Default minimum | 0.08 | −0.95 | 78 | 75 | −0.80 |
| Feasible reference portfolio | 0.02 | −0.98 | 79 | 71 | −0.85 |
Reference and RCR gaps are mean instance-wise percentage gaps to the main experiments’ CP-SAT reference. The final column averages over test instances, with negative values indicating an average relative improvement over the reference schedule. CLC activation is the percentage of decision steps with . Test activation is computed offline, as the CLC penalty is unused during inference.
RCR improves upon its reference schedule on average under all four rules. The default minimum yields a lower RCR gap than either individual rule and comes within 0.03 percentage points of the portfolio, supporting its effectiveness with only two deterministic reference schedules. CLC remains active under all four rules.
Here, an optimal reference is unnecessary for obtaining improved solutions, although reference quality can affect the usefulness of capacity guidance. Certificate validity depends on the capacity and scheduling-transition assumptions in Proposition 2.
(3/4) Author Response: We clarify CLC alignment, horizon sensitivity, transition validity, and statistical reliability.
Q3: Do all three backbone environments enforce the assumption that newly assigned operations start no earlier than the machine’s current ready time? If any backbone permits insertion into earlier idle intervals, please explain how the capacity calculation and certificate remain valid, and whether integrating RCR required changes to the original scheduling transition.
A3: About the scheduling-transition assumption across backbones:
Yes. In all three integrated environments, newly assigned operations start no earlier than the latest completion time of operations already assigned to the selected machine. RCR preserves the original scheduling transitions, including their start-time updates and feasibility masks.
| Backbone | Native start-time rule | Insertion into earlier machine gaps | Scheduling transition changed by RCR |
|---|---|---|---|
| HGNN | Dispatch at the current event time, with busy machines and unavailable jobs masked | No | No |
| DANIEL | Maximum of operation-ready and machine-ready times | No | No |
| RESCHED | Maximum of operation-ready and machine-ready times | No | No |
HGNN’s event-driven implementation differs from the other two environments: an action dispatches an available operation on an idle machine at the current clock time. This still ensures that its start time is no earlier than the machine’s previously assigned completion time. DANIEL and RESCHED explicitly update machine availability to the completion time of each newly assigned operation. Previously committed processing intervals remain fixed in all three cases.
These implementation details establish the assumption required by Proposition 2. Because previously assigned processing intervals remain fixed and subsequent operations cannot start before the machine’s ready time, Eq. (4) provides a valid upper bound on the capacity available to remaining operations. HGNN additionally enforces the current event time as a lower bound on future start times.
For an environment that permits insertion into earlier idle intervals, the machine-tail expression would require adaptation. Let denote the union of fixed occupied intervals on machine , and let denote the total duration of the intervals in . An appropriate capacity upper bound is $ C_{G}^{\mathrm{ins}}(l,u) = \sum_{k\in G} [(u-l)-\ell([l,u]\cap\mathcal{B}_{k}(s_{t}))]. $ This capacity bound must be combined with valid temporal bounds for the environment. We have documented these transition assumptions and clarified the adaptations required for earlier-gap insertion in Appendix I.2 of the revised manuscript.
(1/4) Author Response: We clarify CLC alignment, horizon sensitivity, transition validity, and statistical reliability.
We thank the reviewer for recognizing RCR’s modularity, complementary BCD and CLC components, and empirical improvements. We address the four questions below with additional analyses, experiments, and implementation details.
A1: About CLC penalties and makespan minimization:
CLC is a key training component of RCR with a role distinct from BCD. BCD provides comparative capacity information for candidate actions, but BCD alone leaves policy learning dependent on the backbone reward. CLC evaluates the full constructed constraint set on the executed successor, rather than the active subset used by BCD, and converts completion-condition violations into explicit training feedback. The two components therefore provide complementary guidance at the action-representation and policy-optimization levels.
Under Proposition 2’s assumptions, a positive CLC means that every feasible continuation preserving the current commitments has makespan greater than H. This identifies partial schedules whose commitments have ruled out completion within the reference horizon. However, zero CLC does not guarantee completion within H, and its magnitude is not established as a makespan-regret bound. Accordingly, cumulative penalties need not rank all trajectories by final makespan.
A conditional alignment result clarifies the relationship to the original objective. For a fixed instance with N operations and a complete trajectory S with T decisions, define P(S)=N1∑t=0T−1Δ(st+1;H).
Suppose the certificate assumptions hold, the undiscounted base return equals a constant minus Cmax(S)/σ for fixed σ>0, and H is the makespan of a feasible reference schedule attainable under the same transition. Any trajectory completing within H admits such a completion from every prefix and therefore has P(S)=0. Since the reference is attainable, every makespan-optimal trajectory satisfies Cmax≤H. Together with P(S)≥0, this gives, for λ≥0, Sargmin[Cmax(S)+λP(S)]=SargminCmax(S).
Both minimizations are over feasible trajectories under the same transition. Under these conditions, CLC does not penalize makespan-optimal trajectories, while the base reward continues to distinguish schedules completing within H. This does not imply that reducing P(S) alone improves makespan or guarantee policy convergence. It also does not establish objective equivalence for RESCHED with γ=0.99. We have revised “preserving the makespan objective” in Appendix F.2 to specify that RCR retains the makespan-oriented reward and adds an auxiliary penalty, without claiming general policy invariance.
Dense CLC deliberately penalizes both violation magnitude and persistence. If a positive certificate remains unchanged over several steps, dense CLC continues to penalize those states, whereas signed increments are zero at those steps and a terminal penalty is applied only at completion. The factor 1/N normalizes the accumulated penalty by problem size. Trajectories with similar final makespans can consequently receive different penalties, reflecting an explicit preference against large or persistent certified violations.