RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States
Authors: Xiangjie Xiao
Cong Zhang
Wen Song
Zhiguang Cao
Venue: ICLR 2026 Poster (2026)
Keywords: Flexible Job Shop Scheduling Problem; Deep Reinforcement Learning; Transformer Architecture ;
Primary area: optimization

Abstract: Neural approaches to the Flexible Job Shop Scheduling Problem (FJSP), particularly those based on deep reinforcement learning (DRL), have gained growing attention in recent years. However, existing methods rely on complex feature-engineered state representations (i.e., often requiring more than 20 handcrafted features) and graph-biased neural architectures. To reduce modeling complexity and advance a more generalizable framework for FJSP, we introduce \textsc{ReSched}, a minimalist DRL framework that rethinks both the scheduling formulation and model design. First, by revisiting the Markov Decision Process (MDP) formulation of FJSP, we condense the state space to just four essential features, eliminating historical dependencies through a subproblem-based perspective. Second, we employ Transformer blocks with dot-product attention, augmented by three lightweight but effective architectural modifications tailored to scheduling tasks. Extensive experiments show that \textsc{ReSched} outperforms classical dispatching rules and state-of-the-art DRL methods on FJSP. Moreover, \textsc{ReSched} also generalizes well to the Job Shop Scheduling Problem (JSSP) and the Flexible Flow Shop Scheduling Problem (FFSP), achieving competitive performance against neural baselines specifically designed for these variants.

Published as a conference paper at ICLR 2026
RESCHED: RETHINKING FLEXIBLE JOB SHOP
SCHEDULING FROM A TRANSFORMER-BASED ARCHITECTURE WITH SIMPLIFIED STATES
Xiangjic Xiao', Cong Zhang", Wen Song", Zhiguang Cao
School of Computing and Information Systems, Singapore Management University, Singapore Cooleeee of Computing and Data Science, Nanyang Technological University, Singapore 'Institute Marine Science and Technology. Shandong University, China
edu sg, cong . 9aaann920@mmii com, wensong@email. sdu. edu. cn, zgcaol sm..lmmmueeee sg
wi.xiao.... 202 4ephdcs.
ABSTRACT
Neural approaches to the Flexible Job Shop Scheduling Problem (FISP), partic- ularly those based on deep reinforcement learning (DRL), have gained growing attention in recent years. However, existing methods rely complex feature- engineered state representations (i.e., often requiring more than 20 handcrafted features) and graph-biased neural architectures. To reduce modeling complexity and advance a more generalizable framework for FISP, we introduce RESCHED, minimalist DRL framework that rethinks both the scheduling formulation and model design. First, by revisiting the Markov Decision Process (MDP) formu- lation of FJSP, we condense the state space to just four essential features, elimi- nating historical dependencies through a subproblem-basee -ased perspective. Second, we employ Transformer blocks with dot-product attention, augmented by three lightweight but effective architectural modifications tailored to scheduling tasks. Extensive experiments show that RESCHED outperforms classical dispatching rules and state-of-the-an DRL methods FJSP. Moreover, RESCHED also gener- alizes well the Job Shop Scheduling Problem (JSSP) and the Flexible Flow Shop Scheduling Problem (FFSP), achieving competitive performance against neural baselines specifically designed for these variants.
INTRODUCTION
The Flexible Job Shop Scheduling Problem (FISP) is a fundamental combinatorial optimization problem (COP) with widespread applications in manufacturing (Ding et al., 2019; Wang et al., 2024a), edge computing (Luo et al., 2021; Yang et al., 2025), and logistics (SAT, 2014; Arunarani et al., 2019). In FJSP, jobs decomposed into sequences of operations, each processable by set of compatible machines. Solving FJSP entails two coupled decisions: assigning operations to machines and sequencing them each machine. As generic model, FISP unifies multiple scheduling sce- narios: it reduces to the Job Shop Scheduling Problem (JSSP) when machine assignments are fixed, and the Flexible Flow Shop Scheduling Problem (FFSP) when jobs follow shared processing stage but retain machine flexibility. This inherent generality makes FISP a critical framework for diverse real-world systems.
Recent research has leveraged Deep Reinforcement Learning (DRL) to construct scheduling heuris- ties (Feng et al., 2021; Lei al., 2022), typically representing partial solutions (states) via disjunc- tive graphs (Blažewicz et al., 2000) enriched with complex node features. However, many of these features are redundant! and incorporating historical construction data into the current state can para- doxically degrade learning (see Section 4.2).. Furthermore, pruning unpromising actions based on human heuristics (Song et al., 2023; Wang et al., 2024b; Zhao et al., 2025), while intended to boost
Corresponding author. For instance, we demonstrate in Appendix B.3 using DANTEL. (Wang al., 2024b) that removing half of the input features does compromise performance.

---

Published as a conference paper at ICLR 2026
efficiency, often hampers policy generalization and yields suboptimal solutions (see Appendix B.3). These practices necessitate persistent tracking of auxiliary variables at every step, introducing sig- nificant computational overhead. Architecturally, most DRL approaches rely Graph Attention Networks (GATs) (Velickovic et al., 2017), which impose rigid inductive biases: capturing long- range dependencies requires deep stacking, while linear attention mechanisms struggle to model complex non-local scheduling interactions. These limitations prompt a central question: Can we de- sign a general construction policy, derived minimal Markov-sufficien state and implemented with generic yet expressive architecture, that generalizes naturally to FJSP variants?
We address this by proposing RESCHED, DRL framework that unifies minimalist state design with flexible neural modeling to achieve state-of-ther of-tthe-at (SOTA) performance. We demonstrate that ensuring state sufficiency reduces the need for heavy architectural inductive bias. Our formulation introduces compact state representation comprising only four core node features and graph struc- ture that explicitly encodes intra-job dependencies, thereby eliminating the need for historical track- ing. To enhance representational power, we replace conventional GNN-based policies (Franco et al., 2009) with a Transformer backbone featuring two complementary branches: self-attention for opera- tions and tross-aftention for machines. Applying Transformers to FISP presents specific challenges: self-attention must capture process constraints without extra parameters, while cross-attentii must handle indirect adge-feature integration and severe aperation-machine imbalance (often exceeding 10:1). We overcome these by incorporating Rotary Positional Encoding (RoPE) for intra-job se- quencing and determining a novel cross-attention module that directly embeds edge features while using self-connections to mitigate representation dilution. Empirical results show that RESCHED establishes a new SOTA on FJSP, outperforming both handcrafted heuristics and leading DRL base- lines. Crucially, it generalizes robustly across problem sizes, datasets, and variants (JSSP, FFSP), proving that minimalist design coupled with expressive modeling enables broad applicability. Our key contributions are:
We revisit the MDP for FJSP to design a compact state representation with only four essen- tial node features. By utilizing graph structure that explicitly encodes intra-job relation- ships, we eliminate redundant features, historical dependencies, and auxiliary variables.
We introduce a brancb Transformer architecture tailored for scheduling. It features self-attention enhanced by RoPE to model intra-job dependencies, and a novel cross- attention module that directly integrates edge features while mitigating operation -arratiinnmmccineee imbalance through seff-connections.
We demonstrate that RESCHED achieves SOTA performance on FJSP benchmarks while exhibiting strong generalization capabilities across varying problem sizes and scheduling variants, including JSSP and FFSP.
2 RELATED WORK
Priority dispatching rules (PDRs) (Haupt, 1989; Sels et al., 2012) are widely used in real-world FJSPs for their simplicity, interpretability, and fast decision-making, However, designing effective and generalizable PDRs remains challenging, as they often rely on domain expertise and fail to adapt across diverse problem instances. This limitation has motivated surge of interest in learning PDRs through deep reinforcement learning (DRL). Most DRL-based methods formulate FJSP as a dis- junetive graph, where nodes represent operations and machines, and edges encode precedence and assignment constraints. Graph neural networks (GNNs) are then employed to capture the complex relationships among operations and machines. For example. Song et al. (2023) proposed HGNN, a heterogeneous GNN tailored for FJSP; Wang et al. (2024b) introduced a dual-attention mechanism to jointly model operation and machine features; and Zhao et al. (2025) developed a GNN-based approach augmented with reward shaping to improve training efficiency. While effective, these methods typically depend on heavily engineered state representations, which limit scalability and generalization. Beyond FJSP, DRL has also been applied to other scheduling variants. For instance, Zhang et al. (2020) proposed a GNN-based DRL framework for JSSP that learns operation se- quencing policies, and Kwon et al. (2021) introduced a mixed-score attention mechanism to model operation operation-machine machine interactions in FFSP. These works further highlight the growing role of neural methods in advancing data-driven scheduling.
2

---

Published as a conference paper at ICLR 2026
3 PRELIMINARY
3.1 FLEXIBLE JOB SHOP SCHEDULING PROBLEM (FJSP)
Consider generic scheduling problem with operations fundamental units. Suppose there are two sets: a set of operations O = {O1, ...... On Each operation O₂ can be processed by one of the machines in M with a specific duration (process- ing time) D > O. In FISP, jobs are collections of operations that must be executed sequentially. Each job J, consists of several operations, so operations can be represented as Ozj, where denotes the job index and represents the position of the operation in job i. Each operation Oiz can be processed by one or multiple machines, which means "flexible", from compatible machine set Mij S .M with duration D > O. Meanwhile, the FJSP is subject to several important constraints: (1) An operation can only begin after all its preceding operations in the job sequence have been completed. (2) Each operation must be assigned
and a set of machines M {M,.M,,..... My...., Mm
single eligible machine and executed non- preemptively, without interruption once started. (3) Each machine processes only one operation at time, requiring sequential execution without overlap. The objective of FJSP is to find feasible solution that satisfies all the above constraints while minimizing the overall makespan, which is de- fined as the maximum finish time among all operations. Moreover, the transformation of FJSP to other variants like JSSP and FFSP are presented in Appendix A.2.
3.2 TRANSFORMER BLOCK
The Transformer block (Vaswani et al., 2017) is fundamental component designed to capture dependencies in sequential data. primarily consists of multi-head attention (MHA) mechanism and ferwafo network (FFN), combined with residual connections and layer normalization (He et al., 2016; Ba et al., 2016). the attention mechanism, each element attends to all others through weighted combination of their representations. For given input sequence h [/1, 1/i,hg.... hn]. the attention weights are computed by measuring the similarity between query 4a E Id and keys ko Rd typically obtained via learned linear projections of ht and hys The normalized attention weight 0, from node to node b, and the resulting embedding h2 for node a are computed as follows (head is omitted for brevity):
(gas ku) Vd
Okabb = softmaxy
1/= = Σ Rabb
(1)
where ()-) denotes the dot product, vdl is scaling factor stabilize training, and R is the value vector corresponding to node b. The outputs from multiple heads are concatenated and passed through linear transformation form the final MHA output, which is then processed by position-wil -wise FFN, with residual connections and layer normalization applied after both the atten- tion and FFN sub-layers. This structure allows the Transformer block effectively capture global dependencies and complex interactions among elements in the input.
4 METHODOLOGY
In this section, we introduce ReSched, construction-type neural framework designed for solving scheduling problems. We begin by revisiting the problem formulation, focusing the Flexible Job Shop Scheduling Problem (FISP), generalized model that captures diverse scheduling scenarios. Within this formulation, we cast scheduling a Markov Decision Process (MDP), where each decision step resolves a subproblem using a compact, task-specific state representation. Building on this MDP, we develop Transformer-basee policy network cquipped with structure-aware attention mechanisms and trained via reinforcement learning.
4.1 STATE REPRESENTATION
In our framework, we aim to minimize the complexity the state representation while ensuring remains fully expressive and sufficient to guide optimal scheduling decisions.
3

---

Published as a conference paper at ICLR 2026
Staiie D Mo.
M6
Mil
Instance
Beast on 2110
AT ATg-and AT
State St +
State
FiSh Formulatio
Networkk
On
Selutonn Voll
6..
OFORO
Materpand 2
Fired
(b)
Figure 1: (a) Illustration of the formulation for a 2-job, 2-operation, 2-machine (2-2-2) FISP in-
stance. (b) Changes in topology and O2M/O20 Connection between two steps for 3-3-3 instance.
4.1.1 REVISITING THE SCHEDULING FORMULATION
We represent FJSP instance using a heterogeneous disjunctive graph (Song et al., 2023), as illus- trated in Figure la. solution to FJSP consists of two key components: assigument and order. To evaluate solution quality, an explicit formulation is required to compute the makespan.
Let dr,i E (0, } indicate assignment Oiş to machine m at step L. ensure only one operation-
machine pair is scheduled per step, we enforce a constraint: ΣmEm Eiieo o 1, Vt. When th = 1, the finish time FT. is computed as:
FT. = max IT, + Diy, i = 1,
AT. [FTry if af =1 (ATT otherwise.
Here, FTgg-1) denotes the finish time of the preceding operation in job J. ATT" is the available time of machine m at step I, and (i'j') is the operation assigned to machine m at the previous step. The goal of FISP is minimize the maximum finish time across all operations, which is defined as FTaaxx = max FT.j. This unified formulation supports our state representation simplification, and it can also be adapted JSSP and FFSP by appropriately modifying machine assignment rules. For the sake of space, the detailed mathematical formulation of FISP and its variants are deferred to Appendix A.
Looking at Figure la again, it illustrates how two different solutions for the same FISP instance are translated, via the above formulation, into concrete Gantt charts and makespan values. Specifi- cally, the top solution with order [O11, O12, O21, Ozz] and assignment [M2, Mi, M2, Mi] results in a makespan of FTTax = 7. while the bottom solution with order [O11, O21. O12, O22] and assign- ment [M2, M1, M2, M2] achieves makespan of FTmax 6.
4.1.2 MDP FORMULATION
As a construction method, the scheduling process can be viewed as a sequential decision making problem, where the agent iteratively selects operation-machine pair to assign each step. This leads to a natural formulation the scheduling problem as an MDP.
State: Minimal Representation According to Eq. (2), computing the finish time for operation Og step requires three pieces of information: (1) the finish time of predecessor Oit--1)= (2) the Duration D of Oi on machine Mn,, and (3) the available time ATT of machine Mm Particularly, "predecessor" denotes the precedence constraint between operations: an operation may start only after all of its predecessors have finished; we refer to this the operaaiiontoo-operatioo (020) dependency. Meanwhile, the Machine Available Time ATT is determined by the finish time of the operation assigned to machine Mm. at the previous steps. Therefore, the ATT is influenced tiniiionnt--mccieee O Osg-1) also be interpreted the Operation Available Time for its successor Ozg.
by the operation to--to---aa- machine (02M) connection. From consistency perspective, the finish time of
4

