acceptodds
Under review as a conference paper at ICLR 2027

Scheduling with Heterogeneous Relations: Reinforcement Learning for Complex Hierarchical Manufacturing Systems

Abstract

Hierarchical manufacturing scheduling is particularly challenging in practice, as complex production structures and heterogeneous operational constraints give rise to tightly coupled decisions that extend substantially beyond the standard flexible job shop scheduling problem.To address this challenge, we propose CRST, a neural architecture that models scheduling states through multiple complementary relations. CRST performs relation-specific reasoning over workflow dependencies, machine competition, and reusable resource interactions, and then adaptively combines these complementary contexts through Relation Mix to measure the importance of these relations. A pair decoder directly evaluates feasible task machine assignments, while the environment enforces exact feasibility under hard scheduling constraints.Additionally, we introduce a decomposition strategy that substantially reduces memory consumption during large-scale inference while preserving global constraint consistency.Experiments show that CRST achieves solution quality comparable to CP-SAT on standard size instances and becomes more competitive on larger problems, outperforming CP-SAT under a fixed 30-minute search budget by up to 8.48% while requiring only tens of seconds of inference.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, hierarchical manufacturing scheduling, flexible job shop scheduling, heterogeneous relations, resource-constrained scheduling, neural combinatorial optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_766oOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a Constraint-Relational Scheduling Transformer (CRST) to solve the complex hierarchical manufacturing scheduling problem. CRST employs three relation-specific branches to model workflow, task–machine, and task–resource interactions, which are integrated through Relation Mix. A pair decoder scores feasible assignments, while an event-driven environment ensures feasibility and bounded-context decomposition reduces memory consumption during large-scale inference. Experimental results on four synthetic industrial-inspired scenarios demonstrate that CRST achieves competitive makespan performance compared with CP-SAT.

Critical strengths

S1: The proposed architecture has a clear motivation and a coherent design.

S2: The experimental results demonstrate promising performance on four synthetic datasets.

Critical weaknesses

W1: Recent learning-based scheduling methods [1,2] increasingly focus on developing unified solvers capable of handling multiple problem variants. However, CRST is designed and evaluated exclusively for a single hierarchical manufacturing scheduling problem. The authors are encouraged to evaluate CRST on other scheduling problems, such as standard FJSP and JSP, to demonstrate its versatility and generalizability.

W2: The manuscript lacks sufficient sensitivity analysis of key hyperparameters, particularly those associated with the proposed bounded-context decomposition strategy, such as the context size, action-core size, and rolling commitment interval.

W3: The presentation of Figure 1 could be improved. A clearer vector-based illustration would make the overall architecture easier to follow and help readers better understand the workflow of the proposed model.

[1] RESCHED: Rethinking flexible job shop scheduling from a transformer-based architecture with simplified states. ICLR 2026.

[2] Towards a Unified Model for Flexible Job Shop Scheduling Problems. NeurIPS 2026.

Questions for authors

see Weaknesses

2 comments
AuthorsOpenReview ↗

Response to Reviewer 766o

We thank the reviewer for the constructive comments. Our responses are given below.

W1

Our goal differs slightly from unified multi-problem solvers [1,2]: rather than covering many problem classes with one model, CRST targets a family of FJSP variants with workflow, machine, and resource constraints. Standard FJSP is a special case of this family, and JSP is a further special case with a single eligible machine per operation, so CRST applies to them without architectural changes. Following the reviewer's suggestion, we tested CRST in two additional settings.

(1) Standard FJSP. We compared CRST with the recent learning-based FJSP methods DANIEL and ReSched on the DPP, Fattahi, and Hurink benchmarks. CRST obtains the lowest gap on some sets at comparable runtime (gap %, runtime):

BenchmarkCRSTDANIELReSched
Dauzère6.84 (29.48s)9.42 (25.30s)11.49 (27.45s)
Fattahi5.94 (0.54s)6.31 (1.19s)6.36 (1.24s)
Hurink-edata7.28 (12.21s)8.72 (11.36s)8.13 (11.41s)
Hurink-rdata6.81 (11.93s)4.95 (11.53s)4.92 (11.55s)
Hurink-vdata1.30 (11.61s)0.69 (12.69s)0.69 (12.60s)
Hurink-edata is derived from classical JSP instances with only a few alternative machines per operation and is therefore close to JSP; CRST is also best on this set.

