acceptodds
Under review as a conference paper at ICLR 2027

Learning with Resource-Capacity Reasoning for Flexible Job-Shop Scheduling

Abstract

Deep Reinforcement Learning (DRL) has emerged as a promising paradigm for Flexible Job-Shop Scheduling (FJSP). However, existing DRL-based schedulers predominantly rely on learned state representations to evaluate candidate decisions, with limited explicit reasoning about whether an action preserves sufficient resource capacity to avoid future bottlenecks and complete the remaining operations. In this paper, we introduce Resource-Capacity Reasoning (RCR), an encoder-agnostic framework that incorporates analytical capacity information into DRL-based scheduling without modifying the underlying encoder. RCR constructs a Balanced-Capacity Descriptor (BCD) that characterizes how each candidate assignment changes residual capacity pressure and redistributes bottlenecks, augmenting the corresponding action representation used by the policy network. Based on the same capacity conditions, RCR further introduces a Completion-Loss Certificate (CLC) and incorporates it as an auxiliary penalty while preserving the original makespan-oriented reward. Extensive experiments across representative DRL-based scheduling methods demonstrate consistent improvements in solution quality. Moreover, RCR naturally extends to the Job-Shop Scheduling Problem (JSSP), confirming its applicability for different scheduling variants.

Primary area:
reinforcement learning
Keywords:
Resource-Capacity Reasoning, Flexible Job-Shop Scheduling, Deep 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 2 reviews, above 27% of the others.
Reviewer_1vfEOpenReview ↗
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 HH 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
AuthorsOpenReview ↗

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

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.

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 HH. This identifies partial schedules whose commitments have ruled out completion within the reference horizon. However, zero CLC does not guarantee completion within HH, 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 NN operations and a complete trajectory SS with TT decisions, define P(S)=1N∑t=0T−1Δ(st+1;H).P(S)=\frac{1}{N}\sum_{t=0}^{T-1}\Delta(s_{t+1};H).