---

Published as a conference paper at ICLR 2026
Thus, the transition from step 1 to requires only the following information: 1) Operation and Machine Available Time (Node feature); 2) Duration (Edge feature); 3) O20 Dependency (Graph structure); 4) O2M Connection (Graph structure).
Definition 4.1. Let St E & be the state representation at decision step t, which uniquely determines the following: 1) the available times of all machines. 2) the completion status of all jobs (i.e., the finish times of their most recently scheduled operations), 3) the 020 precedence between operations, and 4) the 02M connections (including the corresponding durations).
Proposition 1 (State-dependent Optimality in Scheduling). For any two scheduling trajectories T1 and 72 that reach the same state St, the corresponding remaining subproblems share identical feasible solution set.
As a direct consequence, the optimal decision at step t depends only on St, rather than on the full trajectory history. With this state definition, the scheduling problem can be viewed as finite-state MDP that satisfies the Markov property. A formal proof of Proposition is provided in Appendix D.
State: Subproblem In our framework, each scheduling step is modeled as an individual subprob- lem. To better support this formulation, we refine the state representation along two dimensions: available time from node features and 020 dependencies from gruph structure, thereby excluding historical information and focusing solely the current subproblem. 1) Relative Available Time. We normalize all operation and machine available times by subtracting the global minimum avail- able time each step. This prevents the unbounded growth of absolute time values and mitigates potential generalization issues. A conceptually related idea of removing historical dependencies and using relative-time features for JSSP was explored by Lee Kim (2024); Unlike this JSSP- specific design, we remove all historical information under a subproblem-bis based formulation and extend the relative-time principle to a unified minimal state for FISP and its variants. 2) O20 Con- nection. Instead of the bidirectional operation-to-opeeaaionn (020) edges commonly used in prior work (Song et al., 2023; Wang et al., 2024b; Zhao et al., 2025), we adopt boccward-lookingg edges. Under the subproblem formulation, each operation only requires information from its successors, making redundant historical tracking unnecessary. To further improve efficiency, we introduce hop connections from each operation to all its successors, granting direct access to job-level future straints without relying on multi-layer message passing. Figure 1b illustrates how graph topology and 020/02M connections evolve: once an operation is scheduled, and its associated 020/02M connections are removed, yielding a new subproblem.
Regarding the node feature mentioned in Minimal Representation, we also incorporate the Minimum Duration miDme.M., D across candidate machines as compact yet informative proxy. This value provides a lower bound on processing time, enabling the network distinguish operations of varying difficulty. Although it depends variations, prior work (Song et al., 2023; Lei et al., 2022; Wang al., 2024b; Zhao al., 2025) shows that it is simple and effective approximation in practice. In our framework, it significantly improves learning efficiency without requiring explicit machine assignments.
the set of candidate machines and may be sensitive to instance
State: Features Our state representation consists of four key features: 1) Operation Available Time; 2) Machine Available Time; 3) Duration; and 4) Minimum Duration. Note that dependency and machine eligibility are not features but graph structure, represented by 020/02M connections.
Action In our MDP formulation, the action at step t corresponds to selecting an opera- tion- pair (ij, m), meaning that operation Oi is assigned to machine Mn. For simplic- ity, we denote this action as a,, and the complete schedule is represented as sequence of actions: A {(),,.... , ... J.n). where is the total number of scheduling steps (i.e., the total number of operations). In contrast to many existing neural approaches for FJSP, which introduce auxiliary notions such as free time current time to prune the action space at each step (Song et al., 2023; Wang et al., 2024b; Zhao et al., 2025), our framework avoids such heuristic constraints. The only restriction we impose is the natural precedence constraint between operations (Zhang et al., 2020).
Transition After taking action de, the environment transitions deterministically to state $141, fully determined by the current state 8y and action a;- Specifically, operation and machine status updated according to Eq. (2).
5

---

Published as a conference paper at ICLR 2026
ReSched
Openaie Viatile
Mectine
(T100
Honivamate
Reelaal
Sebe Op Mr
Hesidaa
000
Favil
Oparation
Space
State Sta
Feature Extraction
Decision-Making
Figure 2: The RESCHED framework. The state consists of four information, resulting in four key features (available time and minimum duration for operation; available time for machine; duration), and incorporates three (underlined) architectural enhancements for Transformer-basee network. For secision-making module, we concatenate the embeddings each feasible operation-machine pair, feed them into an MLP to obtain a score.
Reward Inspired by Zhang et al. (2020), we use an estimated lower-bound makespan the re- ward?. Before the scheduling process begins, lower-bound finish time for each operation can be computed iteratively as: FL,g FT + mitlmeM.; D and FT ma) FTa.- where FT,, denotes the lower-bound finish time of operation Oij, and FT max represents the es- timated lower-bound makespan. During the scheduling process, we compute the estimated lower- bound finish time FTTmax (sx) based the current state st. The reward at step t is defined as the negative difference between the estimated lower-bound makespan before and after the action:
Tt (FT (8++1) FT FTmax (8t)).
4.2 POLICY NETWORK ARCHITECTURE
We design decoder-only neural architecture (Drakulic al., 2023) to solve scheduling problems, consisting of two main modules: feature extraction network that models structural and tempo- ral information into embeddings, and lightweight MLP-based policy head that makes scheduling decisions. The overall architecture is illustrated in Figure 2.
4.2. FEATURE EXTRACTION NETWORK
To effectively represent both structural and temporal aspects of the scheduling problem, design a feature extraction network composed of two branches. The operation branch models 020 depen- dencies via self-attention, while the machine branch is built around cross-attention that aggregates operation information into machine embeddings. Both branches are built upon standard Transformer layers, with several targeted adaptations to better capture the unique scheduling characteristics.
Operation branch with RoPE In the absence of explicit positional encoding, intra-job order (i.e., 020 dependency) must be inferred implicitly across network layers, which is both inefficient and unreliable. To address this, incorporate Rotary Positional Embedding (RoPE) (Su et al., 2024) into the operation branch to directly model relative intra-job distances without introducing additional learnable parameters, as shown in the middle bottom of Figure Particularly, RoPE makes the similarity between query and key As a function not only of their content embeddings and æb. but also of their relative position b:
(RoPE,(Ia,) a), RoPE, b)) g( Lb, b).
II Appendix F, we further compare this estimated lower-hound reward with two alternatives (estimated- and A A-makespan rewards).

---

Published as a conference paper at ICLR 2026
In scheduling, dependencies arise only within individual jobs. Operations from different jobs or machines can be permuted arbitrarily without affecting decision-making rendering their relative positions irrelevant. In this sense. RoPE is exclusively applied within the operation branch, injecting positional awareness into intra-job attention patterns. Unlike index-hased positional features, RoPE has been shown to provide stronger generalization and better structural encoding. This allows to simplify the feature set while still preserving the essential sequential information at the job level.
Machine branch with Edge in Attention The machine branch is designed capture the struc- tural interactions between operations and machines. A key aspect of this interaction is the processing duration, which is naturally defined on edges rather than belonging to either operation or machine nodes. To model this, we employ a cross-attention mechanism in which each operation attends to all of its candidate machines, incorporating both node-level and edge-level information. This design is illustrated in Figure 2 (upper branch of the Feature Extraction module).
Unlike prior gross-attentin approaches (Kwon et al., 2021; Drakulic et al., 2024). which incorporate edge features indirectly by adjusting attention scores, our design integrates edge information directly by embedding into the value vectors. This ensures that edge attributes influence not only the attention weights but also the final aggregated representations. Formally, for an operation node Oij and a machine node Mm. the attention is computed as:
Attention(M O1²) = (9m + 9m..s) T (Kiy + kmmdss)
(ro)) + Um,,s),
(5)
Vd
where denotes the softmax function, Im is the query from the machine node, kig and Vig the key and value from the operation node, and Qm,ijs km.ij. Un,új are edge-specific projections derived from the duration Diy. Since the number of operation-machine pairs scales with [O] x [MI] learning independent projection parameters for each edge would be computationally prohibitive. To maintain efficiency, we share projection weights across all attention heads as well as across the query, key, and value projections, significantly reducing parameter count and memory usage.
Machine branch with Self-based Cross-attention In scheduling problems, the number of oper- ations often exceeds the number of machines by an order of magnitude. This structural asymmetry leads to a severe information imbalance: each machine must aggregate information from a dispro- portionately large number of operations, i.e., often 10 times or more, which dilutes attention sig- nals and destabilizes training. Inspired by the machine-node embedding aggregation in Song et al. (2023), we introduce self-based tross-attention mechanism, where each machine node also attends to its own representation during attention weight computation (i.c., upper branch of the Feature Ex- traction module in Figure 2). While residual connections inject self-information unconditionally after attention, the self-based formulation enables the model to assign a soft, adaptive attention weight to the machine's own embedding. This helps preserve critical machine-level information in the presence of overwhelming inter-node messages. Formally, for a machine node Mn with pro- jected value vector Un. and operation projected value vectors Vij E RRd the attention output hmm is defined as:
h' = Crya Dmn +
Σ
Vij
(6)
(3)EN(())
where Oymm is the attention weight assigned to the machine node itself, any are the attention weights for operation nodes connected to Mm, and (MM) denotes the set of such operation nodes. To reduce parameters, we share the query, key, and value projection weights across machine nodes.
4.2.2 DECISION-MAKIN
Our Drcision-making module follows a standard policy network design adopted in prior DRL-based scheduling works (Song et al., 2023; Wang et al., 2024b; Zhao et al., 2025) based on operation- machine pairs. It consists of multi-layer perceptron (MLP) that takes input the operation and machine embeddings from the feature extraction network, along with the edge (i.e., duration) em- beddings, and produces a scalar score for each feasible operation-machine pair. A softmax over these scores yields the final probability distribution. Notably, for simplicity, we do not include a S global embedding in decision-making, as it shows limited effectiveness' Additionally, as discussed
We demonstrate in Appendix B.3, using DANTEL (Wang et al., 2024b) an example, that removing its global embedding does not degrade performance.
7

---