(2) A different real-world problem. We further applied CRST, without retraining, to the published aircraft disassembly benchmark of Thomas and Schaus (2026), built from real operational data. It contains constraints that CRST does not model (technician capacity per location, technician unavailability, and mass balance); these are enforced by the environment through action masking and delayed start times, while the network is used unchanged. Gaps are relative to the authors' published CP Optimizer results (all constraints, 1 h):

Instance#OpsCRST makespan (gap)CRST time (s)CP Optimizer (1 h)
B737NG600-101064 (+0.0%)1.964
B737NG600-151564 (+0.0%)0.564
B737NG600-2020128 (+96.9%)0.665
B737NG600-3030128 (+88.2%)0.968
B737NG600-4040128 (+40.7%)1.291
B737NG600-5050128 (+37.6%)1.593
B737NG600-7575128 (+12.3%)2.3114
B737NG600-100100128 (+9.4%)3.8117
B737NG600-150150175 (+10.1%)4.7159
B737NG600-200200190 (+3.3%)6.1184
B737NG600-300300259 (+3.6%)9.7250
B737NG600-400400301 (+4.9%)15.1287
B737NG600-600600433 (+3.1%)32.0420
B737NG600-800800510 (+1.0%)57.6505
B737NG600-12001200843 (+1.1%)144.7834
B737NG600-14541454989 (+1.6%)235.3973

On instances with 200 or more operations, CRST is within 1.0–4.9% of CP Optimizer while using at most 236 s instead of 1 h.

W2

We varied the context size H, the action-core size A, and the rolling commitment interval S one at a time around the default (H = 200, A = 150, S = 50). Changes are relative to the default, with paired 95% bootstrap CIs:

SettingΔ makespan95% CIRuntime
H = 150+0.24%[−0.66, 1.12]33.6 s
H = 500−0.12%[−0.94, 0.71]53.9 s
H = 1000+0.19%[−0.61, 0.83]72.5 s
A = 50+90.60%[85.39, 95.27]40.6 s
A = 75+2.30%[1.02, 3.64]36.7 s
A = 100+0.15%[−0.74, 0.95]36.6 s
A = 200+0.09%[−0.76, 0.85]36.1 s
S = 10+0.71%[−0.22, 1.66]45.5 s
S = 100+0.05%[−0.67, 0.81]34.6 s
S = 125+1.08%[0.46, 1.68]34.0 s
S = 150+36.65%[32.74, 40.78]34.7 s

Two observations follow. First, H has no significant effect on quality across 150–1,000, while peak GPU memory grows from 50.6 MB to 403.8 MB, so a small context is sufficient. Second, A and S matter only through the overlap A − S, i.e., the planned tasks that are not committed and can be replanned in the next window. Whenever A − S ≥ 50, makespan stays within 0.71% of the default; with overlap 25 (A = 75 or S = 125) it degrades by 1–2%, and with no overlap (A = S) it degrades sharply. The method is therefore robust over a wide range of settings, provided that some overlap is retained. We will add these results to the appendix.

W3

Thank you for the suggestion. We will redraw Figure 1 as a clearer vector graphic in the revised version, so that the overall architecture and workflow of CRST are easier to follow.

Thank you for your responses. I will maintain my original rating.