Suppose the certificate assumptions hold, the undiscounted base return equals a constant minus Cmax⁡(S)/σC_{\max}(S)/\sigma for fixed σ>0\sigma>0, and HH is the makespan of a feasible reference schedule attainable under the same transition. Any trajectory completing within HH admits such a completion from every prefix and therefore has P(S)=0P(S)=0. Since the reference is attainable, every makespan-optimal trajectory satisfies Cmax⁡≤HC_{\max}\le H. Together with P(S)≥0P(S)\ge0, this gives, for λ≥0\lambda\ge0, argminS[Cmax⁡(S)+λP(S)]=argminSCmax⁡(S).\underset{S}{\mathrm{argmin}} [C_{\max}(S)+\lambda P(S)] = \underset{S}{\mathrm{argmin}} C_{\max}(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 HH. This does not imply that reducing P(S)P(S) alone improves makespan or guarantee policy convergence. It also does not establish objective equivalence for RESCHED with γ=0.99\gamma=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/N1/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.

AuthorsOpenReview ↗

(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 Δt=Δ(st;H)\Delta_t=\Delta(s_t;H) and write the auxiliary reward as −λqt/σ-\lambda q_t/\sigma. We have added this discussion to Appendix I.1 of the revised manuscript.

The table reports mean instance-wise gaps on SD1 20×1020\times10 under greedy decoding. All variants use identical backbone configurations, training budgets, and test instances. The nonzero penalties use the same coefficient λ=0.3\lambda=0.3.

Variantqtq_tDANIEL gap (%)RESCHED gap (%)
Dense (RCR)Δt+1/N\Delta_{t+1}/N0.18−0.95
None001.010.38
IncrementalΔt+1−Δt\Delta_{t+1}-\Delta_t0.770.03
Terminal1[t=T−1]ΔT\mathbf{1}[t=T-1]\Delta_T0.91−0.08

For γ=1\gamma=1, signed increments telescope to ΔT−Δ0\Delta_T-\Delta_0, 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 γ=1\gamma=1.

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 H=αH0H=\alpha H_{0}, where H0=min⁡Cmax⁡SPT,Cmax⁡MWKRH_{0}=\min\\{C_{\max}^{\mathrm{SPT}},C_{\max}^{\mathrm{MWKR}}\\} and α∈1.0,1.1,1.2\alpha\in\\{1.0,1.1,1.2\\}. The maximum gap increase is 1.13 percentage points. We have additionally retrained RCR-RESCHED under four reference rules on SD1 20×1020\times10, 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 ruleReference gap (%)RCR gap (%)Training CLC activation (%)Test CLC activation (%)Gap to reference horizon (%)
SPT0.650.177469−0.44
MWKR0.810.237572−0.69
Default minimum0.08−0.957875−0.80
Feasible reference portfolio0.02−0.987971−0.85

Reference and RCR gaps are mean instance-wise percentage gaps to the main experiments’ CP-SAT reference. The final column averages 100(Cmax⁡,iRCR−Hi)/Hi100(C_{\max,i}^{\mathrm{RCR}}-H_i)/H_i over test instances, with negative values indicating an average relative improvement over the reference schedule. CLC activation is the percentage of decision steps with Δ>0\Delta>0. 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.

AuthorsOpenReview ↗

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

BackboneNative start-time ruleInsertion into earlier machine gapsScheduling transition changed by RCR
HGNNDispatch at the current event time, with busy machines and unavailable jobs maskedNoNo
DANIELMaximum of operation-ready and machine-ready timesNoNo
RESCHEDMaximum of operation-ready and machine-ready timesNoNo

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 Bk(st)\mathcal{B}_{k}(s_{t}) denote the union of fixed occupied intervals on machine kk, and let ℓ(A)\ell(A) denote the total duration of the intervals in AA. 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.

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

The paper introduces RCR, which augments existing DRL schedulers with capacity-based action features and an auxiliary reward penalty. The work is well organized and supported by extensive experiments, while its modular design allows integration without changing the backbone encoder. However, the broader applicability of its heuristic capacity-based features remains unclear, and the contribution appears primarily incremental, focusing on integrating established capacity reasoning into existing scheduling frameworks.

Critical strengths

RCR can be integrated into existing scheduling networks without changing their encoder architectures, and its evaluation across GNN/Transformer backbones and PPO/REINFORCE supports its compatibility with different approaches. It adds only four interpretable features per candidate action and requires no optimal-schedule labels for its capacity-based guidance. Experiments across multiple datasets, together with component ablations and multi-seed results on selected FJSP settings, provide useful evidence of its effectiveness.

Critical weaknesses

RCR may introduce substantial computational overhead, since it evaluates multiple capacity pressures for every feasible action at every decision step. Although the paper reports overall inference times, it is unclear how much time is spent on the added capacity analysis. A complexity analysis and a runtime breakdown separating state construction, capacity analysis, and neural inference would help clarify this concern. This matters particularly given the modest gains on JSSP: averaging the reported gaps equally across instance sizes gives reductions of around 0.59 percentage points on Taillard and 0.31 on DMU, with some regressions and no corresponding uncertainty estimates. It is therefore unclear whether these gains justify the additional computation.

RCR relies on heuristic capacity-based features to guide action scoring, which raises questions about how easily it extends to other scheduling formulations. These features depend on the assumed precedence structure and constraints, and may require adaptation when those assumptions change. For example, the job-path metrics do not directly carry over to general precedence-DAG scheduling without predefined job chains. This limits what can be concluded about broader applicability from the current experiments. FFSP, which was evaluated in the original RESCHED paper, is also omitted, leaving the evaluation restricted to standard FJSP/JSSP settings.

Questions for authors
  1. Can you provide a complexity analysis and a runtime breakdown separating state construction, capacity analysis, and neural inference?
  2. Can you provide multi-seed results to assess the reliability of the modest gains on Taillard and DMU?
  3. Can you provide results on FFSP, which was evaluated in the original RESCHED paper?
8 comments
AuthorsOpenReview ↗

(1/3) Author Response: We clarify RCR's computational cost, statistical reliability, and applicability to FFSP.

We thank the reviewer for recognizing RCR’s modularity, soundness, and compatibility across encoders and policy-gradient algorithms. We have added experiments and methodological clarifications to strengthen the assessment of RCR’s efficiency, reliability, and applicability.

W1: It is therefore unclear whether these gains justify the additional computation.

A1 response to Q1 provides a complexity analysis and runtime breakdown to assess the quality–runtime trade-off. A2 response to Q2 reports matched five-seed evaluations on Taillard and DMU to assess variability across runs, explicitly retaining the observed regression.

W2: RCR relies on heuristic capacity-based features to guide action scoring, which raises questions about how easily it extends to other scheduling formulations.

A3 response to Q3 reports additional FFSP experiments. A4 clarifies RCR’s applicability and the adaptations required for general precedence DAGs, distinguishing demonstrated applicability from potential extensions.

Q1: Can you provide a complexity analysis and a runtime breakdown separating state construction, capacity analysis, and neural inference?

A1: About computational complexity and runtime:

Let NN, mm, and AtA_t denote the numbers of operations, machines, and feasible actions, respectively. Let BB denote the number of time bins. With g≤m+1+Gmaxg \le m+1+G_{max} resource groups and O(B2)O(B^2) intervals, dense pressure evaluation with precomputed operation–group membership costs O((N+m)gB2)O((N+m)gB^2) per state. Evaluating the parent and candidate successors therefore yields the conservative per-decision bound Ttcap=O((At+1)(N+m)gB2).T_t^{cap}=O((A_t+1)(N+m)gB^2).

Episode-level capacity computation sums the per-decision bound over at most NN policy decisions. Reference schedules and fixed constraints are constructed once per instance. Counterfactual evaluations use deterministic updates and share the current-state encoder output.

We clarify that the timing previously labeled as horizon generation in Appendix G also covered initialization and capacity analysis. We have corrected this attribution in Appendix G. The breakdown below separates these components using non-overlapping intervals under matched hardware, batch sizes, and greedy decoding, with GPU synchronization and repeated measurements. Setup covers initialization and, for RCR, horizon generation and fixed-constraint construction. The CLC penalty is not applied during inference. All shared capacity computations are included in the reported capacity-analysis time. Times are reported per instance, and greedy gaps follow Tables 1 and 5.

SettingMethodGap (%)Setup (s)State (s)Capacity (s)Neural (s)Other (s)Total (s)
SD1 20 × 10RESCHED0.480.310.7400.980.092.12
SD1 20 × 10RCR-RESCHED−0.950.350.750.090.960.112.26
Taillard 15 × 15RESCHED15.70.270.6800.890.111.95
Taillard 15 × 15RCR-RESCHED14.90.300.690.080.910.102.08

Capacity analysis takes only 0.08–0.09 s per instance, accounting for 3.8–4.0% of RCR’s total runtime. Including setup, total runtime increases by 6.6–6.7%, while gaps decrease by 1.43 and 0.80 percentage points, respectively. These measurements support a favorable quality–runtime trade-off: the small additional computational cost provides improved scheduling quality on the evaluated settings. We have added a discussion of this point to Appendix G of the revised manuscript.

AuthorsOpenReview ↗

(2/3) Author Response: We clarify RCR's computational cost, statistical reliability, and applicability to FFSP.

Q2: Can you provide multi-seed results to assess the reliability of the modest gains on Taillard and DMU?

A2: About multi-seed reliability on Taillard and DMU:

We have extended the JSSP evaluation to five independent training runs per method. RESCHED and RCR-RESCHED were retrained in the same computing environment using the same five seed values and matching backbone configurations on 10 × 10 instances, then evaluated greedily on identical Taillard and DMU instances without fine-tuning. The baseline values below come from these matched reruns. Small differences from the originally reported values can arise across computing environments even with identical seeds.

All entries report mean ± standard deviation across the five training seeds. For benchmark summaries, each seed’s results are first averaged equally across the eight test sizes.

Benchmark/settingRESCHED gap (%), mean ± SDRCR-RESCHED gap (%), mean ± SD
Taillard, eight-size average17.10 ± 1.6116.54 ± 0.72
DMU, eight-size average26.92 ± 2.3426.66 ± 1.17
Taillard 30 × 1521.9 ± 2.0521.7 ± 0.98
DMU 40 × 2029.6 ± 2.6430.4 ± 1.22

RCR-RESCHED achieves lower benchmark-average gaps on both Taillard and DMU while approximately halving the observed standard deviations across the four reported settings. These results indicate lower variability across training runs alongside modest improvements in mean performance. The higher mean gap on DMU 40 × 20 shows that improvements are not uniform across settings.

Our primary focus is FJSP, where the benefits are broader and more pronounced: RCR improves 70/72 paired comparisons on synthetic datasets and 21/24 on public benchmarks across three backbones. For example, on SD2 20 × 5 under greedy decoding, RCR-RESCHED reduces the gap from 9.87% to 5.43%. The additional JSSP experiments extend this evaluation to fixed machine assignments, showing improved benchmark-average quality together with reduced variation across training seeds. We have expanded Appendix H.2 of the revised manuscript to address this point.

Q3: Can you provide results on FFSP, which was evaluated in the original RESCHED paper?

A3: About evaluation on FFSP:

We have extended the evaluation to FFSP. Each FFSP job retains an ordered operation chain, with eligible machines restricted to the parallel machines at each stage. Under the same append-only scheduling transition, RCR’s job-path and resource-capacity conditions remain applicable without changing the four-dimensional BCD or the CLC definition.

Following RESCHED’s original FFSP protocol, we consider three stages, four machines per stage, and processing times uniformly sampled from [2, 9]. Models trained on 20-job instances are evaluated on 20/50/100-job instances without retraining or fine-tuning. We retain the original decoding protocol, including 24 parallel solutions per instance, and use the default RCR hyperparameters. The table compares mean makespans against the RESCHED results reported in its original paper (Table 9), with lower values indicating better performance.

MethodDecodingFFSP20FFSP50FFSP100
RESCHEDGreedy26.6551.2492.28
RCR-RESCHEDGreedy24.2749.6890.33
RESCHEDSampling25.1249.6590.80
RCR-RESCHEDSampling24.0847.7389.64

RCR-RESCHED achieves lower mean makespans than RESCHED across all evaluated FFSP sizes under both greedy and sampling decoding. Improvements on the unseen 50- and 100-job instances further support cross-size generalization. These results demonstrate that capacity reasoning also benefits scheduling under shared stage routing, extending the empirical evidence for RCR beyond FJSP and JSSP. We have incorporated these additional results into Appendix H.3 of the revised manuscript.

AuthorsOpenReview ↗

(3/3) Author Response: We clarify RCR's computational cost, statistical reliability, and applicability to FFSP.

A4: About applicability beyond predefined job chains:

Encoder independence and scheduling-model applicability are distinct aspects of RCR. Our experiments establish compatibility across GNN/Transformer encoders and PPO/REINFORCE, with evidence from FJSP/JSSP and the additional FFSP evaluation reported above. For general precedence DAGs, the chain-based job-path conditions and temporal bounds require adaptation. A principled extension would compute valid earliest/latest bounds through forward/backward longest-path propagation, then compute demand for each resource group and interval without double-counting operations shared by multiple precedence paths. Certificate validity would additionally require capacity calculations consistent with the scheduling transition. We have clarified this scope and outlined the required adaptations in Appendix J of the revised manuscript.

A5: About the methodological contribution:

RCR’s contribution lies in converting shared analytical capacity conditions into complementary action-comparison and learning mechanisms. BCD compares candidate successors on a common parent-state constraint support, balances heterogeneous constraint families, and captures bottleneck redistribution through its KL component. CLC uses the complete constructed constraint set to provide a sound certificate of infeasibility relative to the reference horizon under the stated transition.

The component evidence supports these design choices: removing family balancing, local windows, additional resource groups, or the KL component worsens RCR-RESCHED on all four tested SD1 sizes (Tables 3 and 9). These results substantiate the proposed integration of capacity reasoning into policy learning, while the unchanged encoders and original policy-gradient algorithms demonstrate its compatibility with existing scheduling methods.

Comments on the paper

4 comments
AuthorsOpenReview ↗

(1/2) Author Response: We clarify CLC informativeness and compare RCR with extra sampling at matched runtime.

We thank the reviewer for recognizing RCR’s compatibility across schedulers, empirical improvements, and practical horizon construction. We address the reviewer’s questions with certificate diagnostics, a matched-runtime comparison, and penalty ablations.

W: Repeated penalties on successor violations also alter the training objective beyond terminal makespan, rather than forming a potential difference.

A: About the optimization bias of dense CLC penalties:

RCR retains the original makespan-oriented reward and adds an auxiliary penalty discouraging large and persistent certificate violations. Trajectories with similar final makespans can therefore receive different cumulative penalties. This optimization bias does not imply general policy invariance. We have clarified this distinction in Section 4.2 and Appendix F.2 and added the penalty comparisons to Appendix I.1 of the revised manuscript.

We compare four penalty variants while retaining BCD in DANIEL and RESCHED. Dense denotes the proposed CLC penalty, None removes CLC, Incremental uses signed certificate differences, and Terminal applies the penalty only at episode completion. Let Δt=Δ(st;H)\Delta_{t}=\Delta(s_{t};H) and write the auxiliary reward as −λqt/σ-\lambda q_{t}/\sigma. Results are mean instance-wise gaps on SD1 20×1020\times10 under greedy decoding.

Variantqtq_{t}DANIEL gap (%)RESCHED gap (%)
Dense (RCR)Δt+1/N\Delta_{t+1}/N0.18−0.95
None001.010.38
IncrementalΔt+1−Δt\Delta_{t+1}-\Delta_{t}0.770.03
Terminal1[t=T−1]ΔT\mathbf{1}[t=T-1]\Delta_{T}0.91−0.08

Dense CLC achieves the lowest mean gap on both backbones. Signed incremental and terminal penalties also improve over BCD alone, but less than dense CLC. Removing CLC worsens RCR-RESCHED on all four SD1 sizes in Table 3. These results support dense CLC as a useful auxiliary learning signal in the evaluated settings. The trajectory diagnostic in A1 below complements these ablations by characterizing the observed association between intermediate certificate values and final scheduling quality.

Q1: In the existing test trajectories, how often does the certificate activate, and how closely does its value relate to final makespan regret?

A1: About certificate activation and final scheduling quality:

Under Proposition 2’s assumptions, a positive CLC certifies that the current partial schedule cannot be completed within HH. A zero certificate does not guarantee completion within HH, and its magnitude is not established as a lower bound on makespan regret.

We report training and test activation rates for RCR-RESCHED on SD1 and SD2 20×1020\times10 under the default horizon. Activation is the percentage of evaluated decision steps with Δ>0\Delta>0. Training activation is averaged over the entire training process, covering all training iterations. Test activation is evaluated offline for diagnosis, as the CLC penalty is not applied during inference.

Using existing greedy test trajectories without retraining, we record the normalized certificate Δ/H\Delta/H for each instance after ⌊N/2⌋\lfloor N/2\rfloor of its NN operations have been assigned. Within each dataset, trajectories are divided into zero, smaller-positive, and larger-positive groups. Positive values at or below their median enter the smaller-positive group, while those above it enter the larger-positive group. Overall and subgroup gaps are mean final instance-wise percentage gaps computed from the same evaluation records, CP-SAT references, and instance weights.

SettingTraining activation (%)Test activation (%)Overall gap (%)Gap: zero CLC (%)Gap: smaller positive CLC (%)Gap: larger positive CLC (%)
SD1 20×1020\times107875−0.950.32−1.52−0.64
SD2 20×1020\times10746910.8211.919.5711.47

CLC is frequently active during both training and testing. Among trajectories with positive midpoint certificates, the larger-positive group has a higher mean final gap in both datasets. However, the zero-certificate group has the highest mean gap, so these results do not establish an overall monotonic relationship between certificate magnitude and final quality. CLC concerns completion within each instance’s horizon, whereas final gaps use CP-SAT references. These descriptive group-level comparisons do not establish causality or a quantitative makespan-regret bound. We have added these diagnostic results and their interpretation to Appendix I.3 of the revised manuscript.

AuthorsOpenReview ↗

(2/2) Author Response: We clarify CLC informativeness and compare RCR with extra sampling at matched runtime.

Q2: At a shared end-to-end inference time, including horizon generation and capacity evaluation, does RCR still improve over allocating extra samples to the original backbone?

A2: About additional sampling under a matched runtime budget:

We compare both approaches on SD1 20×1020\times10 using a target average end-to-end budget of 2.26 s per instance. RESCHED selects the best of five schedules: one greedy and four sampled. The sample count is selected through timing-only calibration. Both methods use the same hardware, test instances, and batching protocol. Timings include setup, inference, and solution selection, with GPU synchronization.

MethodDecodingPolicy-generated solutions/instanceTotal time (s/instance)Gap (%)
RESCHEDGreedy12.120.48
RESCHEDGreedy + additional sampling52.250.24
RCR-RESCHEDGreedy12.26−0.95

Additional sampling improves RESCHED’s mean gap from 0.48% to 0.24%. At closely matched runtimes of 2.25 and 2.26 s, RCR-RESCHED reduces the mean gap by 1.19 percentage points relative to the additional-sampling baseline. This supports better scheduling quality at the evaluated setting and budget.

We have corrected the timing attribution in Appendix G and provided a detailed runtime breakdown in Appendix G.3 of the revised manuscript. The 0.44 s labeled as horizon generation covered 0.35 s of setup, including initialization, horizon generation, and fixed-constraint construction, and 0.09 s of capacity analysis. Both are included in the unchanged total of 2.26 s.

AuthorsOpenReview ↗

General Response

We thank the reviewers for their careful assessment and constructive feedback. We have provided point-by-point responses and updated the manuscript to incorporate the principal analyses, additional experiments, and methodological clarifications. We summarize the main additions below.

  1. CLC's role and optimization bias. We clarify that BCD compares candidate successors on a common parent-state active constraint set using family-balanced weighting and KL-based bottleneck redistribution. CLC evaluates the full constructed set to provide complementary training guidance. RCR retains the original makespan-oriented reward and adds an auxiliary penalty. Under the stated assumptions, including a valid certificate and an attainable reference schedule, we show that adding CLC leaves the optimal schedules unchanged for undiscounted returns. This does not guarantee the same result for RESCHED's discounted returns. On SD1 20 × 10 with greedy decoding, dense CLC gives lower mean gaps than no CLC, signed incremental penalties, and terminal penalties for both DANIEL and RESCHED. These clarifications appear in Section 4.2 and Appendices F.2 and I.1.

  2. Reference-horizon quality and certificate diagnostics. Besides testing longer horizons with fixed models, we retrained RCR-RESCHED using four reference rules: SPT, MWKR, the better of the two, and the best schedule from a set of feasible schedules. Each model uses the same rule for training and testing. The default minimum yields an RCR gap within 0.03 percentage points of the portfolio result while using only two reference schedules (Appendix G.2). We also report activation averaged over the entire training process and offline test diagnostics. Under the default horizon, test-step activation is 75% on SD1 and 69% on SD2 for 20 × 10 instances. Across the midpoint groups, larger certificate values do not always mean larger final gaps to the CP-SAT references. We distinguish these descriptive observations from the certificate's formal guarantee concerning completion within the reference horizon (Appendix I.3).

  3. Scheduling-transition compatibility. We document the native transitions of all three evaluated backbones, including HGNN's event-driven dispatching. These environments preserve committed processing intervals and prevent subsequent assignments from starting before machine readiness. RCR retains these transitions and feasibility masks. We also explain why earlier-gap insertion would require adapted capacity calculations and valid temporal bounds (Appendix I.2).

  4. Computational cost and matched-runtime comparison. Appendix G.3 provides a complexity analysis and an end-to-end runtime breakdown. Capacity analysis accounts for 3.8–4.0% of total RCR-RESCHED runtime, with total overhead of 6.6–6.7% in the two evaluated settings. On SD1 20 × 10, RESCHED with one greedy and four sampled candidates achieves a 0.24% gap in 2.25 s, while greedy RCR-RESCHED achieves −0.95% in 2.26 s. This is a 1.19-percentage-point improvement at closely matched runtimes, with the conclusion restricted to this setting and budget.

  5. Statistical reliability and limitations. Matched five-seed JSSP evaluations show lower benchmark-average gaps and reduced observed training-run variability on Taillard and DMU (Appendix H.2). We also compare RCR with its backbone on the same test instances, count wins, ties, and losses, and use exact sign tests. The selected FJSP comparisons include the small gain on Edata and all three settings where RCR performs worse on average under greedy decoding. RCR-RESCHED on Rdata shows a significant win advantage after Holm correction across five comparisons (p = 0.0025).

  6. FFSP evaluation and applicability. Using the original RESCHED FFSP protocol, RCR-RESCHED trained on 20-job instances achieves lower mean makespans than the published baseline on 20-, 50-, and 100-job instances under both greedy and sampling decoding (Appendix H.3). We explain the adaptations required for general precedence DAGs (Appendix J).

  7. RCR gains on newer FJSP backbones. In the follow-up discussion, we compared the gap reductions from adding RCR to each backbone, giving equal weight to the six test sizes in Table 1. HGNN showed the largest average gains overall. The newer RESCHED backbone (ICLR 2026) gained more on average than DANIEL (IEEE TNNLS 2024) on both SD1 and SD2 under both greedy and sampling decoding. For example, on SD2 with greedy decoding, RCR reduced the average gap by 3.7 percentage points for RESCHED and 1.2 for DANIEL. Across the three backbones tested, RCR’s gains therefore did not consistently diminish with newer architectures.

The revised manuscript includes corresponding updates to the main text and appendices, with the principal additions highlighted in blue. We hope that our revised manuscript and responses will be considered in the overall assessment, and we welcome any remaining questions.

AuthorsOpenReview ↗

Kind Reminder on Our Response

Dear Reviewer,

Thank you for your time. We have addressed your concerns in our response and revised manuscript. We would welcome any further comments as the rebuttal period nears its end.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.