Published as a conference paper at ICLR 2026
in Section 4.1.2, we do not incorporate heuristic masking to prune the action space beyond the hard scheduling constraints (i.e., 020 dependency/O2M connection).
However, unlike most prior works (Zhang et al.. 2020; Song al., 2023; Wang et al., 2024b; Zhao ct al., 2025) that adopt actor-critic frameworks such as Proximal Policy Optimization (PPO) (Schul- man et al., 2017), leverage a simple REINFORCE algorithm (Williams, 1992) to optimize the policy. Although vanilla REINFORCE is known to exhibit higher variance than actor- critic meth- ods such as PPO, we deliberately adopt REINFORCE to isolate the impact of state and architecture design from algorithmic improvements. This choice simplifies implementation and aligns with stan- dard Transformer-bar based NCO practice, such as AM (Kool et al., 2019) and POMO (Kwon et al., 2020). It keeps the training pipeline minimal, without additional critic networks or auxiliary losses, and allows us to focus on the impact of the proposed state representation and architecture rather than on the choice of specific RL algorithm. (However, we also implemented the PPO version of our method for a more comprehensive evaluation, which presented in Appendix E.3). The re- ward is defined (in Eq. (3)) as the negative difference between the estimated lower-bound makespan before and after taking an action. Details of the training algorithm are provided in Appendix B.3.
5 EXPERIMENTS
In this section, we conduct extensive experiments FJSP to demonstrate the effectiveness of RESCHED, comparing it with strong baselines and performing ablations on its key components. As generic framework, we also extend our evaluation JSSP and FFSP to showcase its generality.
Training and Evaluation Settings We train RESCHED on FISP and two variants, JSSP and FFSP, respectively. For each problem, we generate one or two million instances for training, depends on the problem size. The models are trained on smaller problem sizes and evaluated on significantly larger ones as well as standard benchmarks: Bandimarte (Brandimarte, 1993) and Hurink (Hurink et al., 1994) for FJSP, Taillard (Taillard, 1993) and DMU (Demirkol et al., 1998) for JSSP, and extended sizes up to 100x12 for FFSP Notably, for both JSSP and FFSP, we use only single training size (10x10 for JSSP and 20x12 for FFSP) to demonstrate generalization capability. Additionally, we evaluate the policies not only using greedy strategy. but also with a sampling strategy. Following HGNN (Song et al., 2023) and DANIEL (Wang et al., 2024b), for each test instance we run 100 independent stochastic decoding trajectories of the policy in parallel, where every decision step the next mearaiien-mmchinee pair is sampled from the network's 's categorical output, and we report the solution with the smallest makespan among the 100 trajectories. Further details of the dataset and configurations are provided in Appendix B.2. Our code is available at https: / //g/tttuuu com/ Xiang j eeiiao ReSched.
Baselines We compare RESCHED against three groups of baselines. (i) Classical priority dis- patching rules (PDRs), including FIFO, SPT, MOPNR, and MWKR. (ii) State-of-the DaL-based methods: HGNN (Song et al., 2023), DANIEL (Wang et al., 2024b), and DOAGNN (Zhao et al., 2025) for FJSP; L2D (Zhang et al., 2020) and RL-GNN (Park et al., 2021b) for JSSP; and Mat- Net (Kwon et al., 2021) for FFSP. (iii) Strong non-learning baselines. including the 2SGA ge- netie algorithm (Rooyani & Defersha, 2019) tailored for FJSP and the CP-SAT solver from OR- Tools (Da Col & Teppan, 2019), which we apply to both FJSP and JSSP benchmarks. More details given in Appendix B.3.
5.1 PERFORMANCE ON FJSP
In-Distribution Performance Table shows RESCHED outperforms all baselines on both SD, (Song et al., 2023) and SD2 (Wang et al., 2024b) datasets, achieving superior results in 14/16 cases. The advantage is most pronounced on challenging SD₂ instances, where RESCHED reduces the gap by 30% versus DANIEL (15x10 case). Even on simpler SD, instances, it maintains con- sistent improvements, cutting DANIEL's gap by half in 15x10 and 20x10 settings, demonstrating robust performance across difficulty levels.
"The notation X indicates jobs and m machines(the number of operations per job varies across datasets and is omitted here for brevity).
8

---

Published as a conference paper at ICLR 2026
Table 1: Results on datasets: in-distribution (top); out-of-distribution (middle); benchmark (bottom)
Dutaset
Size
FIFO
PDRs MOPNR
MWKR
HGNN
Greedy DANIEL
RuScHuD
HGNNN
Sampling DANIEL
RuSciun
OR-Tools'
Gapti8
17.58
16.87
12:25
5.57
5.95
96.33 (5%)
8
15 10
x0
Guptie)
28.65
38.23
20.68
19:41
16.33
12.27
12:42
6.51
4.63
12.13
2.46
6.79
3.09
2.33
143. (7%)
(0%)
20 10
(upt())
19.22
30.25
12.20
10.30
10.15
1.31
0.48
9.64
-1.03
-1.55
195. (0%)
10xx5 5
76.47
57.96
72.52
70.01
71.43
25.68
16.36
49.71
12.57
6.39
506 24 (96/6)
20 5
74,59
38.91
74.58
71.31
76.79
11.52
9.87
60.70
4,66
3.68
602.00 042.04 (0%)
10
132.23
56.74
125.32
121.45
115.26
57.16
18.14
101.52
38,70
9.81
377.17 17 (28%))
129,09
124.98
14.18
7,90
464.16 (1%)
PDR
Greedy
Sampling
SPT
HGNN
30 10
23.42
13.96
$6.81
14:11
5.10
2.58
3,44
2.69
12.56
13.89
6.43
1.67
3.40
1.51
274.57 (8S]
40x
Gape9
21.66
13:37
14.21
13.75
5.65
1.52
2.54
12.26
13.49
3.77
1.14
3.64
(994)
A
40
59:74
38.74
108.06
109.87
108.12
14,35
0.52
11.95
-1.07
-2.40
-4.5
102.45
99.26
9.47
2.74
4,90
-..00
5..0
-7.61
996.39 (09)
195)
Stratago
Datant
(Top PDR)
MWKR
BKNN
10 5
16 10
HINN
DANIF
10.x
16.x 10
DOACINN
20.x-
10 5
16:x 10
25GA
OR- Yock
UIF
Gredly
Mornetrdrra
Brandimeeee
Copt51
Captia1
25.91
18.0
28.51
15.31
26.77
13.58
16:3%
12.90
14.41
31.64
16:21
9,08
15:48
12:49
54
175 175-2003 1716)
1074, 914-0098)
124.30 1.56)
172.7
Cop1511
4.32
2.55
812.200.996)
Simpting
Beandimane
Gapt1111
25.91
18.50
1911
9.53
8:95
1862
6.61
5.14
175.200 1716)
174, 174,21N 595)
172.7
Haraiciadzas
18.6
9.07
8.09
9.08
8.72
8.46
8.13
10.30
1025-924 4088599
1028-85
Coptla
13.80
5.87
5.5
4.95
5.40
5.33
500
4.92
Cop/551
1. OR-Tools (1800s per instance): solution and optimal ratio reported;
2. UB is the best-known solution (Behnke & Geiger, 2012), used as the baseline to compute gaps;
3. Instance-wise average gap is reported to reduce bias from varying instance scales.
Table 3: Results on Taillard Benchmark for JSSP.
PIB:: REAMINE
SPT MOKE
L.D
$3:0.0
36.7
43.0
25:0
15.74
31
04.3
55.7
43.4
43.6
3.4
28.3
16.3
14171
31-20
66.
659
16.3
48.
338
13.8
33.5
28
19114
114
419
11:1
114
1611
100
410
329
23.4
363
136
82
06
30
53966
Figure 3: Running Time on FJSP Benchmark
Generalization Performance RESCUED demonstrates strong generalization on both synthetic and benchmark datasets (Table 1). On larger synthetic instances (30x10 10 to 40x10), it outperforms DRL baselines in 6/8 cases, even surpassing OR-Tool, by 7.61 % on the challenging SD₂ with 40x10 setting. For Brandimarte and Hurink benchmarks. trained solely on SD₁, RESCHED achieves best performance in 7/8 cases across both strategies. Notably, the DOAGNN does not report results for the 15x 10 setting, and is thus only compared using one configuration. Compared with strong non-learning baselines, 2SGA and OR-Tools (with 3600s time limit) can often obtain solutions very close to the best-known upper bounds, but at the cost of substantially longer computation time due search or exact optimization. In contrast, once trained, RESCHED pro-
to lengthy population-bal duces competitive solutions within short inference time per instance (see Figure 3), and its perfor- mance can be further improved by simple sampling-buus based decoding without additional training cost, making it more suitable for time-sensitive or repeatedly solved scheduling scenarios. These results suggest RESCHED'S 's potential for generalization to real-world settings with complex characteristics under practical time budgets.
Running Time Analysis To evaluate runtime efficiency, we conduct experiments on open bench- mark instances characterized by diverse problem structures. Each algorithm is independently exe- cuted five times to ensure reliable results, and their average running times are reported in Figure 3. Notably, our method achieves a runtime comparable to existing DRI--based approaches while out- performing current state-of-the-art methods in terms of scheduling quality.
5.2 ABLATION STUDY AND ROBUSTNESS ANALYSIS
We conduct ablation studies on RESCHED's 's two key innovations: (1) the minimal representation and (2) attention- based architectural improvements, by removing each design element individually.

---

Published as a conference paper at ICLR 2026
Results in Table 5 (Appendix B.3) confirm that all components contribute positively to performance. Additionally, we perform robustness analysis by training RESCHED across multiple random seeds to assess its stability and consistency. The results, presented in Table 6 (Appendix B.3), demon- strate that the variation across seeds is minimal (less than 1 1%), further confirming that RESCHEd'S improvements both robust and consistent.
5.3 PERFORMANCE ON JSSP AND FFSP
We evaluate RESCHED's generalization capability on the Taillard benchmark (Taillard, 1993) for JSSP. Trained solely on synthetic 10x 10 instances (generated under the same distribution as Zhang et al. (2020)), our model is directly tested on benchmark instances ranging from 15x15 15 to x00 by greedy strategy. The results in Table show that, RESCHED outperforms L,2D and RL-GGN in 7 out of 8 test sizes, even surpassing their in-distribution performance (trained and tested on the same size). For reference, we also report the results of the CP-SAT solver OR-Tools (Da Col & Teppan, 2019) with a 3600-second time limit per instance, which provides strong upper bounds on the Taillard instances. This demonstrates exceptional scalability, as no size-specific tuning is required, which exhibits our framework's s ability to adapt to different scheduling problems. Results on in-distribution settings and the DMU henchmark, when evaluated with a greedy decoding strat- egy, also confirmed its consistent superiority (see Appendíx B.3). We further evaluate RESCCED on FFSP under MatNet's setting (Kwon et al., 2021). Unlike MatNet, which trains a separate model for each size (20/50/100), RESCHED, trained only on size 20, achieves the best results in most settings across sizes under both greedy and sampling strategies (Table 9). Same as MatNet, we also use 24 parallel solutions per instance, which showed superior generalization.
CONCLUSION
In this paper, we present RESCHED, novel framework for solving scheduling problems using deep reinforcement learning. RESCHED introduces a simplified state representation and a Transformer- based architecture, which effectively captures the structural and temporal characteristics of schedul- ing problems. Our extensive experiments on FJSP, JSSP, and FFSP demonstrate that RESCHED achieves favorable performance while maintaining high efficiency. The results highlight the po- tential of RESCHED as generic framework for various scheduling tasks. However, RESCHED cur- rently encodes only 020/O2M interaction with aeff=attentionmuuiiirecitiaaa machine to operation (M20) feedback is not yet modeled and will be explored in future. Moreover, we will also investigate how to adapt our method to search-based works (Zhang et al., 2024).
-ross-attnntion; explicit
ACKNOWLEDGEMEENTS
This research is supported by the National Research Foundation, Singapore under its AI Singapore Programme (AISG Award No: AISG3-RP-2022-0031) This work is also supported by the National Natural Science Foundation of China (No. 62473233).
REFERENCES
A multi-agent approach to intelligent transportation systems modeling with combinatorial auctions. Expert Systems with Applications. ((15))6622-6633 2014. ISSN 0957-4174. doi: https://doi. org/10.
URL https: htwp///wwwt//.. sci sencedirect com/ sci science/ art articcle/11//09574111 4002954.
AR Arunarani, Dhanabalachandran Manjula, and Vijayan Sugumaran. Task scheduling techniques in cloud computing: A literature survey. Future Generation Computer Systems, 91:407-415,
2019.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. stat, 1050:21, 2016.
Dennis Behnke and Martin Josef Geiger. Test instances for the flexible job shop scheduling problem with work centers. 2012.
'ee only report best OOD setting for I.2D) for short
10

---