Reviewer_CEgwOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies a hierarchical manufacturing scheduling problem that extends standard FJSP with process-stage-task structures, parallel tasks within stages, cross-process precedence, machine compatibility and exclusivity, machine rest periods that pause and resume tasks, and reusable resource capacities. Its main contribution is CRST, a heterogeneous relational scheduling framework that separately models workflow, task-machine, and task-resource relations, adaptively combines them through Relation Mix, and scores feasible task-machine pairs with a pair-level decoder, while an event-driven simulator enforces hard feasibility so the policy only ranks legal assignments. For large-scale inference, a bounded-context decomposition limits only the neural observation while keeping global machine, resource, precedence, and calendar states consistent. On 200-task benchmarks, CRST with sample-64 decoding reaches a 1.12% average gap to a 30-minute CP-SAT reference. On 500-task and 1000-task instances, greedy CRST beats the same fixed-budget CP-SAT reference by 8.59% and 7.00% while requiring only 27.48 s and 35.44 s. On 2000-task instances, decomposition cuts peak GPU memory to 5.61% of full-graph level with a 0.48% makespan increase. Ablations support all three relational views, Relation Mix, and pair-level decoding.

Critical strengths
  1. The FJSP variant is more realistic.
Critical weaknesses
  1. The benchmark is synthetically generated, lacking public benchmarks or real cases to assess the effectiveness of the proposed method.
  2. The bounded-context decomposition seems a critical design for the method to scale up to the large scale instances. However, its configurations, e.g., H, A, and S are not provided with ablation studies.
  3. The bounded-context decomposition make the whole decision problem a partially observed MDP, why don't we try some POMDP methods?
  4. A systematic study on the level of exposures of the bounded-context decomposition should be provided to understand the mechanism of how this key component affact the overall performance.
  5. Lacking real cases from real industry can not fully assess the effectiveness of the proposed method. As the authors stated, the paper try to solve a more realistic FJSP variants with real features, so it is strange that the authors did not evaluate CRST on real problem instances.
  6. The idea of bounded-context decomposition is not new, for example in https://openreview.net/forum?id=s5pWbwf2tk, the aurhors also applied a similar strategy.
  7. Least but most important. To the community, I think it is dangerous for us to makeup a “more challenging problem variant” and then design a tailored method to solve it without evaluation the critialness and value of the proposed problem. If we encourage such publications, it is a bad signal for the community, so we should avoid this together.
Questions for authors
  1. Do we have open benchmark for this scheduling problem? Or the real dataset from the industry. I would like to see the results on these datasets.
  2. Can CRST solve standard FJSP problems? If so, what is the performance compared with the SOTA baselines on FJSP?
  3. We do not know whether CP-SAT is the best to-compare-against baseline here, for this kind of specific FJSP variant, why do you choose CP-SAT as the baseline solvers? Do we consider any other options?
  4. Meta-heuristic is one of popular familes of solvers for FJSP and its variants. I would like to see the perforamnce compare with them.
8 comments
AuthorsOpenReview ↗

Response to Reviewer CEgw (1/4): Motivation and related industrial problems

We sincerely thank the reviewer for the careful reading and constructive comments, which have helped us improve the paper. In response, we have clarified the industrial motivation of our problem, added results on standard FJSP benchmarks and on a published real-world aircraft disassembly benchmark, provided ablation studies of the decomposition parameters (H, A, S), and extended the baseline comparisons with Gurobi and a metaheuristic (2SGA). Our point-by-point responses are given below.

W7

We agree with the reviewer that introducing artificial difficulties without practical motivation should not be encouraged. However, we would like to clarify that the problem studied in this paper arose from scheduling requirements encountered in our collaborations with manufacturing companies. In these settings, production workflows are organized into successive stages, each containing one or more executable tasks. This observation motivated the process–stage–task representation used in our study.

Further examination of publicly available industrial documentation shows that such hierarchical organization extends beyond our collaborating companies. For example:

SAP describes production recipes as collections of operations, with each operation further divided into executable phases performed by operators or machines. Siemens Teamcenter Easy Plan explicitly supports hierarchical operations, parallel activities, and operation sequencing within its Bill of Process, together with the association of production resources with individual operations. Airbus describes A321XLR final assembly as a sequence of assembly stations, each involving multiple installation, assembly, or testing activities. Although the terminology and level of detail vary across these examples, they provide concrete industrial support for representing production through hierarchical workflows. In our formulation, the process–stage–task hierarchy captures a class of such workflows with parallel tasks and synchronization between successive stages. The practical scheduling challenge is to coordinate these dependencies while multiple processes compete for machines and reusable resources.