Published as a conference paper at ICLR 2026
Jacek Blažewicz, Erwin Pesch, and Malgorzata Sterna. The disjunctive graph machine represen- tation of the job shop scheduling problem. European Journal of Operational Research, 127(2): 317-331, 2000.
Paolo Brandimarte. Routing and scheduling in a flexible job shop by tabu search. Annals of Opera- fions research, 41(3):157-183, 1993.
Ruiqi Chen, Wenxin Li, and Hongbing Yang. A deep reinforcement learning framework based on an attention mechanism and disjunctive graph embedding for the job-shop scheduling problem. IEEE Transactions on Industrial Informatccs, 19(2):1322-133 2023. doi: 10.1 111//T1..022.3167622.
Giacomo Da Col and Erich C Teppan. Industrial size job shop scheduling tackled by present day ep solvers. In International Conference on Principles and Practice of Constraint Programming, pp- 144-160. Springer, 2019.
Ebru Demirkol, Sanjay Mchta, and Reha Uzsoy. Benchmarks for shop scheduling problems. Euro- pean Journal of Operational Research, 109(():137-141, Aug 1998. doi: 10.1016/50377-2211700 (97) 00019-2.
00019-2. URL stttps://don wtt.:/o..oooooooo 10..0.1116//000
Kai Ding. Felix TS Chan, Xudong Zhang, Guanghui Zhou, and Fuqiang Zhang. Defining digital twin-based syyber-physice production system for autonomous manufacturing in smart shop floors. International Journal of Production Research, 57(20) 2019.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. Bq-nco: Bisimu- lation quotienting for efficient neural combinatorial optimization. Advances in Neural Information Processing Systems, 36:77416-77429, 2023.
Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. Goal: A generalist combinatorial opti- mization agent learner. In The Thirteenth International Conference on Learning Representationss 2024.
Yi Feng, Lu Zhang, Zhile Yang, Yuanjun Guo, and Dongsheng Yang. Flexible job shop scheduling based deep reinforcement learning. In 202/ 5th Asian Conference on Artificial Intelligence Technology (ACAIT), pp. 660-666. IEEE, 2021.
Scarselli Franco, Gori Marco. Tsoi Ah Chung, Hagenbuchner Markus, and Monfardini Gabriele. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2009.
Reinhard Haupt. A survey of priority rule-based scheduling. Dperations-Research-SPpeo 3-16, 1989.
11(1):
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Johann Hurink, Bernd Jurisch, and Monika Thole. Tabu search for the job-shop scheduling problem with multi-purpose machines. Operattioss-Reseand--Sppeee
15(4):205-215, 1994.
Zangir Iklassov, Dmitrii Medvedev, Ruben Solozabal Ochoa de Retana, and Martin Takac. the study of curriculum learning for inferring dispatching policies the job shop scheduling, In Edith Elkind (ed.), Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pp. 5350-5358. International Joint Conferences Artificial Intelligence Organization, 8 2023. doi: 10.24963/iccai222235544 URL https: wttp:/i...rr.................... ijcai. 2022 594. Main Track.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference Learning Representations, 2019. URL https::/ net/forum? i
Yeong- Dae Kwon, Jinho Choo. Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 188-21198. 2020.

---

Published as a conference paper at ICLR 2026
Yeong-Dae Kwon, Jinho Choo, I1joo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Ma- trix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138-5149 2021.
Je-Hun Lee and Hyun-Jung Kim. Graph-based based imitation learning for real-time job shop dispatcher. IEEE Transactions Automation Science and Engineering, 2024.
Kun Lei, Peng Guo. Wenchao Zhao, Yi Wang, Linmao Qian, Xiangyin Meng, and Liansheng Tang. A multi-action deep reinforcement learning framework for flexible job-shop scheduling problem. Expert Systems with Applications, 205:1 17796, 2022.
Quyuan Luo, Shihong Hu, Changle Li, Guanghui Li, and Weisong Shi. Resource scheduling in edge computing: A survey. IEEE communications surveys & tutorials, 23(4):2131-216) 2021.
Junyoung Park, Sanjar Bakhtiyar, and Jinkyoo Park. Schedulenet: Learn solve multi-agent scheduling problems with reinforcement learning. arXiv preprint arXiv:2106.0303 2021a.
Junyoung Park, Jaehyeong Chun, Sang Hun Kim, Youngkook Kim, and Jinkyoo Park. Learn- ing to schedule job-shop problems: representation and policy learning using graph neural net- work and reinforcement learning. International Journal of Production Research, pp. 3360-3377, Jun 2021b. doi: 10. (08000000054322000008877 00207543 2020 ww....1...000000 1870013.
URL http:///://tt doi. iicciio.. org orgg//..//0000000
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Danial Rooyani and Fantahun M Defersha. An efficient two-stage genetic algorithm for flexible job-shop scheduling. Papersspess,,,,,, 52(13):2519-22) 2524, 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Veronique Sels, Nele Gheysen, and Mario Vanhoucke. comparison of priority rules for the job shop scheduling problem under different flow time-and tardiness-related objective functions. In- ternational Journal of Production Research, 50(15):4255 4270, 2012.
Wen Song, Xinyang Chen, Qiqiang Li, and Zhiguang Cao. Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Transactions on Industrial Informatics, 19(2):160-11100, 2023. doi: 10. 10.11000 102.//1..222..1199777
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: En- hanced transformer with rotary position embedding. Neurocomputing, 568: 180063,763, 2024.
E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, pp. 278-285, Jan 1993. doi: 10. 10.1016/0000 101160077-22117999901888288 htts 1016/0377-200 (93) 9018 10002-1-0 12288. m.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention you need. Advances in neural informa- tion processing systems, 30, 2017.
Petar Velickovie, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Ben- 2017.
gio, al. Graph attention networks. stat,
Jin Wang, Jia Hu, Geyong Min, Wenhan Zhan, Albert Y. Zomaya, and Nektarios Georgalas. Depen- dent task offloading for edge computing based deep reinforcement learning. JEEE Transactions on Computers, 71(10):2449 2461, 2022. doi: 10. 10.1109/TC.202113311440
Rongkai Wang, Yiyang Jing, Chaojie Gu, Shibo He, and Jiming Chen. End-to-end multi-target flexible job shop scheduling with deep reinforcement learning. IEEE Internet of Things Journal, 2024a.
12

---

Published as a conference paper at ICLR 2026
Runqing Wang, Gang Wang, Jian Sun, Fang Deng, and Jie Chen. Flexible job shop scheduling via dual attention network-basee reinforeement learning. JEEE Transactions on Neural Networks and Learning Systems, 35(3):3091-3100 2024b. doi: 10. WAL.1099TNNISS222333.332
Yong Wang. Zhi- Yang Ru, Kezhi Wang, and Pei-Qiu Huang. Joint deployment and task scheduling optimization for large-scale mobile users in multi-nav-enabled mobile edge computing. IEEE Transactions on Cybernetics, 50(9):3984-3997, 2020. doi: 10.1109/TCY..2019922999
Ronald J Williams. Simple statistical gradient- following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-255) 256, 1992.
Xiang-Jie Xiao, Yong Wang, Pei-Qiu Huang, and Kezhi Wang. Neural combinatorial optimization for multiobjective task offloading in mobile edge computing. IEEE Transactions on Vehicular Technology, 74(7):10869 1080006699-00000--11110118188000 2025. doi: 10.100//VT.20253556914.
Yifan Yang, Gang Chen, Hui Ma, Cong Zhang, Zhiguang Cao, and Mengjie Zhang. Graph assisted offline-olline deep reinforcement learning for dynamic workflow scheduling. In International Conference on Learning Representations, 2025.
Cong Zhang. Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Xu Chi. Learning to dispatch for job shop scheduling via deep reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 1621-1632. Curran Associates, Inc., neurips. ec sttppper_fileeeppeeeeeeeee pdf.
2020. URL Btte:2195sttee2200000eaaaaa23333
Cong Zhang, Zhiguang Cao, Wen Song, Yaoxin Wu, and Jie Zhang. Deep reinforcement learning guided improvement heuristic for job shop scheduling. In The Twelfth International Conference on Learning Representations, 2024.
Peng Zhao, You Zhou, Wang. Zhiguang Cao, Yubin Xiao, Xuan Wu, Yuanshu Li, Hongjia Liu, Wei Du, Yuan Jiang, and Liupu Wang. Dual operation aggregation graph neural networks for solving flexible job-shop scheduling problem with reinforcement learning. In Proceedings of the ACM Web Conference 2025, WWW '25, pp. 4100, New York, NY, USA, 2025. Association for Computing Machinery, ISBN 9798400712746. doi: 10.1145726964133371466..
URL
13

---

Published as a conference paper at ICLR 2026
A STATE REPRESENTATION: FROM FJSP TO OTHER VARIANTS
A.1 REVISITING THE FSJP FORMULATION
In FJSP, for each operation node Oij. define:
ST the start time of operation Oifi
D the duration of operation Ozg on machine m;
. F: the finish time of operation Oij-
For each machine node M, we define:
A. the available time of machine m at the current scheduling step.
Whenever ox operation node Oij may start only satisfies the following two constraints: the operation dependency constraints and the machine availability constraints. Then the finish time FTy and start time STi can be computed as follows:
F ST + Di. if a
S max
AT;")
where FT is the finish time of predeccessor operation Osú-1) in the job J. For the machine nodes, the available time ATT at step is updated as follows:
FT ATT
if af =1
ATM
(8)
otherwise
where (f'j") is the operation assigned to machine m at step /
Finally, for scheduling problem like FJSP, we aim to optimize the solution A to minimize the makespan FTiaxx which is defined as the maximum finish time across all operations:
FT
max FTi-- (5))EO
Remark 1. As we analysed in the Proposition of past states. This means do not need to directly track the finish times of operations scheduled in previous steps. However, since the finish time of an operation Oiz-1 serves as the available time for its successor Oij, same information in a recursive manner. Thus the Eq. (7) can be simplifted as Eq. (2) in the main text.
is unnecessary to explicitly retain the full history
instead maintain the operation available time a quantity that captures the
Using the above formulation, for a given FISP instance and feasible solution A, we can compute each operation's 's status and machine's status at each scheduling step.
A.2 FROM FJSP TO OTHER SCHEDULING PROBLEMS
From heterogeneous graph perspective, FJSP provides a unified formulation that naturally extends two classical variants: JSSP and FFSP.
JSSP as a special case. In JSSP, each operation is tied to exactly one machine rather than a set of machines. Consequently, the duration D and schedule a!,,; degenerate to Dij and ar.ij. respec- tively. The 020 dependencies remain unchanged, whereas the O2M connections become oot-hot. The state representation and update rules are the same as FISP, with trivial O2M connections.
FFSP special case. In FFSP, all jobs follow an identical sequence of stages, i.e. an identical routing with one operation per stage. In this context, an "operation" " can be viewed as a stage. Each stage is executed at station, and under the flexible setting, station is typically composed of mul- tiple parallel machines capable of performing the same task. Hence, FFSP can viewed as an FJSP with Mú M, for all jobs i. The 020 dependencies reduce to stage-to-ste st-stage precedence, while the 02M connections remain similar to FJSP, where each stage is connected to its corresponding station's 's machines.
14

---

Published as a conference paper at ICLR 2026
A
M
A6
AG
A6
35
M,
Mr
JSSP Instance
JSSP O2M Connection
FFSP Instance
FFSP O2M Connection
Figure 4: The illustration of JSSP and FFSP instances, respectively.
Implications for our framework. Across these variants, the core state representation and update rules remain consistent with those of FJSP. The O20 dependencies are preserved; differences arise only in the pattern of O2M connections, reflecting each problem's 's -acbine-vvailabiiityy constraints. Figure 4 illustrates both variants with identical O20 dependencies and differing machine-availabiie constraints.
B TRAINING ALGORITHM AND EXPERIMENT
B.1 TRAINING ALGORRTHM
We introduce the training algorithm for RESCHED in Algorithm 1. The training process follows the REINFORCE algorithm, where sample actions from the policy network and compute the policy loss based on the rewards received. The model parameters are updated using gradient descent.
Algorithm 1 Training RESCHED with REINFORCE
1: Input: Scheduling environment E, model parameters 0, number of epochs E, training episodes N, batch size B3, learning rate a;;
2: for epoch 1 to E do
3: Initialize score and loss meter;
4: while ep N do
5: Generate B instances using environment E;
6: Reset the environment get initial state so; Initialize empty trajectory: T 0;
7:
8:
repeat
9:
Process current state 8; into model input; Sample action ag TTo- st);
11:
Execute a, get reward r, and next state 8 Store (8t, at, Ft, 8e++1 into T;
12:
13:
8: 8111;
14:
until task is finished
15:
Compute return G₁ using discounted cumulative rewards; Normalize advantages: A, = G, mean (G)); Compute policy loss L = E, A, log To se);
16:
17:
18:
Update parameters: 0 - VoV:
ep < ep + B;
20:
end while
Validate Te on validation set;
22:
end for
Output: Trained model parameters
15

---

Published as a conference paper at ICLR 2026
B.2 EXPERIMENT DETAILS
Datasets For FJSP, the model is trained on synthetic datasets SD₁ (Song et al., 2023) and SD2 (Wang al., 2024b), evaluate its in-distribution performance, and then evaluated on larger size as well as standard benchmark: Bandimarte (Brandimarte, 1993) and Hurink (Hurink et al., 1994). The synthetic datasets are generated using the same method as Song et al. (2023) and Wang et al. (2024b). Specifically, for an instance of FJSP with n jobs and m machines:
SD1: Duration Dij is uniformly sampled from [12 Each job's operations number is uniformly sampled from [0.8n, 1.2n];
SD2; Duration D is uniformly sampled from 99]: Each job's operations number is uniformly sampled from [1,n]] n].
For JSSP, the model is trained on the synthetic dataset to evaluate its in-distribution performance, and then evaluated on the standard benchmark: Taillard (Taillard, 1993) and DMU (Demirkol et al., 1998). The synthetic dataset generated as follows: Duration Dsg is uniformly sampled from [1,99]; Each job's operations number is uniformly sampled from [1, m).
For FFSP. the model is trained on the synthetic dataset generated with the same method as in Kwon et al. (2021), to evaluate its in-distribution performance and cross-size generalization performance. The synthetic dataset generated as follows: Duration D uniformly sampled from [2, 9]: Each job has 3 stages, and each stage has 4 parallel machines a station.
Configurations The RESCHED framework is implemented in PyTorch (Paszke et al., 2019) and trained using the REINFORCE algorithm (Williams, 1992). The feature extraction network con- sists of 2-layer Transformer blocks, each with 8 attention heads, a hidden dimension of 128, and feed-forward dimension of 512. The decision-maie masiing network is 3-layer MLP, with each layer containing 64 hidden units, following prior works (Zhang et al., 2020; Song et al., 2023; Wang et al., 2024b; Zhao al., 2025). We use the Adam optimizer with learning rate of x 10-5, The model is trained for 2000 epochs, with 1000 training instances per epoch and batch size of 50. The discount factor 7
0.99. Due resource constraints, for lager sized problem, the number of training instances per epoch is reduced to 500 and the batch size to 24. During training, we use the estimated lower bound of the makespan as the reward, as described in Eq. (3), with a discount factor of 0.99. The model that achieves the best performance on the validation set is saved and later evaluated on the test set (100 generated instances) and benchmark datasets. We use a single NVIDIA RTX A40 GPU for training and evaluation. We will release the code and data generation scripts.
Hyperparameter tuning and reporting We tune RESCHED on the SD, 10 x 5 setting and keep the selected hyperparumelers fixed for all other datasets and sizes. For baselines, we do not perform additional tuning beyond the authors' default settings. We either directly report the results from their original papers use their open-source code with the provided hyperparameters and checkpoints to ensure a fair comparison. All baselines have open-source implementations: some also provide checkpoints.
Baselines To assess the effectiveness of RESCHED, we compare it against both rule-based and DRL-based baselines commonly adopted in the FISP literature. The baselines are grouped into two categories:
(1) Priority Dispatching Rules (PDRs). We include four widely used heuristic rules:
FIFO Crist-In-First-uut Selects the carliest operation- machine pair based on the order of arrival.
SPT (Shortest Processing Time): Selects the pair with the shortest operation duration.
MOPNR (Most Operations Remaining): Selects the pair associated with the job that has the largest number of remaining operations, breaking ties by the earliest machine available time.
MWKR (Most Work Remaining): Selects the pair associated with the job that has the largest total remaining processing time, using the average duration of successor operations, and breaks ties by the earliest machine available time.
16

---

Published as a conference paper at ICLR 2026
These heuristics are widely adopted due their efficiency, simplicity, and strong generalization ability, particularly in large-scale or unseen scheduling instances (Sels et al., 2012). We implement these PDRs using the open-source code by Song et al. (2023) and keep the same hyperparameter settings.
(2) Neural methods for FJSP We also compare RESCHED against three representative GNN-based approaches developed for FJSP:
HGNN (Song et al., 2023): Models the scheduling problem heterogeneous graph, where operations and machines are treated as distinct node types.
DANIEL (Wang al., 2024b): Employs dual-attention mechanism to jointly capture opecation-machine interactions.
DOAGNN (Zhao et al., 2025): Leverages a decoupled disjunctive-graph formulation to better encode precedence and machine constraints.
All three methods are DRL frameworks based GNN variants (e.g., GAT) (Velickovic al., 2017), and using the PPO (Schulman et al., 2017) as training algorithm. For HGNN and DANIEL, directly report the results from their original papers. For DOAGNN, we use their open-source code and evaluate it on the open benchmark using their provided checkpoints. Additionally, we retrain DANTEL from scratch in our ablation study to validate our simplified feature set, maintaining the same hyperparameter settings as in the original work.
(3) Neural methods for other variants Additionally, we compare RESCHED against two GNN- based methods targeting JSSP; and a transformer-based method for FFSP:
L2D (Zhang et al., 2020): Proposes an end-to-end DRL framework that learns size-agnostic priority dispatching rules for JSSP, based on disjunctive graph representation and Graph Isomorphism Networks.
RL-GNN (Park al., 2021b): Integrates RL with a GNN-based encoder-decoder network to solve JSSP, capturing both job and machine contexts through dynamic graph representa- tions.
Matnet (Kwon et al., 2021): Introduces a matrix- encoding of combinatorial struc- tures for routing problems and FFSP, enabling flexible attention across decision steps. applies a transformer-style architecture to scheduling by encoding instance states as 2D matrices and training via REINFORCE.
For L2D and RL-GNN, we directly report the results from their original papers. For Matnet, we use their open-source code to retrain and evaluate it under the default hyperparameters.
B.3 EXPERIMENTAL RESULTS
The input embedding for decision-making module in DANIEL is the concatenation of the operation, machine, pair and global embeddings, involving a total of 26 features (10 for operation, 8 for machine, 8 for pair); the global embedding is learned and does add additional raw features. To evaluate the effectiveness of each component, we conduct an ablation study by removing the components one by one. The experiments are conducted on the synthetic dataset SD, with 15 10, and the results are shown in Table 4.
Ablation Study on DANIEL
Table 4: Ablation study on DANIEL.
setting
Obj-b
Avg. A(%)
DANIEL
589.44
56.28
Del Global
589.12
56.19
Del Global MA
588.66
56.07
Gloabl MA P(-P6) 588.76
56.10
Del Gloabl MA P(-P6) O(-02399)
587.68
55.81
We conduct an ablation study on DANIEL to analyze the impact of different input embeddings. The results in Table 4 reveal the following insights:
17

---

Published as a conference paper at ICLR 2026
Del Global: Removing the global embedding leads to slight improvement, indicating that this component may introduce redundancy or noise.
Del Global MA: Further removing the machine embedding, comprising 8 machine-related features, results in continued improvement, suggesting that the model can perform well without explicit machine descriptors.
Del Global MA P(-P6): Based on the previous experiment, we further prune the pair-wise features from 8 to single (6th) feature, which still maintains performance. This indicates that most pair features are not essential for effective scheduling.
Del Global MA P(-P6) O(-02379): Afterwards, based on all the previous experiments, we prune the operation features from 10 to 4 (retaining only features 2, 3, 7, and 9), and the performance is still comparable the original DANIEL. This further validates that the full feature set is not strictly necessary for effective scheduling.
In the last step above, eliminate the number of features in DANIEL from 26 to only 5 (4 for operation, i.e. O2379, and for pair-wise, i.e. P6), and the performance is still comparable to the original DANIEL.
Table 5: Ablation study on ReSched.
In- Distribution
Open Benchmark Brandimarte
Ablation
Avg. A(%) 4
30
40
RESCHED
Gap(%))
A
0.00
+0.10
3.44
2.54
0.00
0.00
9.08
+0.00
Gap(Sk))
16.42
14.48
Connection
A(%)
+4.17
+3.30
+1.29
+5.40
+3.54
Relative Available Time
Gap(%))
A(%)
+1.08
13.33
+1.58
5.02
3.77
+5.76
14.84
+2,41
Gap(5))]
13.49
3.38
2.73
12.71
Current Time
A(%)
+0.19
43.63
+1.25
Gap(Si)]
12.81
3.34
2.75
14.97
RoPE
((%)
+0.56
-0,10
+0.21
+5.89
+1.64
Gap[%)) A(%)
13.02
Edge in Att
+1.50
+0.31
+0.84
+0.90
+3.94
Gap(%)) A(%)
13.16
4.67
3.72
16.10
Self-hased CA
+2,59
+0.91
+1.23
+1.18
+7.02
(%) indicates the gap deviation from standard RESCHED.
Avg. A summarizes overall performance deterioration across all datasets.
Ablation Study on RESCHED To evaluate the effectiveness of each proposed component in RESCHED, we conduct comprehensive ablation studies to analyze our simplified state representa- tion and network architecture. Specifically, we individually remove six key ideas from our standard framework, including simplifications and attention-related improvements. The ablation settings are illustrated follows:
Connection:
Removing the 020 connection, and using the original bidirectional connec-
tion, which are widely used in previous works (Zhang et al., 2020; Song al., 2023; Wang et al., 2024b; Zhao et al., 2025).
Relative Available Time: Replacing the relative available time with the absolute available
time (for operation and machine).
Current Time: Using the absolute current time prune the action space in previous works (Song et al., 2023; Wang et al., 2024b; Zhao et al., 2025).
RoPE: Removing the RoPE mechanism in operation branch.
Edge in Att: Removing the edge features in cross-attention mechanism in machine branch.
belf-based CA: Removing the self-based cross-attention mechanism in machine branch.
All variants are trained on the smallest SD, dataset (10x5) and evaluated on four test settings, in- cluding in-distribution, out-of-distion difrriiittibbtion x30x 10 and 40x 10), and challenging open benchmark (Bandrimarte). As shown in Table 5, each component contributes to the overall performance, con- firming the effectiveness and necessity of our design choices.
18

---

Published as a conference paper at ICLR 2026
Table 6: Performance of RESCHED trained with REINFORCE across four random seeds.
Dataset
DANIEL
RESCHED-Avg.
RESCHED-Orig.
Seed
Sced2
Seed3
In-distribution
SD1-10x05
10.87
11.75
12.25
11.40
12.33
11.03
Out-of-distribution
-0x
5.10
3.10
3.44
2.46
3.39
3.09
SD₃-40x10
3,65
2.23
2.54
1.64
2.46
2.26
SD;-30x10
14.85
9.04
8.79
9.35
9.78
8.22
SD2-40x10
0.52
-2.61
-2.40
-3.00
-1.80
-3.23
Avg.
6.03
2.94
3.09
2.61
3.46
2.59
Open Benchmark
Brandimarte
13.58
10.28
9.08
11.70
10.10
10.24
Hurink (edata)
16.33
15.84
15.48
16.46
15.52
15.88
Hurink (rdata)
11.42
10.13
10.18
10.30
10.46
9.57
Hurink (vdata)
3.28
2.90
3.48
2.60
2.55
2.95
Avg.
11.15
9.78
9.56
10.27
9.66
9.66
Values are average optimality gaps (%) w.r.t. the best-known upper bounds.
"RESCHED-Avg." denotes the mean over all four RESCHED runs (original + three additional seeds),
Robustness Evaluation under Multiple Random Seeds To verify the robustness of our frame- work, we RESCHED (REINFORCE version) the SD1-10x5 training setting with three additional independent runs using different random seeds (four runs in total, including the originally reported in Table 1). For each run, evaluated the policy across in-distribution, out-of-distribution, and open benchmark test settings to comprehensively test the performance of RESCHED. For ease of comparison, Table 6 reports the second column the average over all four independent runs (the originally reported run plus the three new ones), while the subsequent columns list the results of each individual run. On -iitt-i-iitiiitiinonn and open benchmark tests, all RESCHED runs outper- form DANIEL, while in-distribution performance on SD1-10x5 remains comparable. Moreover, the variation across seeds much smaller than the performance gap between RESCHED and DANIEL, indicating that our gains robust and not due to fortunate choice of random seed.
Performance on JSSP with Synthetic Data and DMU Benchmark In main text, we have reported the performance of RESCIED on the Taillard benchmark. Here, we also evaluate its per- formance on synthetic JSSP data and the DMU benchmark. The synthetic data is generated using the same method as in Zhang al. (2020), and the DMU benchmark is widely used benchmark for JSSP. The results are shown in Table 7 and Table 8, respectively. Similar to the Taillard benchmark, both synthetic data and DMU benchmark by solely
RESCHED achieves the best performance using the same model trained on the 10 x 10 synthetic data.
Table 7: Performance on synthetic datasets of JSSP.
PDRs
DRL-based
Size
RESCHED
Opt. Rate( %)
SPT
MWKR
FDD/WKKR
MOPNR
L2D
10
10
6
x
6
42.0
34.6
24.0
29.2
17.7
7.0
100
10
10
50.0
42.6
36.6
36.5
22.3
9.5
100
15
15
59.2
52.6
45.1
42.6
26.7
14.3
99
20
62.0
58.6
49.6
45.5
29.0
15.0
4
30
20
65.3
58.7
44.7
29.2
12
50
20
54.9
48.1
38.4
33.7
22.1
12.8
48
100
20
35.1
27.0
19.6
14.7
9.4
4.3
2
Opt. Rate is the rate of instances for which oRoTools returns the optimal solution.
19

---