Beyond industrial documentation, several scheduling problems studied in the literature are close to ours. Similar structures appear in shipbuilding (Jeong et al., 2020; Pernas-Álvarez and Crespo-Pereira, 2023), railway maintenance (Torba et al., 2024), aircraft disassembly (Thomas and Schaus, 2026), glass and semiconductor manufacturing (Alvarez-Valdes et al., 2005; Deenen et al., 2023), and integrated production–maintenance (Geurtsen et al., 2024). For example, a ship block can be assembled only after its subblocks (cross-process precedence), and a photolithography operation cannot start on an idle machine if its reticle is in use (shared auxiliary resource). Table R1 summarizes these correspondences.

Table R1. Correspondence between industrial applications and the features of our formulation (✓: explicitly present; ○: partially or implicitly present; –: not reported)

ApplicationMulti-stage workflows with parallel tasksCross-process precedenceMachine restShared / auxiliary resourcesResource availability restrictions
our work✓✓✓✓✓
Shipbuilding (Jeong et al., 2020; Pernas-Álvarez & Crespo-Pereira, 2023)✓✓-✓○
Aircraft disassembly (Thomas & Schaus, 2026)○–○✓○
Glass manufacturing (Alvarez-Valdes et al., 2005)✓○○✓–
Semiconductor photolithography (Deenen et al., 2023)––○✓○
Production–maintenance (Geurtsen et al., 2024)––✓–✓

At the same time, each of these problems has its own domain-specific constraints, such as aircraft mass balance or buffer capacity in shipyards, and none exhibits all features of our formulation. Our problem can therefore be viewed as an abstraction and distillation of these problem classes: it retains the structure they share while omitting domain-specific details, and our partner's system exhibits all of these features simultaneously.

Existing studies have addressed operation splitting, sublot synchronization, and multi-resource scheduling. Building on this background, our study investigates how a learned scheduling policy can jointly account for workflow dependencies, machine alternatives, shared-resource capacities, and machine availability calendars.

We have expanded the Introduction to explain this industrial background, clarify the relationship to established scheduling formulations, and make the motivation and scope of our study more explicit.

AuthorsOpenReview ↗

Response to Reviewer CEgw(2/4): Real-world data

  1. W1.
  2. Q1.
  3. W5.

We agree that public or real data are preferable. However, to our knowledge, no existing public benchmark or open-source real-world dataset closely matches our problem: FJSP benchmarks (e.g., Brandimarte, Hurink) contain only linear job sequences and machine constraints, while RCPSP benchmarks (e.g., PSPLIB) lack flexible machine assignment and interdependent workflows. Moreover, our industrial partner, for confidentiality reasons, does not permit its original data to appear in the paper, so we developed an instance generator calibrated on the partner’s real production data.

On the other hand, since no testbed exists for such FJSP variants, we also intend this benchmark as a resource for future research: following the practice of Taillard, Brandimarte, Hurink, and PSPLIB, we will release the generator and all instances upon acceptance. Together with our FJSP results, CRST is thus evaluated on both public and industrially calibrated instances; the industrial origin of the problem is discussed in our response to W7.

We also evaluate on a published industrial problem that is structurally close to ours: the aircraft disassembly scheduling problem of Thomas and Schaus (2026), whose instances are derived from real operational data. As in our setting, precedence-constrained tasks require qualified technicians and capacity-limited work locations, so a task whose predecessors are finished may still have to wait for an occupied resource. Some constraints of this benchmark are, however, not modeled by CRST: location capacity measured in technicians, technician unavailability and mass balance. We handle them without retraining: the network is used unchanged, while the scheduling environment masks infeasible actions and delays start times as needed, so every constructed schedule satisfies the original constraints. The results therefore measure zero-shot transfer to a constraint class outside CRST's scope. Results are shown below.