Published as a conference paper at ICLR 2026
Table 8: Performance on DMU benchmark of JSSP.
PDRs MWKR
DRL-based
Size
RESCHED
UB'
SPT
FDD/MWKR
MOPNR
L2D
10 10
20 15
64.1
62.1
53.6
49.2
39.0
23.72
3023.8
20 x 20
64.6
58.2
52.5
45.2
37.7
22.2
3472.6
30 15
62.6
60.9
54.1
47.1
41.9
27.8
3879.0 0
30 x 20
65.9
63.2
60.1
52.0
39.5
28.3
4248.4
40 x 15
55.9
52.9
51.4
44.7
35.4
26.5
4871.2
40 20
63.0
61.1
55.5
49.2
39,4
29.2
5240.9
50 x 15
50.38
48.94
52.55
40.78
36.2
26.3
5950.6
50 20
62.2
56.4
57.3
49.6
38.8
31.8
6227.3
Upper Bound (UB) the best known solution (available) for each instance. 2. Instance-wise average gap is reported to provide higher accuracy.
Table 9; Performance FFSP.
Greedy
Sampling
setting
FFSP20
FFSP50
FFSPI00
FFSP20
FFSP50
FFSPI00
Matnet20
28.05
52.58
93.00
27.31
52.36
93.40
Matnet50
27.78
52.05
92.17
27.05
51.55
91.86
Matnet100
27.64
51.79
91.79
27.09
51.40
91.50
ReSched20
26.65
51.24
92.28
25.12
49.65
90.80
In the main text, reported the overall performance of RESCHED on the FFSP. Here, we present the detailed results Table
Performance on FFSP
C THEORETICAL ACCELERATION OPPORTUNITIES: KV CACHE
The RESCHED framework allows for theoretical acceleration via Key-Value (KV) caching mech- anism, owing to the following structural properties:
Backward-looking -lokknn edges: Each operation node is updated only by its successor operation;
The representation of each successor operation is fixed (determined by the minimum dura-
tion);
Operation nodes are not updated by machine nodes, which contain dynamic features that vary across scheduling steps.
As illustrated in Figure 5, this structure enables us to cache and reuse the key-value pairs previ- ously computed operation nodes during multi-step decoding, avoiding redundant computation across steps. To see this, consider an instance with n operations and m machines, decoded n decision steps by L-layer Transformer. Without KV cache, each step the 020 branch performs self- attention over n operation nodes, with complexity (LL?),, and the 02M branch performs cross- attention between m machine queries and operation keys/values, with complexity ((mmn). Over decoding steps, the total attention cost is therefore
OLLnn + mn²)).
With KV cache, the operation representations (and their keys/values) computed only once in the 020 branch, with cost (Ln"), and then reused at all later steps; the O2M branch still needs to be recomputed each step due to changing machine availability, giving total of
(Ln (1 m)).
The asymptotic reduction in attention computation is thus by factor of
L(n3 + mn?)
n + m
Ln m) m
20

---

Published as a conference paper at ICLR 2026
Openation with Ausiiable Time Computed by this smp
Sparebar witl Anciliee Computed dapa
AG
M6
74
26
A5
Cooo
Step
Step
Figure Illustration of the KV cache mechanism in RESCHED.
which approaches = when m, common regime in scheduling where the number of opera- tions greatly exceeds the number of machines. In experimental settings, the number of operations typically 10-40 times larger than the number machines (i.e., n = 10m-40m (0m-40m), which implies a reduction of about 10-40x in attention computation when KV cache is applied.
While this caching mechanism is not yet implemented in our current experiments, it presents a promising future direction for further inference-ting acceleration.
D PROOF OF STATE-DEPENDENS OPTIMALITY IN SCHEDULING
Proof. Fix any decision step and any state S. S. By Definition 4.1, S, uniquely specifies the following elements: (i) the available time A7T of each machine m;; (ii) for every job j. the completion status of its operations up f, which is equivalent to knowing the finish time of the dependency (020); and (iv)
most recently scheduled operation of j; (iii) the
operation-machine feasibility graph with duration (O2M).
Let ( be the set of all operations in the scheduling instance described by S. From element (ii), we can uniquely determine the subset
Oylone (S:) C
of operations that have already been completed by step t, and hence the set of remaining operations
ree ( = doooe(S.))
From elements (iii) and (iv), we know for every pair of operations in O their precedence relations, and for every operation in O the set of feasible machines together with the corresponding durations. Restricting these relations to Orem (S.) yields
(a) all remaining precedence constraints among operations in O (S:),
(b) all remaining duration and feahiit-feasibilityy constraints for operations in Orem (St).
Finally, element (i) gives the current available time ATTM of every machine m. From element (ii) we know exactly which operations have already been completed, and thus the set of remaining op- erations O (S.). Element (iii) specifies all precedence constraints between operations; restricting to rem (S,) yields the remaining 020 dependencies. Element (iv) specifies, for each operation, the of feasible machines and their processing durations; restricting it Orem(()) yields the remaining 02M relations.
Any feasible completion of the schedule starting from S, must therefore 1) assign each operation in Orem(S) to exactly one machine that is feasible according to the restricted O2M graph: 2) respect all restricted precedence constraints among operations in Orem (S.); and 3) choose start time for each operation that is not earlier than both the available time ATT of its assigned machine and the finish times of all its predecessors.
Let F(S,) denote the set of all schedules for the remaining operations that satisfy 1)-3). By con- struction, this feasible completion set F(S:) completely determined by the tuple
(AT!)) grem(S.), restricted 020, restricted 02M),
21

---

Published as a conference paper at ICLR 2026
which itself is uniquely determined by St through elements (i) above. In particular, F(S)) depends only on the current state S, and not on which trajectory has led to S..
Now consider any two scheduling trajectories TI and т2 (possibly defined on different execution histories) that reach the same state Sy. Let F(S,) denote the set all feasible completions of the schedule starting from St, that is, all feasible ways to schedule the remaining operations in Orem Since F(S,) is a function of S, only, the feasible solution set for the remaining sub- problem induced by Ti and 72 identical. For any objective that depends only the operation finish times (for example, the makespan), each completion in F(S,) has the same objective value regardless of whether it is viewed
continuation of тi or 72. Hence the optimal objective value and the set of optimal completions from St are the same for both trajectories. This proves that the corresponding remaining subproblems share an identical feasible solution set and the same set of optimal solutions, which establishes the proposition.
L
E RESCHED WITH PROXIMAL POLICY OPTIMIZATION
In the main paper train RESCHED with REINFORCE, following standard practice in Transformer- based neural combinatorial optimization (e.g., AM (Kool et al., 2019) and POMO (Kwon et al., 2020)). This choice keeps the implementation simple and allows to fo- cus on our main contributions, namely the state representation and network architecture. To verify that our framework is not tied REINFORCE, and to align with the PPO-based baseline DANIEL, we also implement a PPO version of RESCHED (denoted as RESCHED-PPO).
E. TRAINING ALGORITHM WITH PPO
We also train RESCHED with Proximal Policy Optimization (PPO) using a clipped surrogate objec- tive and generalized advantage estimation (GAE); the procedure is summarized in Algorithm 2.
E.2 PPO CONHIGURATION AND EXPERIMENTAL SETUP
In the PPO version, we keep the state representation and network architecture identical to the RE- INFORCE version. The PPO implementation follows the elipped-surrogate variant with generalized advantage estimation (GAE). Unless otherwise stated, adopt the same critic architecture and PPO hyperparameters as DANIEL (Wang et al., 2024b), i.c., discount factor y = 1, GAE parameter = 0.98, clip range E 0.2, value-loss coefficient C, 0.5 and entropy coefficient c. 0.01. The critic shares the encoder with the policy network and adds a small MLP head that outputs a scalar state value (st).
Experimental setting. We evaluate RESCHED-PPEE on our main task, FISP, and for simplicity we restrict the comparison to the strongest DRL-based method specifically designed for FJSP, DANIEL. We keep the same training and test splits as in the main paper: models are trained on synthetic instances from the SD,/SD2 datasets and evaluated under greedy decoding strategy on (i) in- distribution synthetic instances, (ii) -ui-tf-distribution synthetic instances of larger sizes, and (iii) open FJSP benchmarks.
Training budget. For clarity, we measure the training budget terms of the effective number of trajectory updates.
In vanilla REINFORCE, each sampled trajectory used once for a single gradient update. In the main-paper configuration, we run 2000 updates and collect 1000 trajectories per update, which yields 2000 x 1000 2,000,000 trajectories. We adopted this relatively large budget to compensate for the higher variance and lower sample efficiency of REINFORCE and to stabilize training.
In PPO, for each policy update we collect a batch B trajectories from the environment and reuse them for K optimization epochs, which corresponds to BK effective trajectories per policy update. To disentangle the effect of the RL algorithm from that of the training budget, and to enable a fair comparison with DANIEL, consider two budget regimes: In the small-budget setting, choose U 400 updates with B 50 trajectories per update and K = 4 PPO epochs, resulting in 400 50 x 4 80.000 effective trajectory updates. This matches the training budget used
22

---

Published as a conference paper at ICLR 2026
Algorithm 2 Training RESCHED with PPO
1: Input: scheduling environment &, model parameters 0, total number of policy updates U, num- ber of trajectories per update B, mini-batch size M, number of PPO epochs K per update, discount factor 7/, GAE parameter X, clip range learning rate
2: for update u = to U do
3: Set old parameters Outa f- 8;
4: Initialize buffer D <- V:
5: for 1 to B do
6: Sample training instance from & and reset to get initial state so: Initialize trajectory T
7:
8: repeat
9:
Encode current state 8 and compute Te (- st) and Ve.. (s:);
10:
Sample action a (- st);
Execute at to obtain reward r, and next state 81+1;
12:
Store (st, 0t, Ft. Vau (8c), log Ten (ag 8e)) into T;
13:
St f- St+1;
14:
until the scheduling instance is finished
15:
Append all time steps in to buffer D; end for
16:
17:
Using rewards and old values in D, compute returns RG and advantages A, with GAB(?, A);
18:
for PPO epoch k = 1 to K do
19:
Shuffle D and split into mini-batches of size M;
for each mini-batch B c. D do
21:
For all (st, az) in B, compute Te st) and Vo(s)); Let Pt Ta 8t), p. Te (a: 8t), and r: = Pe/p.
23:
Policy loss:
policc
EieB minn(rA,, clip(r,, +,1+
24:
Value loss with clipping:
Lvalue
Ere max ((Vo(s)) RR,²
(Vonu clipp(Vo(ss) Va (sr), -8,8) R=)
25:
Entropy bonus: Lentroy ErEB ( st))];
26:
Total loss: L = Lpolic + Lvalue + co Centopyi
27:
Update parameters: x- f aVoL; end for
28:
29:
end for
30:
Optionally step the learning-rate scheduler and evaluate me validation set;
31:
end for
Output: trained model parameters
by DANIEL, for which we report the original DANIEL results while retraining both RESCHED- REINFORCE and RESCHED-PPO under the same budget. In the large-budget setting, we increase by a factor of 25 so that both DANIEL and RESCHED-PPO are retrained with approximately 2,000,000 effective trajectory updates, matching the budget of our original RESCHEED-REINFORC configuration, for which we directly reuse the main-paper model.
E.3 COMPARISON OF RESCHED AND DANIEL UNDER DIFFERENT TRAINING BUDGETS
The results for DANIEL, RESCHED-REINFOREE and RESCHED-PPO are reported in Table 10.
In-distribution performance under a small training budget. Under the small-budget configu- ration, RESCHED-PPO converges in noticeably fewer updates than RESCHED-REINFORCE and
23

---

Published as a conference paper at ICLR 2026
Table 10: Results on FJSP: in-distribution (top); out-of-distriuttion (middle); benchmark (bottom)
Dattwet
Size
Pill
Nexil Iraising bedget
Lorxx traistaa tradget
Cill-Sassh
10
31.06
24.25 15775
19:83
17:58
11U.7
16.41
11:31
9:22
$3.24
11:15
96-13 (583)
Gaa
28.05
3016
19:11
12:43
13:41
12:30
6.51
23 10%
19:22
33.25
12:30
10.30
1.31
6.97
3.50
-1.43
044
40.35
195.56.00 (19))
Gape/511
76.47
$7.00
72.53
T601
25.68
16.77
34.75
(W66)
8
Gagr1911
24.50
39:91
76.39
71.31
11.32
1076
0.31
8.80
608
002.1 10%
(256)
134.96
38.09
Arg.
43.53
59.53
$5.82
19:45
12.42
17.39
Top PIMA
Squall tratetng baadast REINFORCE
training bodtect
Datavt
Stee
SPT
XWWX
10.
DANIFI
20xx. 111
10 x.6
21 30
10
ReSeree PPO
20/ L0
M0 3
DANIEI
201 50
Rescemn REINRORCE
10:55
20 x
30 x.5 25 111
ReSeeen PRO
OR Tools
3.50
4,3
4.50
3.44
234 (AR)
21,06
13.57
3.65
1.52
8.04
3.97
2.19
9.25
0.98
0.59
2.34
1.64
2.06
1.45
965.06 (24))
g
18.24
106.08
-187
23.29
-3.99
-1.29
4.50
22.00
-.38
928.39 (0%5
Cupett
35.00
64.72
508
3.38
3.15
4.00
7.29
3.09
Strotegy
Dataset
MWKR
DANIEL
RESCIRD REINFORCE
ReSCHED PPO
ISGA
OK-Toels
Brydimaane
Capt1511
78:M1
13.58
12.97
14:35
10.52
11:77
1758)
174 2011 58)
132.7
Gap/9611
18.60
16.33
14.41
18.06
15.34
15.29
20.00
1028. 03: 003--30-0000 0.0248)
1028.83
Small training budget
Harmkindata
Capr161
13.85
11.42
12.07
10.38
9.92
1045
13.44
105-800.119)
935
934.25
Hurisk(vbbaa)
(ap/5)]
4.72
1.38
3.95
2.67
2.87
4.56
812.2000 9956)
919 919600-30193
919.95
Gup/9)
10.56
Brandimane
Capt9611
29.91
14,10
14.55
9:08
12.49
10.34
10.97
175.2003 1719)
114.201155))
172.7
Gegt%)
18.80
14.67
13:21
15:48
18:34
16.25
18.0
1028 0076
1028.80
Large training budget
Harmnsidaata)
13.8%
11.20
10.34
10.38
10.31
10.59
10.42
983 3000 (19)
954.25
4.22
3.17
3.42
3.48
2.55
6.41
3990)
919.000-000900
Gup/811
10.42
1. OR-Tools (1800s per instance): solution and optimal ratio reported;
2. UB is the best-known solution (Bchnke & Geiger, 2012), used the baseline to compute gaps;
3. Instance-wise average gap is reported to reduce bias from varying instance scales.
achieves the best average in distribbution performance, with an average gap of 12.42% compared to 14.35% for BESCHED-REINFORC and 19.45% for DANIEL. Even the REINFORCE version, de- spite its slower convergence, still surpasses DANIEL in terms of average optimality gap, indicating that the main gain comes from our architecture rather than from using larger training budget. PPO further exploits the limited data more efficiently than REINFORCE, yielding the best average results among all compared methods.
Out-of-distributinn performance under a small training budget. In the out-of-distribttion set- ting, models trained on 10x5 and -2x evaluated on larger unseen instances. Under the small training budget, as shown in Table 10, RESCHED-PPO trained only on SDx510x5 al- ready achieves the best average OOD performance, achieves the best average OOD performance (2.72% gap), outperforming both DANIEL and tecture combined with PPO can generalize well even when trained on the smallest problem size with limited data. In contrast, the REINFORCE version trained on 1005 generalizes poorly under this small budget, which attributed to its lower sample efficiency. However, when the training size is increased to S2, 10 (with the same budget), its OOD performance improves substantially and becomes comparable to DANIEL. Overall, these results indicate that our architecture does general- ize beyond the training size, with PPO exploiting limited data more efficiently (as PPO trains the policy multiple times on the same data), whereas REINFORCE requires somewhat richer training instances to reach similar level of OOD performance.
showing that our archi-
Open benchmark performance under small training budget. On the open benchmark sets, all DRL-based methods achieve very similar average performance under the small training bud- get. In particular, the REINFORCE and PPO versions of RESCHED trained on small synthetic instances remain competitive with the best DANIEL configuration. Specifically, the REINFORCE- based RESCHED requires approximately 30 minutes to train on the 10x5 instances, while the PPO-based version trains in about 20 minutes. In comparison, HGNN (Song et al., 2023) and DANIEL (Wang et al., 2024b) require about 21 minutes and 18 minutes, respectively, to complete the same training. This indicates that, with only small amount of training data and short training time. current DaL-based methods already reach a reasonably strong level on real-worth scheduling benchmarks, highlighting their practical potential for real scheduling applications.
24

---

Published as a conference paper at ICLR 2026
In-distribution performance under large training budget. Under the large-budget set- ting. both RESCHED versions benefit from the increased data: the average gap of RESCHED- REINFORCE drops from 14.35% 10.30%, and RESCHED-PPO further improves it to 9.02%. RESCHED-PPO consistently improves over the REINFORCE version across almost all datasets. DANIEL also benefits from the larger budget, yet even the REINFORCE version of RESCHED now clearly outperforms DANIEL on most SD2 and medium-sized SD₁ instances, and the RESCHED- PPO achieves the best average in-distribution performance overall. This shows that, even when DANIEL is given comparable large training budget, the proposed architecture (especially with PPO) remains substantially stronger.
ooto---distribution performance under a large training budget. In the out-of-distribtiion set- ting with large training budget, both RESCUED versions clearly outperform DANIEL on average, and the PPO version consistently improves over the REINFORCE version across most datasets.
Interestingly, when we increase the training budget of DANIEL by 25x, its OOD performance on the SD₂ datasets does not improve and even degrades compared to the original setting. This sug- gests that, under the current training setup, DANIEL does not clearly benefit from additional data, which may partly explain why the original work chose a relatively small training budget. In con- trast, RESCUED continues to improve when the training budget increased, indicating that our architecture can effectively leverage more trajectories.
Open benchmark performance under a large training budget. On the open benchmark, all DRL-based methods achieve very similar performance under the large training budget, with only minor differences in gaps. RESCUED (both REINFORCE and PPO) remains competitive with DANIEL, indicating that models trained on synthetic SD₁ instances transfer reasonably well to these open benchmark and do not exhibit noticeable overfitting to the synthetic distribution.
These new experiments show that architecture works well with both REINFORCE and PPO: the PPO version converges faster and further improves in-distribution and out-of-distribution per- formance, while the REINFORCE version already remains competitive better than DANIEL un- der matched budgets. In particular, replacing REINFORCE with the stronger PPO algorithm further improves RESCHED's performance, demonstrating that our framework can directly benefit from stronger RL algorithms. Overall, across all budgets and RL algorithms, RESCHED consistently matches or outperforms DANIEL, indicating that the benefits come from our framework rather than from the large amount of training data.
F ADDITIONAL ABLATIONS AND DESIGN CHOICES OF RESCHED
Reward Design In our early framework explorations, we tested three different reward formula- tions: A A-makespan (the change in makespan before and after taking an action), estimated mean re- ward Song et al. (2023), and estimated lower-bound reward Zhang et al. (2020): Wang et al. (2024b). As summarized in Table 12, all three variants are able to train a reasonable policy, but the choice of reward has noticeable impact on generalization. In particular, the delta-makespan reward tends fit the synthetic distribution more aggressively: can slightly improve average performance on synthetic OOD instances, but it significantly degrades performance pared to the estimated lower-bound reward, which we interpret as a form of overfitting to the syn- thetic training distribution. As the estimated lower-bound reward is commonly used in DRL based scheduling methods like L2D (Zhang et al., 2020) and DANIEL (Wang et al., 2024b), we also use to align with the standard practice.
the open benchmarks com-
Discount Factor We initially set the discount factor to y = 0.99, following standard deep RL practices. To investigate the impact of this hyperparameter, ments with y = 1.0. The results, summarized in Table 13, show that our method is not sensitive to this hyperparameter choice, and we have maintained 7 0.99 in our main configuration.
also performed additional experi-
25

---

Published as a conference paper at ICLR 2026
Table 12: Effect of different reward the performance of RESCHED.
Dataset
Est LB
Est Mean
-Makespan
In-distribution
SD
12.25
12.56
13.05
Out-of-distribuiin
10
3.44
3.29
3,30
SD,440x10
2,54
2.15
2.41
SD,-30x10
8.79
9.19
7.53
40
-2.40
-2.57
-4.30
Avg.
3.09
3.015
2.24
Open Benchmark
Brandimarte
9.08
9.66
15.35
Hurink (edata)
15.48
16.58
17.27
Hurink (rdata)
10.18
10.34
11.62
Hurink (vdata)
3,48
2.75
4.50
Avg.
9.56
9.83
12.19
Table 13: Effect of the discount factor y on the performance of RESCHED.
Dataset
RuScHeD--1.9-Avg
Rešcoun-1.--Agg.
BeScHenn-L.-seell
RESCHEED1 O-sced2
RESCHED-1 Al-eeds
In-distribution
05
11.75
11.75
11.41
11.76
12.07
Out-of-distribation
SD;-30x10
3.10
3,10
2,63
3.69
2.97
SD:440x10
3D,-30=10
9.04
10.03
8.28
11.58
10.22
40xx40110
-2.61
-2.09
-3.55
-0.11
-2.61
Avg.
3.31
2.34
4.42
Open Benchmark
Brandimarte
Hurink (edata)
15.84
16.25
16.03
16.89
15.85
Hurink (ndata)
10.13
10:50
10.49
10:11
10.91
Hurink (yclata)
2.67
2,66
2.37
2.98
Avg.
9.78
10.24
10.41
9.92
10.39
Values are average optimality gaps (%) w.r.t. the hest-known upper hounds. "-Avg." denote averages over four and three seeds, respectively.
G FREQUENTLY ASKED QUESTIONS
G.1 RESCHED EXCEL ON FJSP BUT ARE LESS COMPETITIVE ON RECENT JSP BASELINES. WHAT STRUCTURAL OR DISTRIBUTIONAL DIFFERENCES MAKE JSSP HARDER FOR RESCHED?
As the instance distribution of FJSP moves closer to a pure JSSP (one feasible machine per opera- tion), the relative advantage FISP-oriented DRL methods becomes smaller. This phenomenon is not specific to RESCHED; it also appears on existing FJSP baselines. For example, on the Hurink benchmarks for FISP, edata has on average only 1.15 feasible machines per operation (very close to JSSP), whereas rdata has 2 and vdata has about (m/2) machines operation. As shown in Table 14, all three FJSP methods (HGNN, DANIEL, and RESCHED) perform worst on edata and improve as the flexibility increases from edata - rdata vdata.
Beyond the empirical trend observed on the Hurink dataset, we would like to highlight structural reason for this behavior. Methods for the Flexible JSP (FJSP), including own, are explicitly designed to model the interactions between operations and machines. Our architecture, for instance, incorporates dedicated O2M branch and machine nodes, whose primary function is to resolve assignments among multiple feasible machines and balance their loads.
In strict JSP instances, however, this flexibility is absent, each operation is assigned to a single feasible machine. Consequently, the O2M decision structure becomes less critical, and a portion of the model's 's dedicated capacity is consequently less informative. The challenge in these instances
26

---

Published as a conference paper at ICLR 2026
Table 14: Perfprmance degradation analysis for RL approaches.
Dataset
Avg. machines/oper
HIGNN 10:5
DANIEL 10:5
ReSched 10
Hurink (edata)
1.15
15.53
16.33
15.48
Hurink (adasa)
2
11.15
11.42
10.18
Hurink (vdate)
4,25
3.28
3,48
shifts predominantly to resolving fine-grained sequencing conflicts along predetermined machine routes.
In contrast, many recent JSP-tailored methods simplify the representation by pooling machine- related information into aggregated operation features, effectively modeling the problem an operation-ons -onloonooyyyyooo graph (Lee & Kim, 2024; Zhang et al., 2020; Park et al.. 2021b; Chen et al., 2023; Park et al., 2021a; Iklassov et al., 2023). This abstraction can enable the model to concentrate more directly on resolving sequencing conflicts within a fixed disjunctive graph, which may yield stronger performance on classic JSP benchmarks.
However, we posit that in practical manufacturing settings, an operation is intrinsically linked to its machine resources, as embodied by attributes like machine-specific processing times. This is why our framework intentionally maintains distinct operation and machine nodes with explicit O20 and O2M edges. This architectural choice necessarily trades off some degree of short-term, JSP-specific optimality to achieve more generalizable, faithful, and extensible model. It is specifically designed to accommodate FISP and other complex variants where machine ficxibility and richer precedence structures are fundamental to the problem.
G.2 THE FISP, JSSP, AND FFSP REPRESENT RELATIVELY LIMITED AND LESS COMPLEX SCHEDULING PROBLEMS. HOw COULD THIS APPROACH BE EXTENDED TO HANDLE BROADER RANGE OF SCHEDULING PROBLEMS, INCLUDING THOSE WITH MORE DIVERSE AND REALISTIC CONSTRAINTS ENCOUNTERED IN REAL-WORLD APPLICATIONS?
The goal of RESCHED is precisely to build a simple and generic framework that can be quickly adapted different scheduling or sxource-alllcaatiin scenarios. To this end, we start from FJSP as generic formulation, view other classic shceudling problems (JSSP, FFSP) through a heterogeneous operation machine graph, and deliberately avoid problem-specifi features or heuristics in both the state representation and the network architecture. This is why the same model can already handle FISP, JSSP, and FFSP without any architectural changes.
As a concrete example, dependent task offloading in mobile edge computing (Wang et al., 2022; Xiao et al., 2025; Wang et al., 2020) can be viewed as an instance of our formulation. In this problem, an application is modeled the scheduler must decide for each ready task whether to execute locally or offload to one of several heterogeneous edge/cloud servers, subject to communication and resource limits, in order to minimize end-to-end latency (or latency-energy tradc-off).
DAG of computation tasks with precedence constraints, and
In this case, each computation task in DAG corresponds to operation node, and each local device, edge server, or cloud node corresponds to a machine node. Task dependencies form the 020 edges, while the end-to-end latency for executing task on given resource (communication plus compu- tation, or purely computation for local execution) defines the O2M edge durations, with infeasible assignments masked out. Under this mapping, the task DAG is directly represented as the 020 con- nection mask fed into the operation branch, so no architectural change is required. The scheduler's decision at each step select a feasible task-resource pair, and the objective is typically function of task completion times such as total latency or a latency-energy trade-off. Our state representation and dual-branch Transformer can thus be reused without modification; only the duration model and reward definition need to be adapted, illustrating how RESCHED can be extended to more realistic scheduling scenarios.
H STATEMENT ON THE USE OF LARGE LANGUAGE MODELS (LLMS)
We used large language models (c.g., ChatGPT) as a general-purposs. purpose assistant for language polish- ing (grammar, wording, clarity) and for suggesting occasional non-substantive code snippets. L.LMs
27