Instance#OpsCRST (sample16) makespan (gap)CRST time (s)CP Optimizer (1 h) makespan
B737NG600-101064 (+0.0%)1.964
B737NG600-151564 (+0.0%)0.564
B737NG600-2020128 (+96.9%)0.665
B737NG600-3030128 (+88.2%)0.968
B737NG600-4040128 (+40.7%)1.291
B737NG600-5050128 (+37.6%)1.593
B737NG600-7575128 (+12.3%)2.3114
B737NG600-100100128 (+9.4%)3.8117
B737NG600-150150175 (+10.1%)4.7159
B737NG600-200200190 (+3.3%)6.1184
B737NG600-300300259 (+3.6%)9.7250
B737NG600-400400301 (+4.9%)15.1287
B737NG600-600600433 (+3.1%)32.0420
B737NG600-800800510 (+1.0%)57.6505
B737NG600-12001200843 (+1.1%)144.7834
B737NG600-14541454989 (+1.6%)235.3973
AuthorsOpenReview ↗

Response to Reviewer CEgw (3/4): Bounded-context decomposition

  1. W2.
  2. W3.
  3. W4.
  4. W6.

We thank the reviewers and clarify the novelty, motivation, and evidence of our decomposition below.

There may be some misunderstanding of our decomposition method. We believe it is important to distinguish between simplifying the state representation of the remaining problem and selecting a bounded context from the unscheduled tasks. ReSched falls into the former category, whereas our mechanism belongs to the latter. Both involve representing a subproblem, but the cited work is substantively different from the bounded-context inference adaptation mechanism studied in this paper. We agree that decomposition itself is not a new concept. However, existing decomposition methods mainly either use neural networks to learn how to decompose the problem or integrate decomposition into CP-based solution methods. None of them provides what we propose: a training-free, inference-time decomposition framework that adapts an existing, frozen learning-based scheduling policy.

We designed the decomposition to speed up inference and reduce GPU memory, so that the method can run on low-end hardware and handle large-scale instances. It uses constraint-safe rolling decomposition to adapt a trained, frozen heterogeneous-graph schedule generator to instances far larger than those seen during training. We have also conducted a sensitivity analysis of H, A, and S, which shows that the hyperparameters of our decomposition are robust across a wide range of values.

We agree that restricting the context introduces partial observability. To reduce this information loss, we varied H from 150 to 1,000 (A = 150, S = 50). Relative to the default H = 200, makespan differed by at most 0.43%, with all paired 95% bootstrap CIs including zero; H = 1,000 changed it by only +0.186% while doubling runtime (36.32 → 72.46 s) and raising peak GPU memory from 63.64 MB to 403.78 MB. Thus, a nearly global context brings no consistent gain but largely removes the computational benefit of decomposition. Moreover, our H × A × S experiments show that even with H = 1,000, committing too many tasks at once significantly degrades quality. What matters is preserving room for adjustment across windows: each iteration plans A tasks but commits only S, so the remaining A − S can be replanned later. POMDP methods with explicit belief states remain a worthwhile direction, but they typically require retraining, whereas we keep the CRST policy unchanged and adapt it solely through inference-time decomposition.

A=150,S=50:

HAverage MakespanRelative to Default95% Confidence Interval (CI)Average RuntimeAverage GPU Memory UsageSpeedup
1506751.25+0.239%[-0.660%, 1.124%]33.64 s50.58 MB1.080
2006746.250.000%[0.000%, 0.000%]36.32 s63.64 MB1.000
3006726.25-0.248%[-0.998%, 0.431%]42.26 s91.47 MB0.859
4006772.15+0.430%[-0.581%, 1.381%]48.02 s123.38 MB0.756
5006738.70-0.120%[-0.937%, 0.709%]53.94 s160.98 MB0.673
6006749.80+0.028%[-0.813%, 0.725%]59.41 s200.00 MB0.611
7006738.25-0.000%[-0.812%, 0.699%]64.26 s245.74 MB0.565
8006756.20+0.135%[-0.393%, 0.702%]68.08 s300.20 MB0.533
9006759.10+0.225%[-0.505%, 0.923%]71.24 s347.76 MB0.510
10006758.80+0.186%[-0.609%, 0.833%]72.46 s403.78 MB0.501

H=200,S=50:

AAverage MakespanRelative to Default95% Confidence Interval (CI)Average Runtime
5012726.55+90.595%[85.385%, 95.273%]40.58 s
756880.00+2.302%[1.020%, 3.644%]36.70 s
1006748.80+0.148%[-0.743%, 0.949%]36.63 s
1256775.80+0.549%[-0.119%, 1.255%]36.70 s
1506746.250.000%[0.000%, 0.000%]36.32 s
1756759.10+0.349%[-0.797%, 1.608%]36.27 s
2006743.70+0.088%[-0.757%, 0.849%]36.11 s

H=200,A=150:

SAverage MakespanRelative to Default95% Confidence Interval (CI)Average Runtime
106788.60+0.709%[-0.218%, 1.657%]45.50 s
256779.90+0.437%[-0.208%, 1.140%]38.75 s
506746.250.000%[0.000%, 0.000%]36.32 s
756733.55-0.011%[-1.016%, 0.928%]35.02 s
1006740.60+0.054%[-0.667%, 0.809%]34.63 s
1256814.20+1.077%[0.459%, 1.681%]33.96 s
1509229.10+36.647%[32.744%, 40.778%]34.69 s
Reviewer_yvihOpenReview ↗
Rating
4
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes an original architecture for complex scheduling problems. It outperforms CP-SAT and other approaches for large instances.

Critical strengths
  • Very good results on complex instances
  • Addresses real life scheduling problems with success
  • A detailed presentation of the architecture
Critical weaknesses
  • I am not sure to understand well enough how the Input Embedding is generated, a figure could help.
Questions for authors
  • Can you give simple explanations of the architecture of the relational encoder?
2 comments
AuthorsOpenReview ↗

Response to Reviewer yvih

We thank the reviewer for the positive assessment and for pointing out that the input embedding and the encoder can be explained more clearly. We give a simpler description below. We have also added a figure illustrating how the input embedding is generated to Appendix E (CRST Architecture Details) of the revised manuscript.

Weakness

At every decision step, the current partial schedule is converted into a graph with three types of nodes: unfinished tasks, machines, and shared ResourcePools (e.g., a worker team or a tool set). Each node is described by a few hand-crafted numbers, with all times divided by the mean processing time so that the features are scale-free:

  • Task (4): time until it can start, shortest feasible processing time, remaining critical path to completion, and rigidity (1 / number of eligible machines).
  • Machine (3): time until it is next available, length of its current working window, and workload pressure.
  • ResourcePool (3): fraction of members free now, time until the earliest member is free, and remaining demand relative to capacity.

Each node type has its own linear layer followed by LayerNorm, which maps these small vectors into the same 128-dimensional space (Eq. 51). We use separate layers because, for example, "time until available" means different things for a task and a machine.

Relations are not turned into nodes. They are used later inside the encoder: task–task relations (predecessor/successor, graph distance, same or different process) act as attention biases, and task–machine and task–resource edges (processing time, earliest completion time, resource demand, holding time) condition the corresponding attention. The overall flow is:

partial schedule
 -> node features (task 4, machine 3, pool 3) + edge features
 -> type-specific projection to 128-d embeddings
 -> 3 relational encoder blocks (edges used inside attention)
 -> pair decoder scores every feasible (task, machine) pair
 -> chosen assignment is applied; features are recomputed

Question

Each encoder block updates every unfinished task by looking at it from three angles, kept in separate branches:

  1. Workflow: which tasks come before and after it in the production workflow.
  2. Machines: which machines can process it, and how long it would take.
  3. Resources: which shared resources it needs, and how busy they are.

Relation Mix then merges the three views, and each task learns how much weight to give each one. Machines and ResourcePools are updated in the reverse direction, by collecting the demand of the tasks that want them. With three stacked blocks, a task can also "see" other tasks that compete for the same machine or resource. The pair decoder then uses these embeddings to score each feasible task–machine assignment.

The new figure in Appendix E illustrates this process.

Reviewer_CEgwOpenReview ↗

React on the reviews on this reviewer

The comments from this reviewer is much less informative and constructive. You should give more detailed and useful comments to help the authors improve on their paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.