---

Published as a conference paper at ICLR 2026
not used for problem formulation, algorithm/model design, experimental design analysis, data generation, or drawing conclusions. All core code and technical content were implemented and verified by us. We reviewed and edited all LLM-assisted text and code, and take full responsibility for every part of the manuscript, including sections that benefited from LLM assistance.
28


Reviews:
[{"review_id": "qmJUEQYWFI", "reviewer": "Reviewer_1Xow", "summary": "The paper proposes RESCHED, a deep reinforcement learning framework for solving scheduling problems. It proposes a simplified state representation and Transformers to solve Job Shop Scheduling Problems. The experiments show better performance than DANIEL, and RESCHED is even surpassing OR-TOOLS on 40x10 instances. The architecture used is a decoder only architecture and the reinforcement learning algorithm is REINFORCE. It learns a policy that is then used either greedily or with sampling.", "questions": "Can you detail the sampling algorithm used in Table 1?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper has good results on large instances.\nA new state representation and architecture are proposed.", "weaknesses": "The writing is not polished (Experments, Dateset, ...)\nThe training times of the different DRL approaches are not compared.\nIt would be better to also have OR-TOOLS on Taillard benchmark.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "75GFh3IKu4", "reviewer": "Reviewer_cunA", "summary": "The paper claims that a minimal Markov-sufficient state for FJSP can be formed using four core features. It tries to remove historical dependencies, redundancy, and auxiliary variables from node features, and introduces a dual-branch Transformer: an operations branch with self-attention enhanced by RoPE and a machine branch with cross-attention that injects edge features and self-connections to stabilize operation–machine imbalance. The method reports SOTA on FJSP with promising transfer to JSSP/FFSP.", "questions": "1. Can you provide a formal proof that the four-feature state is Markov-sufficient (proposition 1)?\n\n2. You excel on FJSP but are less competitive on recent JSP baselines. What structural or distributional differences make JSP harder for your method?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper shows that strong performance is possible with a small, domain-aware feature set.\n\nStructure-aware Transformer well aligned with precedence and operation-machine eligibility.\n\nIt demonstrates sample efficiency and generalization across instance sizes in FJSP, one of the most challenging COPs.", "weaknesses": "The “minimal MDP” claim (proposition 1) lacks a formal proof; it relies mainly on empirical results.\n\nRelated work on feature minimization is incomplete: Lee & Kim (2024) already aimed to remove historical dependencies and relative time feature (global minimum available time subtraction) in JSSP; conceptually aligned with “State: SubProblem” design (line 229 in this paper). Authors analyze only DANIEL (Wang et al., 2024b) features in FJSP, but feature minimization in JSSP had already been explored. \n- Lee, J. H., & Kim, H. J. (2025). Graph-based imitation learning for real-time job shop dispatcher. IEEE T-ASE.\n\nJSP comparisons are incomplete and relatively weak. While FJSP results include several recent methods, JSP needs stronger baselines. For example:\n– Park, J., Bakhtiyar, S., & Park, J. (2021). ScheduleNet. arXiv:2106.03051.\n– Chen, R., Li, W., & Yang, H. (2022). TII 19(2):1322–1331.\n– Iklassov, Z. et al. (2023). IJCAI, pp. 5350–5358.\n– Lee, J. H., & Kim, H. J. (2025). Graph-based imitation learning for real-time job shop dispatcher. IEEE T-ASE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kNlP9GW0Pb", "reviewer": "Reviewer_54We", "summary": "This paper presents a new neural network architecture and training procedure for different types of scheduling problems, with a particular focus on the FJSSP. The authors also discuss applications to the classical JSSP and the Flow Shop Scheduling Problem.\n\nThe main idea of this work is to employ a simplified feature space as input encoding for a transformer-based architecture that uses a non-learnable positional encoding. In contrast to previous research that relies on extensive and often redundant feature representations, the authors deliberately restrict the input to a small set of features that effectively capture the current system state without incorporating information about past actions. This enables the network to focus on a specific sub-problem at each action step.\n\nThrough extensive experiments, the authors demonstrate that their method outperforms several existing approaches and is capable of establishing new benchmark results across a variety of problem instances and sizes. The model is trained using deep reinforcement learning with the REINFORCE algorithm, where advantage estimates are incorporated into the policy gradient computation.\n\nThe authors also state that they plan to release their implementation publicly.", "questions": "1. In Appendix B.3, could you clarify whether the machine embeddings are entirely removed, or whether only the global descriptors are excluded? If no machine features are present, it is unclear how the Dual Attention Network would function. Were these embeddings perhaps replaced with placeholder values, such as zero entries?\n2. How does your method compare to the DANIEL network when both use a reduced feature space? In the appendix, you demonstrate that the DANIEL network improves in performance when fewer features are used. Furthermore, Table 1 shows that the DANIEL network generally performs as the second-best method and even outperforms your proposed approach in certain cases. How would a feature-reduced version of the DANIEL network compare directly to your method?\n3. The paper presents several ablation studies analyzing various components of the proposed model, but the choice of the REINFORCE algorithm appears to have been assumed without direct justification. Since all competing methods were trained using a Proximal Policy Optimization algorithm, was this alternative also tested? If so, did it yield inferior results? Including such a comparison in the ablation studies would strengthen the empirical analysis.\n4. How does the formulation of the reward function impact the training process? This question is particularly relevant since the DANIEL method learns based on the change in the current makespan rather than the change in the expected lower bound.\n5. Why was the inference speed presented in only a single figure and not compared across all experiments?\n6. Why were no ablation studies conducted on the network size, such as the number of attention heads or Transformer block dimensions? This seems highly relevant when introducing a new architecture.\n7. Why was the RoPE positional encoding chosen? Were other positional encoding methods considered, and how might their use impact learning performance, particularly regarding inference speed and makespan?\n8. A variety of metaheuristics exist for solving the FJSP. Why were none of these methods investigated or compared against the proposed approach?\n9. The FJSP, JSSP, and FFSP represent relatively limited and less complex scheduling problems. How could this approach be extended to handle a broader range of scheduling problems, including those with more diverse and realistic constraints encountered in real-world applications?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper strikes a balanced narrative between reviewing foundational concepts of the FJSSP and introducing the method. Explanations are concise and accessible, enabling readers to follow both theoretical background and model design decisions.\n\n- Although the transformer architecture itself is not new, the authors extend it with relevant innovations (such as rotary positional encodings) and tailor the input representation to the scheduling context. Further, the authors introduces a deliberate feature reduction strategy, focusing only on state-relevant features, a nontrivial design choice in scheduling, where feature selection is often a bottleneck. In sum, the application and evaluation of these architectural modifications in FJSSP (and its extensions) represent a creative adaptation of transformer models to a new domain.\n\n- The paper provides a solid theoretical justification for using a reduced feature space as input to the transformer network. The claims are supported by a direct comparison with another SotA method that uses a richer feature representation, showing improved performance under feature restriction. Comprehensive ablation studies isolate and quantify the contribution of architectural components.\n\n- The proposed method consistently outperforms strong baselines in extensive experiments including both greedy and sampling-based inference strategies. The authors demonstrate a generalization to classical JSSP and FSSP indicating high potential for broader applicability beyond the initial problem formulation. The results contribute actionable insights to the research community, emphasizing the importance of carefully chosen feature representations in neural approaches to scheduling.", "weaknesses": "- The experimental evaluation lacks a comparison of computation time between the proposed method and other neural network–based approaches. This is particularly relevant because the method supports sampling-based inference, which may introduce higher computational cost. A runtime analysis (such as wall-clock time per episode or inference step) would clarify the trade-off between solution quality and computational efficiency and help position the method against deep learning baselines.\n\n- In Figure 1a, the use of plus signs suggests that both solutions are combined to generate a schedule, although the solutions seem independent and not actually aggregated. This may mislead readers. In Figure 2, certain elements, especially the graphs in the upper part of the decision-making module, are not clearly explained in the text, making their meaning and role ambiguous. Enhancing these figures or adding brief explanations in the caption would improve interpretability.\n\n- In the appendix, the authors show that the DANIEL network improves notably when fewer features are used. Table 1 further indicates that DANIEL is generally the second-best method and even outperforms the proposed approach in certain cases. However, the paper does not evaluate how a feature-reduced DANIEL network would perform directly against the proposed model. Since the central contribution of the paper is the effectiveness of a reduced feature space, a head-to-head comparison with a feature-restricted DANIEL baseline would be essential to validate that the performance gain is due to the proposed method, and not merely an effect of feature reduction.\n\n- Appendix C presents a key–value cache mechanism, but its relevance to the main paper is unclear, as no inference-time results are reported. Without linking the cache mechanism to performance measurements, the section feels isolated rather than integrated into the contribution. Including inference-time evaluation, or explicitly discussing when and how the cache is beneficial, would strengthen the connection to the main content.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IvvgDjyrtz", "reviewer": "Reviewer_WVwe", "summary": "This paper introduces ReSched that emphasizes a minimalist approach by redefining the state representation of FJSP, by only using four features compared to the current state-of-the-art method DANIEL, which uses a total of 26 features.  The paper also shows that many of the features of DANIEL are redundant and that performance increases when some are removed. Additionally, the paper introduces a novel network architecture, whereby they show through extensive testing the effect of the components of the network architecture. Their results indicate that ReSched outperforms DANIEL and other baselines, without a significant increase in the evaluation runtime.", "questions": "Could the authors explain why $\\gamma=0.99$, when it is normally set to $\\gamma=1$, such as for L2D and DANIEL?\n\nCould the authors maybe show if their proposed network architecture works well, with PPO or REINFORCE with a custom baseline? Their current motivation of REINFORCE being simpler is not strong, given that we use methods like PPO for a reason, like better sample efficiency and more stable training.\n\nCould the authors show the performance of ReSched when trained on a similar amount of data as DANIEL and HGNN? \n\nIn Table 3, it is unclear whether ReSched uses the greedy or sampling evaluation for JSP. Could you please clarify which one is used?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The authors show that existing DRL work uses too many features to train, and they also show an ablation study for the features of DANIEL, further strengthening their claims for a minimalist approach.\n\nThe Ablation study of ReSched in Table 5 is well done, and it shows the effect of each introduced component of their network architecture.", "weaknesses": "The use of the REINFORCE algorithm over PPO is not well-justified. It is well-known that the vanilla REINFORCE method suffers from high variance, and the paper does not report training across multiple seeds. This raises doubts about the results presented in the paper, as training over multiple seeds might reveal that DANIEL outperforms ReSched. While DANIEL also trained on only a single seed, they used PPO, which is known to be more stable.\n\nREINFORCE is also known to be highly sample-inefficient. The paper states that ReSched trains for smaller instances for 2000 epochs, with 1000 instances each epoch, with a batch size of 50. This is significantly longer than baselines, as both HGNN and DANIEL, who also uses 1000 instances, but with a batch size of 20, train in a single “epoch”, meaning they only use these instances once. This means that DANIEL and HGNN will have $1000 \\times 20= 20000$ different episodes to train on, whereas ReSched has $2000 \\times 50 \\times 1000= 100000000$. This means that ReSched has 5000 times the training data compared to the baselines, which it compares to. This could mean that HGNN and, especially, DANIEL could outperform ReSched whenever they are trained on the same amount of data.\n\nThe contribution of ReSched is marginal in my opinion, since it only introduces a new state representation and network architecture. Moreover, due to previously stated weaknesses, I am not fully convinced about the results and, consequently, the significance of these novel parts.\n\nThe paper uses Definitions, Propositions, Corollaries, and Remarks quite liberally. For example, Corollary 1 is completely based on unproven Proposition 1. I can understand that Proposition 1 is likely true, but I would not state it in this way without giving a formal proof.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)