Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling
Authors: Sirui Li
Wenbin Ouyang
Yining Ma
Cathy Wu
Venue: ICLR 2025 Poster (2025)
Keywords: Learning-Guided Optimization
Rolling Horizon Optimization
Flexible Job Shop Scheduling
Primary area: optimization

Abstract: Long-horizon combinatorial optimization problems (COPs), such as the Flexible Job-Shop Scheduling Problem (FJSP), often involve complex, interdependent decisions over extended time frames, posing significant challenges for existing solvers. While Rolling Horizon Optimization (RHO) addresses this by decomposing problems into overlapping shorter-horizon subproblems, such overlap often involves redundant computations. In this paper, we present L-RHO, the first learning-guided RHO framework for COPs. L-RHO employs a neural network to intelligently fix variables that in hindsight did not need to be re-optimized, resulting in smaller and thus easier-to-solve subproblems. For FJSP, this means identifying operations with unchanged machine assignments between consecutive subproblems. Applied to FJSP, L-RHO accelerates RHO by up to 54\% while significantly improving solution quality, outperforming other heuristic and learning-based baselines. We also provide in-depth discussions and verify the desirable adaptability and generalization of L-RHO across numerous FJSP variates, distributions, online scenarios and benchmark instances. Moreover, we provide a theoretical analysis to elucidate the conditions under which learning is beneficial.

Published as a conference paper at ICLR 2025
LEARNING-GUIDED ROLLING HORIZON OPTIMIZA- TION FOR LONG-HORIZON FLEXIBLE JOB-SHOP SCHEDULING
Sirui Li, Wenbin Ouyang, Yining Ma Cathy Wu
MIT
fairuil, oywenbin, yiningma, cathywujemit.ecm
ABSTRACT
Long-horizon combinatorial optimization problems (COPs), such as the Flexi- ble Job-Shop Scheduling Problem (FJSP), often involve complex, interdependent decisions over extended time framees posing significant challenges for existing solvers. While Rolling Horizon Optimization (RHO) addresses this by decom- posing problems into overlapping shorter-horizon subproblems, such overlap of- ten involves redundant computations.
this paper, we present L-RHO, the first learning-guided RHO framework for COPs. L-RHO employs neural network to intelligently fix variables that in hindsight did not need to be re-optimized, re- sulting in smaller and thus easier-to-solve subproblems. For FISP, this means identifying operations with unchanged machine assignments between consecutive subproblems. Applied to FISP, L-RHO accelerates RHO by up to 54% while sig- nificantly improving solution quality, outperforming other heuristic and learning- based baselines. We also provide in-depth discussions and verify the desirable adaptability and generalization of L-RHO across numerous FJSP variates, dis- tributions, online scenarios and benchmark instances. Morcover, we provide a theoretical analysis to elucidate the conditions under which learning is beneficial.
INTRODUCTION
Enhancing the efficiency and scalability of solving Combinatorial Optimization Problems (COPs) has been a central focus of both the Operations Research (OR) (Schrijver et al.] 2003) and the emerging Neural Combinatorial Optimization (NCO) communities (Bengio et al. 2021). Numer- ous methods have been proposed to decompose large-scale problems into smaller, more tractable subproblems, with the majority focusing on spatial or structural decomposition of decision vari- ables. Despite their success, these methods often face limitations in addressing the unique temporal challenges of long-horizon COPs frequently encountered by industrial practitioners which in- volve optimizing complex decisions over extended time horizons. Such unique challenges, coupled with the inherent NP -a-hhrdness and large-scale nature of the problems, call for advanced temporal decomposition strategies (Du and Pardalos 1998 Hentenryck and Bent. 2006 Yang et al. 2013).
Building on successes in control for complex dynamical systems (Welikala and Cassandras 2021
Franze and Lucial 2015 Castaman et al. (202T), Rolling Horizon Optimization (RHO) has emerged
as a natural temporal decompasition technique for Long-horizon COPs (Glomb et al., 2022). RHO breaks the problem into overlapping subproblems with shorter planning horizons rolling forward over time, allowing for much better scalability. The key to RHO is its temporal overlap, which enhances decision-making at the boundaries of consecutive subproblems, mitigating myopic deci- sions and facilitating modelling interdependencies across the temporal dimension (Sethi and Sorger, 1991 Mattingley et al.) 2011). However, such overlaps often lead to redundant computations that reduce the efficiency especially when only small subset of variables needs re-optimization. This presents an opportunity to accelerate RHO by identifying such redundancies, an approach that, to our knowledge, has not yet been explored in the combinatorial optimization context.
To this end, this work introduces a novel learning beasenng-based RHO framework, termed L-RHO, designed to accelerate RHO for long-horizon COPs by identifying overlapping decision variables that do

---

Published as a conference paper at ICLR 2025
not need to be re-optimized between consecutive iterations. We demonstrate the effectiveness of our L-RHO on the long-horizon Flexible Job-Shop Scheduling Problem (FJSP), a proof-of-concep
example with numerous applications in manufacturing (Liu et al.. 2017), healthcare (Addis et al. 2016), transportation (Zhang et al. 2012), and logistics (Xie et al. 2019). Long-horizon HJSPs represent a complex class of COPs involving interdependent assignment and scheduling decisions over extended time horizons, significantly increasing the difficulty compared to the basic JSP variant. The core of L-RHO to intelligently fix operations assigned the same machine across successive RHO iterations. By employing a customized network with tailored contextual embeddings, L-RHO learns to imitate a look-ahead oracle, effectively reducing the size of subproblems, significantly improving solve times, and delivering notable improvements in solution quality.
Moreover, to gain deeper insights into the research question "To what extent can machine learning accelerate RHO in the context of long-horizon COPs such as FJSP?" we validate and discuss our framework, L.-HO, through both computational experiments and theoretical analysis. Empirically, we show that L-RHO reduces RHO solve times by up to 54% and improves solution quality by up to 21% compared to various heuristic and learning-based baselines (with and without decomposition), across a range of FJSP settings and distributions. Moreover, of our L-RHO in online FJSP settings, where FJSPs operate with limited initial information and require ongoing but more efficient re-optimization as new orders arrive with dynamic environments. Theoretically, we formalize analytical criteria under which I.-HHO outperforms the heuristic base- lines; the analysis incorporates factors including the data distribution and the False Positive (FP) and False Negative (FN) Rates of the learning method, closely aligning with the empirical results.
further discuss the unique potential
(1) We introduce L-RHO, the first learning-guided rolling-horizon method for COPs; by learning which overlapping solutions in consecutive RHO iterations do not re- quire re-optimization, it significantly reduces RHO subproblem sizes and solve times. (2) Validated on long- morizon FJSP, L-RHO effectively accelerates RHO by up to 54% while largely improving the solution quality. (3) Extensive experiments show that L--HO consistently outperforms various ofate-of-the-art heuristic and learning-based baselines (w/ or w/o decomposition), and demonstrates robust effectiveness across diverse FJSP settings, distributions, and online scenarios.
Our contributions are fourfold:
(4) We further provide a principled probabilistic analysis to identify conditions where L-RHO surpasses heuristic RHO baselines, offering theoretical justifications that are aligned with the empirical observations.
RELATED WORKS
Decomposition for COPs. Despite advances in traditional solvers (Pisinger and Ropke 2019 Vi-
dal 2022; Xiong et al. 2022), learning-guider solvers (Labassi et al., [0022] Scavuzzo et al. 2022]
Wang et al. [023bb] Li et al. 2024) and neural solvers (Kool et al.] 2018 Ma et al. 2024 Zhang
et al. 2024c Ye et al. 2024a) for COPs, scalability and adaptability to real-world complexities re- main challenging. Various decomposition strategies have been explored by OR community, such as variable partitioning (Helsgaun 2017). adaptive randomized decomposition (ARD) (Pacino and Van Hentenryck] 2011). and sub- sub-problem constraint relaxation (Pisinger and Sigurd 2007). More recently, machine learning has been exploited to guide the decomposition by selecting subprob- lems et al. 2201 Zong et al. 2022] Huang et al. 2022) or to auto-regressively solve decomposed 2024), leading to notable improvements.
subproblems Wang et al. 202 I Ye However, they primarily emphasize spatial or mumblem-structure decomposition (e.g., for routing problems), which is not suitable for hong-horizon time-structured COPs involving complex, inter- dependent decision variables and constraints spanning extended time horizons. This highlights the need for effective temporal decomposition. We note such temporal decomposition can be orthogonal to other existing ones, and future work could combine them to improve scalability and flexibility.
2024b] Luo
RHO for Long-horizon COPs. RHO a temporal decomposition method originating from Model Predictive Control (MPC) (aarcia et al. 1989). It improves the scalability by dividing the time- structured problem into overlapping subproblems. While such overlap improves boundary decision- making, it can introduce redundant computations. Thus, many control and robotics studies leverage previous decisions to reduce the computations of the current subproblem. This is done, e.g., through hand-crafted methods, such as recording repeat computations (Hespanhol et al. 2019) or tightening primal and dual bounds (Marcucci and Tedrake 2020). and learning- based models that predict active constraints (Bertsimas and Stellato! 2022) solutions for discrete variables (Cauligi et al. 2021)
2

---

Published as a conference paper at ICLR 2025
However, these methods are not tailored for long-horizon COPs. Recently, RHO has been initially adapted for long-horizon COPs, with wide applications such as scheduling (Bischi et al. 2019). lot-sizing problems (Glomb et al.] (022), railway platform scheduling (Lu et al. 2022), stochastic supply chain management (Fattahi and Cioiindan| 2022), and pickup and delivery with time win- dows (Kim et al., 2023). However, they often overlook the redundancies, and none of them have integrated machine learning to address this issue, leaving a gap in accelerating RHO for COPs.
EJSPs. FISP is a complex class of COPs that involve interdependent assignment and scheduling de- cisions over extended time horizons, making it more challenging than the basic JSP, which only ad- dresses scheduling (Dauzère- Pérés et al. 2023). Recently, learning-base -asedd solvers have shown power to outperform traditional methods such as Constraint Programming (Perron and Didier) and genetic algorithms (L.i and Gao, 2016); for example, seerZhng al. | (2020; 2024b a) for JSP and Wang et al.. 2023c); [Song et (2022) for FJSP. However, they are typically limited to small-scale instances (fewer than 200 operations) and struggle to scale to real-world, long-horizon scenarios. Although decomposition (e.g., the above ARD) has been explored for FJSP, their efficiency remains con- strained. Moreover, these methods are offline, requiring full problem information, limiting their use in online setting. While some works have studied dynamic, online FJSP Luo et al. (2021); Lei al.. (023), they are still restricted to small-scale experiments. Consequently, large research gaps remain in developing more scalable and flexible decomposition methods for long-horizon (and online) FJSP.
3 PRELIMINARIES
FJSP Definition. A FISP instance consists of a set TT of jobs, a set M of machines, and a set O of operations. Each job 'T consists of set of n, operations {0 nn S O required to be processed in a precedence order 03,1 0222 + + + O,,,, Each operation Oj, can be processed by any of the compatible machines M,, M: the process duration of operation Oj, by machine m E EMys. is denoted by Pe, A solution to the FISP, denoted as II = (m, T), consists of (i) an assignment m. O + M that represents the machine assignment of each operation, with m(Qj,k) E Mj,k for all j. kt and (ii) a schedule π. {O,,k Vj, k} -> N that represents the process start time of each operation O,,k (Og,k); with the process duration Pj.k m)(),+) the process end time of the corresponding operation is (O,,,, := (OO,,,) + PPik literature, and we consider testing our method on variety of objectives including makespan (Xie 2019), total start delays (Pham and Klinkert 2008) Lee and Yih 2014). and end delays (Zhou ct al.
m((0,.), Many FJSP objectives exist in the
et al.
2009 Andrade-Pineda et al., 2020). Formally. the makespan objective can be expressed as maxo,, J.x Tel Te(k),)) For the delay-based objectives, let each operation O, be further associated with (i a release time $j.k with a constraint (OO,k) )) 2 $ such that the operation can only be processed after the release time, and (ii) a target end time fy both respect the operations' precedence orders
within the same job, that is, V job j and operations h < .22, we assume $j.k, S 8j,k2 and t I ty,62. The total start delay objective is expressed as Σo,, (0O,,)) - 8j,k. and the total end delay objective as Σo,, max(TT((0,,)) - f, 0). Appendix A. provides a detailed list of notations.
RHO for Long-Horizon FJSP. The temporal structure of FJSP enables the use of RHO to decom- pose a long- horg-horizon FJSP into a sequence of shorter-horizon FJSP subproblems.
Our RHO utilizes planning window size H but executes only a step size S with S S H. Each sub- problem is limited to solving for T seconds. Given the long-horizon FISP instance, we first sort the operations O into (Oa)) ...., O(01)) ) based on the precedence order within each job the associated release time. These operations are then divided into overlapping subproblems. Specifically, the th RHO iteration considers FJSP subproblem P. given by subset of operations Oplan,r. consisting of the next H non-executed operations according to the sorted RHO sequence order; we introduce additional constraints in P. to handle boundary conditions for example, each operation in O Optan.r should start after all previously executed operations from the same job. After solving P, under the time limit T, we obtain the subproblem solution 1I, = (m,,, T.). We then execute the first S operations with the earliest process start time π,, (O) following the solution I1,, while deferring the remaining H - S operations for replanning in future iterations. The procedure is then repeated until we solve the full FJSP P. resulting in [O]/S subproblems. A detailed algorithm can be found in Appendix A.2 RHO is also well-suited for online settings with limited visibility, solving early operations while deferring the rest until future batches in the next iteration (see Sec. 5.2
3

---

Published as a conference paper at ICLR 2025
Assignment-Basse Subproblem Restriction
Subproblem Py
Triining Data Collection via a Lookkkbeed Oraaie
Prev. Assignment
Restricted Bubproblem
Machine
Oeorapping
Wachine
Machino
Dverlapping
Maciie 2
New
Inference: Prod Operatons Fichnnggmmemms
New
Operations
Fixed Machine
+
Supprobeer -Piee daaiition
Qurisamed
Assignments
Prev, Schedule Ky-1
(a)
(c)
(b)
Current Assignment
Current Assignment
Esoouuad
Nachina
Deerispiing
Machene
Macciin
Chachine
Solve f. with Subsolver
Overlapping Operation
Niw
Execute operations with earlier solution
schedule nt- (fixed step size S)
Current Schedule IT,
Current Schedole T,
(1
(e)
(d)
Figure 1: One iteration of our L-RHO pipeline. (a) Construct a subproblem P. with H non- executed operations in plan.r- This includes set of overlapping operations Ovvertap.r S Oplan.r each associated with a solution from the previous iteration given by the assignment m,-1 and the schedule ,, -- (b) Identify operations Ofa., S Oowerlap.r that in hindsight, their assignments did not need to be re-optimized; during training, Look-Ahead Oracle determines fin, by solving Pr for Q times; During inference, our learned neural network selects it. (c) Create a restricted subproblem P, by fixing the machine assignments for O fiz.r. (d) Feed P. to a subsolver, solve for up T seconds, and (e) Obtain an updated solution II, = (mr, my). (f) Execute a subset of S
operations in Ozxec,r S Oplan,r based on the solution II,.. We then repeat steps (a)-(f).
4 LEARNING-GUIDER ROLLING HORIZON OPTIMIZATION (L- (L-RHO)
We now introduce learning framework, L-RHO, that accelerates RHO for long-horizon FJSP. We refer to the original RHO, RHO for training data collection, and RHO for inference as RHOv. RHO and RHOtest- In the standard RHO,, each consecutive iterations r-1 and share overlapping operations Oovertap.r = Opian.r n Otonn.r-1 While new operations Onew,r Opton, Oplan.r-1 subproblem P. may change the solution of the overlap parts Ovverlap,rs we find two key observations that, for various FJSP distributions evaluated in Sec. 5
(1) A significant subset of the overlapping operations retain the same machine assignment between the consecutive optimizations. Formally, the shared operations given by jju,r {O
O Ovvertap. (O) m (O)). where 11, = (mr, n.) and II,-1 = (m, 1, 11 are the solutions of the unrestricted subproblem P. and P in RHOOp
(2) Let Pr be the restricted subproblem where we leverage the solution of the r- 1 RHO iteration and fix the machine assignments of the shared operations Or /iz.y" The solve time of P; is significantly reduced from that of the unrestricted subproblem P,.
Assignment- Based Subproblem Restriction. Based on these observations, we propose restricting the subproblem by fixing machine assignments for set of operations Ofzzr S overltap.r selected through oracle, learning. or heuristic methods. This results in the restricted subproblem P,, with a formal formulation provided in Appendix A.5.2] Notably, this approach can be easily extended to other subproblem restriction methods, which we leave for future work.
Our L-RHO Pipeline. We design the L-RHO pipeline (which is shown in Fig. I as follows: First, we collect training data via a Look-Ahead Oracle by solving the unrestricted subproblem P, and identifying 0j Oztzrr as the set of overlapping operations with the same assignments in m, and m,- 1- A neural network fe is then trained with such collected labels. During inference, fa predicts a subset O fir.r, from which we form the assignment-basee restricted subproblem P,. This largly speeds up the inference time optimization by replacing the expensive P. with the easier-to-solve P..
4

---

Published as a conference paper at ICLR 2025
Training Data Collection (RHOddata) At each iteration r, we solve the unrestricted sub- problem P. for Q 2 1 times under a time limit, resulting in Q possibly different solutions { = (m², +²)] We then use the highest overlapping machine assignment as the training labels. That is, let qº' = arg
EoreO.vertap.r V8,, with V = =m?(0")=m- 1(0)) We set the training labels yo = d8 for each operation O E Ovverlap.r- Intuitively, the solve time of FJSP subproblem reduces when more assignemnts are fixed. Empirically, we find the labels not only lead to short solve times but also high solution quality. We then obtain the set Of fic.r = 10 E O Overrtap.r 16- 1 and construct the assignment-base restricted subproblem p7 accordingly. Fig. 1 (b) top illustrates the data collection procedure RHO Comparing with RHO, that solves one unrestricted P. at each iteration, RitiOdat solves P. for Q times and the restricted P, one time, where Q trades-off data collection efficiency and the training label quality.
(vo MoO0o0ouertan
Input Features. The state 8, at each RHO iteration r consists of both the current FJSP subproblem P. and the previous solution 11,-1 (m--1,7--1). We design a rich set of input features, capturing FJSP state details for overlapping operations O Doverlap.r. new operations Onew.r. and machines T. For Ovverlap.r and T, we further design features to capture the previous solution's information, including previous assignment, duration and end time (see Appendix A.3 for details).
Neural Architecture. Our neural network fo pre- dicts the probability of whether each overlapping operation O E Overrlap. should be fixed at each state Sy. It consists of three parts: (1) Input Em- bedding: generate embeddings for each operation O overlap, U Onew. and each machine M, with separate MLPs. (2) Machine/Operation Concate- nation: concatenate the hidden feature of each overlapping operation O E Owvertop. with both the hidden feature of the previously assigned machine (0) E M, and a global feature obtained by a mean pooling. The concatenated features then pass through another MLP. (3) Output: each overlap- ping operation Ovvertap. passed through a final MIP layer to output the probability prediction. Notably, the purpose of (2) is to augment each operation with both local information from the previ- ously assigned machine, as well as global information from all entities, which include overlapping operations, new operations, and the machines. The illustration of ʃo is depicted in Fig. 2 The cur- rent simple architecture shows strong performance, and our preliminary comparisons with advanced architectures, such as Multi-heat heali-headdaee Attention, show no significant improvement (sce Appendix|AA6... we leave the exploration of more advanced designs in future work.
MLP Op-wite 0.6
Overlapping
MLP
Signoid 0.5 Bd
10p1
New Opecationn
Pool
Concat.
Glotcl
Machinas
Ansigned
Machine
Feoture
Machine Operation Concatenation
Figure 2: Our neural architecture fo to pre- dict the probability of whether each overlap- ping operation should fix the assignment.
Loss Function. We use weighted binary cross-entropy loss where Wpos 0 scales positive labels.
(s,e 0), vo) [u log fo (s,; O) + (1 yo) log(1 - fo(s;: O))]
The weight Wpos balances False Positive (FPR) and False Negative Rate (FNR). A Wpos < em- phasizes avoiding predicting False Positives, i.e., cases where the network incorrectly fixes changing operations, which can improve the objective but may increase solve time (see analysis in Sec. 6
Inference (RHO The inference is illustrated in Fig. (b) bottom, where we use the network fo to predict O pie,ri for each operation O E Ooverlap.r. we predict ÿo 1 O))2. which results in the fixed operation set O Ofiz,r {o E O Overloapr do = 1} and the associated assignment- based restricted subproblem P, solved RHO iteration r. By replacing the unrestricted P, with the restricted P,. the computation time can be greatly reduced in comparison with R11Op
EXPERIMENT
In Sec. 5.1 we evaluate L-RHO a standard offline setting, comparing it to various baselines for
long-hone horizon FJSP. Next, in Sec. 5.2 we dive into detailed analysis of L-RHO under different FJSP variants including online settings. We provide additional experimental results in Appendix [A.6] including deep dive on the architecture design and evaluation on a real-world dataset. We aim to
5

---

Published as a conference paper at ICLR 2025
answer: (1) To what extent does L-RHO improve upon competitive offline baseline methods and RHO variants? (2) Can L-RHO adapt to different FJSP distributions and objectives? Moreover, a unique benefit of RHO is its adaptability to online settings with limited visibility. As a step toward realistic online settings, we then study (3) Is L-RHO robust under noisy observation of process durations? (4) is I.-HO reliable under machine breakdowns?
We generate synthetic large-scale FJSP instances following common procedure in (Behnke and Geiger 2012), characterizes by (IMM) [T, where each job j has 10,,) } - n. operations. The total number of operations |[] ranges from 600 to 2000. Notably, the problem horizon in this work (c.g., 600-2000) is considerably larger than those in pre- vious studies (Wang et al.
FJSP Data Distribution and Solver.
2023a Behnne and Geiger 2012 Bauzére-Pééree and Paulli 1997 Hurink
et al. 1994, |Brandimarte 1993), which typically consider fewer than 500 operations. Following the 2024a by. we employ the competitive constraint programming (CP) solver
conventions (Zhang et al.
OR-Tools CP-SAT (Perron and Didier) to solve FJSP, with its detailed CP formulation provided in Appendix A.5.2 We consider makespan objective in Sec. 5.1 and delay-based objectives in Sec. 5.2
(start and end delay) for comprchensive evaluation. More details are in Appendix A.5.T
Proposed Method (L-RHO) Setup. We provide descriptions of the training set up in Appendix A.4 and the details on the choices of RHO parameters in Appendix A.5.4 and A.5.6
Baselines. We include range of traditional and learning- basclines, with and without decom- position for comprchensive evaluation (see Appendix A.5.3 for more details about baselines):
(1) Traditional solver w/o decomposition We include the widely used benchmark solver CP- SAT (Google (023) and Genetic Algorithm (GA) (Li and Gao (016).
(2) Learning-based solver w/o decomposition We compare with the state-of-the-art DRL con- structive method for FJSP (Wang et al. 2023a), which we denote as DRL-20K (using 20,000 training instances as in the original paper). We further compare with two recent learinng meth-
ods: DRL-Echeverria (Echeverria et al., 2023) and DRL-Ho (Ho et al. 2023).
(3) Traditional solver w/ decomposition We include the time decomposition method ARD-LNS
(Time-based) and machine decomposition method ARD-LNS MMchhne-basedd in (Pacino and
Van Hentenryck] 201I), which decompose large neighborhood search (LNS) by randomly fixing
temporal intervals machine subsets subproblems, respectively.
(4) Learning-gui guided solver w/ decomposition While learning-guided decomposition exist, e.g. for routing problems (Li et al. 2021), they are not adaptable to long-horizon COPs like FJSP. We thus opt to include an Oraicle-LNS (Time-based) baseline to estimate the upper bound of enhancing ARD-LNS. samples K subproblems and selects the best one by looking ahead.
(5) RHO decomposition We include Default RHO, where each iteration solves unrestricted FJSP subproblem P, without fixing any variables, and Warm-Start RHO, where previous ma- chine assignments of overlapping operations {m,-1 (O) A O O Doverlop.r) are provided as hints (not fixed) to CP-SAT as a warm start, akin to (Hespanhol et al. 2019) in control systems.
Evaluation Metric. We compare the objective and solve time in Table I Objective improvement (0I%) and time improvement (TI%) over Default RHO are reported in Table 2 an objective obj and solve time f, its OI and TI are calculated as (objo obb)/objj x 100% and (tu t)/to x 100%, respectively, where negative values indicate degradation.
For a solver with
5.1 CANONICAL OFFLINE FISP UNDER MAKESPAN OBJECTIVE
We consider the canonical oflline FJSP with makespan as the objective, with horizons up 2000 operations (significantly longer than literature). following similar synthetic data distribution as in Wang et al. (2023a). The number of jobs and machines are set to 20 and 10, respectively. For both L-RHO and DRL, we train separate models for 30, 40, and 60 operations per job, testing each in its respective setting and transferring the 60 operations-per-jonn model to large-scale test with 100 operations per job. Results are gathered in Table I
We highlight the following findings:
Comparison with baseline solvers w/o decomposition. L-RHO outperforms both traditional solvers (CP-SAT, GA) and the learning-based DRL solver in the standard (offline) FJSP setting. Specifically. (1) L-RHO achieves the best objective, outperforming DRL and all heuristic baselines in both in-domain and zero-shot generalization to larger scales; (2) We find the performance of and DRL-Ho poor; (3) Comparing with DRL-20K (Wang et al. (023a). we see that DRL Greedy is the fastest method but has worse performance than Default RHO. (4) DRI.

---

Published as a conference paper at ICLR 2025
Table 1: Offline FJSP under Makespan Objective. Each column corresponds to a different FJSP size given by the format: total number of operations, followed by a tuple of (number of machines |M jobs [T], and operations per job n)) L-RHO outperforms all types of baselines.
(10,
800 (10,
1200
60)
2000 20, 100), Transfer
Time (s) 1
Makespan 4
Time (s)
Makespann
Time (s) 1
Makespan.
Time (s)
Makespun
CP-SAT (10 hoars)
36000
1583
65
36000
2128 1. 75
35000
3206
36000
1882] 1986
CP-SAT
1800
2274 1: 147
1800
4017 1.413
1800
10925
1013
1800
39585 1 2707
GA
1800
3659
87
1800
5150 + 92
1800
8086
111
1800
10405 + 640
ARD-LNS (Time-bared)
300
2100
209
400
3298
365
600
5115
558
1000
14258 1522
ARD-LNS (Machine-bused)
3974
1227
12764 4206
52225 1793
Orade-INS (Time-based)
300
1789
101
400
2663
120
600
4470
1000
7275 1. 785
DRI.-cchrverri, Greedy
84 27
2347 189
115 32
5105
161
105
4570 218
213 1D
7673 556
Echeveer,,,,,a, Sampling
157 8
2351
139
217 + 11
3131
165
427 = 20
4657 + 192
603 #:41
77774 271
DRL-Ho, Greedy
4:2
3030
69
40.3 1: 87
6045
22 4:3
10344 1: 115
Sampling
168 14
56
385
5870
517
9815
DRL. Greedy
1. 0.02
1628 72
0.04
2128 1: 80
10
3141
16. 0.2
5184
-RI, Sample 100
29 + 0.3
1551
=: 60
47 1
2048 + 69
110 +:
3063 81
302 + 10
S082 + 98
2RI, Sample 500
146 +
1537
61
261 8
2031 + 68
597 16
3045
1738 +
5062 + 98
Default RHO (Long)
599 1: 55
L529 58
728 1. 98
2044 4 75
1099 108
3002
2671 244
4994 114
Default
244 21
73
318 1.26
78
545 36
3136
Warm Start RHO
203 1: 23
1521 67
278 2:22
2055 75
420 33
3081
716
5057 106
L-RHO
126 1: 19
1613 70
160 1 23
2015 1: 86
259 37
3011 1 106
5. 52
4982 132
Sampling improves its performance but significantly increases computational time, with DRL-20K (500 Samples) taking longer and performing worse than L-RHO. Additionally, the solve time of DRL heavily rely on batch-decoding and GPU availability, whereas our L-RHO has competitive inference time even solely running on CPUs. (5) L-RHO requires significantly fewer training in- stances than DRL-20K, making it advantageous when obtaining FJSP instances is costly.
Comparison with baseline solvers w/ decomposition. We first observe that, (1) for ARD- LNS, based decomposition outperforms the machine-based variant but still results in a worse makespan and longer solve time compared to Default RHO, This suggests that effective temporal de- composition is crucial for time-structured, long-horizon COPs. In contrast, (2) L-RHO significantly outperforms both LNS methods in terms of solving time and objective. Furthermore, (3) while Oracle-LNS improves performance by simulating learning-bas based decomposition, it still underper- forms compared to Default RHO. This suggests that RHO is better suited for long-horizon FJSP, partly due complex temporal dependencies as follows: LNS begins with complete solution and refines it iteratively. However, the makespan objective only improves when the last operation on the critical path included. This temporal delay propagating local improvements contrasts with prior sorring-bbsed LNS methods for Mixed Integer Programming (Huang et al. 2023) or Vehicle Routing (Li al. 202T), where subproblem improvements directly impact the objective. In contrast, RHO builds the solution progressively, maintaining tighter makespan by following the natural tem- poral order of operations. Lastly, we note that L-RHO's temporal decomposition is orthogonal to other strategies and could be combined in future work to enhance scalability and flexibility.
Discussion RHO for online settings. Unlike offline baselines (CP-SAT, GA, ARD, DRL. that require complete information, RHO constructs solutions progressively using only near-future infor- mation, making it suitable for online settings. Next, we explore FISP variants, including observation noise and machine breakdowns, to evaluate the applicability of L- to batch-online FJSP.
5.2 DETAILED COMPARISON WITH RHO BASELINES UNDER DIFFERENT FJSP VARIANTS
We now benchmark L-RHO against diverse RHO baselines across FISP variants. We evaluate ob- jectives such as makespan, start delay, and end delay, while also testing its adaptability under higher system congestion, observation noise, and machine breakdowns to simulate real-world dynamics.
We include two more RHO baselines, following the R.HO procedure but obtaining the fixed op- crations Ofizr with the following heuristics: (a) Random OR E [0, 1]: O fiz.r is obtained by select- ing each operation in O Ovvrrlap.r with probability da uniformly at random, (b) First OF j0, 1]: O yiu, is obtained as the first oF fraction of operations in Ovvertap.r with the earliest RHO sequence order based on the precedence order (for makespan) release time (for delay- based objectives).
New Objective: Start Delay. In Table 2 under the new start delay objective, our L-RHO consis- tently outperforms all RHO variants in both solve time and objective across time horizons. Notably,
7

---

Published as a conference paper at ICLR 2025
Table Detailed Comparison of L-RHO with RHO variants under Start Time Delay Objective. We present the time and objective improvements (TI%, 01%) of RHO variants relative to Default RHO. The best TI% and 01% are bolded. L-RHO significantly outperforms all baseline RHO variants.
600 (25, 25, 24)
1050 (35, 35, 30)
1600 (10, 40, 40)
TI %
O1 %1
TI %1
%1
%
OI %
Defunl RHO
(0.0% 0.0%)
946.9% +: 31,6s
1790.5 145.3
0.05)
1119.88 + 35.5%
(.0%)
2960.4 215.7
0.0%)
2349 3s 111.7s
0.05%)
(0.0% 0.1%)
1148.6.2 :: 356.8
Warm Start RHO
38.6% +: 1.0%
-7.5%
2.8%
-12.9% 1.6%
11.2% +: 2.7%
5.2% 2.4%
6.8% 4.8%%
First 20%
26.15% +: 1.3%
2.9% 1: 2.5%
10.2% = 1.7%
-30.5% 1: 10.7%
31.0% 1: 2.49
-91.15 4: 24.3%
First 30%
33.6% 1: 1.3%
-7.0%
2.5%
13.2% = 1.7%
-48.9%
7.2%
31.7% d: 2.1%
-129.4%
19.1%
First 40%
34.8% 1.3%
-32.3%
+: 3.7%
14.1% = 2.1%
-100.45
8.7%
34.7% 3.0%
-274.7%
198
Random
-11.9%
-15.5% 1.7%
-12.9%
3,0%
-55.2%
9.6%
Random 20%
23.8% 1: 1.7%
-27.6%
4: 3.4%
-2.0% 1: 2.6%
-86.1%
7.9%
10.2% 5.5%
-115.6%
14.5%
L-RIOO (Ours)
53.0% +: 1.0%
16.0% à: 1.9%
35.1% = 1.3%
21.0% A: 2.4%
47.3% d: 2.2%
13.1% +: 4.4%
Detoult Random 20%
Rancom 30%
Rist 20%
Rist 40%
Warm Start
Rancom 40%
First 30%
50%
LRHO
4000
6000
4000
3750
high
3500
15000
3500
Objertoo
8000
1000
(11)
OHeccivve
3250
3000
high
obs. noisee
2500
111]
22700
mid
3000
00)
mid
2000
2500
2250
400
30
1000
3400
1500
400
start delay
600
2000
Time
(s)
Solve
Figure 3: L-RHO under different FISP variants. Left: Increased Congestion level with more jobs [T] {30, 32, 34}. We circle the baselines for these three settings with green, yellow and red ellipsoids, using different markers represent each setting. L-RHO is plotted in pink. Middle: Multi-objective and Noisy Observation (online). We analyze FJSP (30, 30, 24) with the (i) start delay objective (ii) start and end delay objective, and (iii) start and end delay objective plus observa- tion noise. The arrows illustrate the performance changes of each method across (i)-(ii)(iii), Right: Machine Breakdown (online). We simulate machine breakdowns during RHO's process, varying intensity (low, mid, high) by adjusting event frequency and machine availability.
it achieves a 35% 53% speed up from Default RHO with a further 13%-21% % improvement in the objective (total start delay), demonstrating the effectiveness of our learning method in accelerating RHO. Comparing with the baseline methods, we observe that: (1) Warm Start RHO does not sig- nificantly outperform Default RHO, indicating the inadequacy of simple warm start techniques for the complex long-horizer FISP. (2) The assignment- based subproblem restriction heuristics, namely First and Random, improve the solve time from Default RHO, albeit at the expense of poorer objec- tive. Moreover, First o emerges more effective heuristic than Random on, with a better solve time and objective improvement when O fizzr is of a comparable size (oF OR).
Data Distribution: Higher Congestion. We raise the congestion level by increasing the number of jobs [T] E {30, 32, 34} while keeping the number of machines |M| = 30 and operations per machine to be 25 under the start delay objective. This results in higher job-to-machine ratio, with congestion build-up over time. In Fig. 3 (left), we observe that L-RHO achieves solve time and objective improvements TI% (41%. 39% 28%} and 01% E {14% 20%. 27%) across the different settings, demonstrating the robustness of the learning method to system congestion. In contrast, the baselines (First and Random) have limited solve time improvement and substantial objective degradation for all settings. This highlights L-RHO's ability to enhance system throughput by enabling the system to process more jobs than Default and baseline RHO methods.
Multi-Objectivee Start and End Delay. While the total start delay objective emphasizes adhering to the release time, reducing the total end delay is crucial in many real world scenarios where fol- lowing each operation's 's scheduled due time is important. Here, we use the sum of the start and end delay as the objective and generate random target end time for each operation (see Appendix(A.5..] In Fig. 3 middle (ii), we observe that L-RHO maintains solve time and objective improvements
8

---

Published as a conference paper at ICLR 2025
with TI% of 39% and 01% of 4% under this combined objective. Interestingly, Random and First also improve relative to Default RHO (better TI% and O1%, see Random 30%, for example). Em- pirically, find more overlapping operations maintain the same assignment under this distribution, our analysis in Sec. 6 indicates the advantageous for Random and First under such a scenario.
Online FJSP: Observation Noise. In real-world FISP deployments, practitioners often face in- complete and noisy operation data. To simulate this, we introduce observation noise into the RHO process, moving towards a more realistic online FISP. Specifically, we assume that in each RHO subproblem, only the durations of operations with earlier release times are accurately observed. For other operations. we only have access noisy estimates, and RHO optimizes subproblems based on this noisy information. Thus, the observed durations in P, may differ from the true execution duration during execution (see Appendix [A.5.] for details). In Fig. [ middle (iii), the Random and First strategies degrade significantly under observation noise, with a more pronounced effect on First. Our analysis in Sec. clattuess such behavior for First and Random, as the observation noise leads to (I) more overlapping operations changing assignments (2) less informative distribution to determine which operation in the subproblem will change assignments. In contrast, L-RHO remains effective under observation noise, with a TI% of 25% and 01% of 4% over Default RHO.
Online FJSP: Machine Breakdown. In real-world FJSP scenarios, unexpected disruptions such as machine breakdowns can occur (Zhang and Wong 2017). We simulate breakdowns, and com- bine the periodic RHO optimization with baent-based rescheduling: when breakdown or recovery occurs, we re-optimize the RHO subproblem with updated machine availability. This leads to two major changes in the RHO pipeline (1) RHO subproblems are solved more frequently due to the breakdown (or recovery) events, and (2) operations with all compatible machines down are deferred until the breakdown ends, thereby resulting in longer scheduling horizon (see Appendix [A.5.] for details). In Fig. B (Right), we test L-RHO under varying machine breakdown intensities by adjusting breakdown frequency and the proportion of downed machines, using makespan as the objective with 10 machines, 20 jobs, and 800 operations. Our L-RHO demonstrates significant time improvements TI% E (47%. 52%, 37%} over Default RHO across all intensity levels, while also achieving a better makespan. This highlights L-RHO's reliability under unexpected disruptions. We also observe that, at high breakdown intensity, First loses its advantageous to Random. This can be similarly explained in our analysis next, unexpected disruptions reduce the amount of information First can leverage.
6 THEORETICAL PROBABILISTIC ANALYSIS
In this section, we present a theoretical probabilistic analysis to identify when RHO can benefit from machine learning. Intuitively speaking, the more irregular the operations to be fixed (O the more advantageous L-RHO can be, because of the greater potential gain from prediction. Also, L-RHO must balance both False Positive (FP) and False Negative (FN) errors: fixing something that should not have been (FP) harms the objective but helps the solve time, while failing fix something that should have been (FN) harms the solve time and also indirectly harms the objective (under fixed time limit). Thus, an ideal L-RHO method will balance the two errors (see Fig.
Notation.
We analyze generic subproblem P. == 1 at each iteration r, and drop the r subscript for ease of notation. We consider fixed set of RHO parameters and denote W = H S S= @overtapl- Given ftu and Of from the Oracle and a method in {Random dR. First Fr, L-RHO], we denote E[n Az = F[ fizll: Il. Ofn = Oj.,. für \Ofix and Opp = O fix A.ji...- We define the FN and FP errors B|nyn] = [I r.l] and E[ = []]Opp]] The (expected) FP and FN rates of each method are E E'n",.ell (,))), with L-RHO's FPR and FNR denoted as (a,
We leverage an intuitive linear decay assumption, validated in Appendix A.7.2 in a given FISP subproblem, the later an operation appears in the RHO sequence, the less likely its assignment should be fixed. This assumption allows us to formally relate the FP and FN errors of different methods (L-RHO versus Random versus First, see Prop. and Fig. rig. (middle)).
Assumption (Linear Decay). Let the probability that each operation O(0) Ovverlap is included in Oju be denoted as P)an (1) E [0, 1). where the index i E (1,.., W} follows the RHO sequence order. We consider linearly decreasing Pfr b- w. where constants 0 $ b, S 1 reflect average behavior across RHO iterations. We have Ennnian) = Expr (1) (b W)

---

Published as a conference paper at ICLR 2025
= H 5
FN Rate
O Overiap
Oren
=
0
0.15 0.29
0.44
0.59 0.73 0.86
Oracle
25
Random &
First, 0
20
First
400%
Random
0.26
FP errrr Efree
20
Pirst m 0.7
FP error ((Ng)
6 8
Better
0.29
Oyz
method
15
First m 1.0
40%
Time Obj
20%
0.22 2
10
0.14
Time
Obj.
(Relative Orecie)
FN
FP
I Time (low Plye)
Obj.
L-RHO
0.07
Time (high myy)
20
20
FN error elBe]]
FN error L[Rm]]
We analyze FN and FP errors of each RHO method relative Oracle and interpret their impact on objective and solve time. Middle: We show the FN and FP errors for Random and First with R, OF [0, 1] under Assump. [ fixing
Figure 4: Left:
m 0.5 while increasing the slope m. Higher m enhances the performance of First relative to Random (with equal σ) by reducing both errors. We plot σR. oF E {0.0.1, 0.1,0.1............... 1} using circles and squares, with darker colors for smaller values. Right: For FJSP (25. 25, 24) with the total start delay objective, we depict the FN and FP errors of [Random, First, and L-RHOO in the low FP region, using an empirically validated p)a.. (i) distribution. By reducing both [r and yo], L-RHO empirically outperforms First op S. 60% in solve time and all baselines in objective (pink region). Transforming the coordinates (right and top axes) can further reveal the FP and FN rates L-RHO should achieve for learning to be effective.
Proposition 1. Under Assump. the FN and FP errors for each method is given in closed-form as
Random: Random) = (1 rz) n jsel ). Rln Random) = n W Exn) fn
fp
* First: B[niin = (1-or) Am
2 W). Em fi oF (W -[[ aW Emi
o))-)))W);
L-RHO: E J LnLO- BTT (zz)) Bl Em L
Furthermore, ignoring the 2 term in E(n for ease of exposition, the FP and FN Rates of First oF and Random on are (a (F) ( " gorl or ov) and (aen, 3R) = (a 1 nn).
b-
Interpretation. The Pizz (i) distribution determines the strength of the Random and First baselines and thus the potential for improvement by learning methods. (1) When E(n is close 0 1, Random achieves low FP and FN errors by setting OR close E[ (2) Our analysis captures the empirical observation that First often outperforms Random: with strong linear decay (a large slope m), First further reduces the FP and FN errors from Random for each or = dR- (3) L-RHO is advantageous when its FP and FN rates (a, (8) is lower than those for First and Random, as given in the Prop. This can provide practitioners a valuable way to assess the effectiveness of the learned model prior deployment. We refer to Appendix A.7 for detailed proofs and interpretation.
CONCLUSION
We contribute the first soarning-guieed rolling coolion method for COPs, which we call L-RHO. By learning which overlapping solutions in consecutive RHO iterations do not need to be re-optimized, method substantially reduces RHO subproblem sizes and thus accelerates their solve time. L- RHO scales and accelerates RHO by up to 54%, improves solution quality, and outperforms a wide range of baselines. both with and without decomposition. We also analyze L-RHO's performance across various FJSP settings, distributions, and online scenarios, highlighting its flexibility and adaptability. We further provide a probability analysis to identify conditions where learning-guide RHO is most beneficial. One limitation is that L-RHO alone may not achieve state-of-the-art perfor- mance when extended to other long-horizon COPs. Future work could extend L-RHO to 1) other long-horizon COPs, e.g., multi-item inventory management and vehicle routing with time windows, 2) training on diverse distributions for better generalization, 3) integration with other decomposition or subproblem restriction methods, and 4) addressing more complex real-world online scenarios. Our theoretical analysis may also guide the development of more effective RHO warm-start tech- niques with applications control and robotics, e.g., accelerating Hybrid MPCs. We believe L-RHO offers a valuable tool for long-houd monghhorzoon COP' and will inspire future work in various domains. Our com/mi mi t-ww-- laap-lab//.. ab/ rho
code is publicly available at ptttttss//ggiiii
10

---

Published as a conference paper at ICLR 2025
8 ACKNOWLEDGEMENT
The authors would like to thank Sean Lo for insightful discussions. This work was supported by the National Science Foundation (NSF) CAREER award (#2239566), MIT's Research Support Commit- tee, Amazon Robotics Ph.D. Fellowship, and gift from Mathworks. The authors acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing HPC resources that have contributed to the research results reported within this paper.
REFERENCES
Bernardetta Addis, Giuliana Carello, Andrea Grosso, and Elena Tanfani. Operating room scheduling and rescheduling: rolling horizon approach. Flexible Services and Manufacturing Journal, 28 (1):206-232, 2016.
Jose L Andradee-Pneed Pineda, David Canca, Pedro L. Gonzalez-R, and Marcos Calle. Scheduling a dual- resource flexible job shop with makespan and due date-related criteria. Annals of operations research, 291:5-35, 2020.
Dennis Behnke and Martin Josef Geiger. Test instances for the flexible job shop scheduling problem with work centers. 2012.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: methodological tour d' d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Dimitris Bertsimas and Bartolomeo Stellato. Online mixed-integer optimization in milliseconds. INFORMS Journal on Computing, 34(4):2229-2248, 2022.
Aldo Bischi, Leonardo Taccari, Emanuele Martelli, Edoardo Amaldi, Giampaolo Manzolini, Paolo Silva, Stefano Campanari, and Ennio Macchi. A rolling-horizon optimization algorithm for the long term operational scheduling of cogeneration systems. Energy, 184:73-90, 2019.
Paolo Brandimarte. Routing and scheduling in a flexible job shop by tabu search. Annals of Opera- tions research, 41(3):157-183, 1993.
Nicola Castaman, Enrico Pagello, Emanuele Menegatti, and Alberto Pretto. Receding horizon task and motion planning in changing environments. Robotics and Autonomous Systems, 145:103863,
2021.
Abhishek Cauligi, Preston Culbertson, Edward Schmerling, Mac Schwager, Bartolomeo Stellato, and Marco Pavone. Coco: Online mixed-integer control via supervised learning. IEEE Robotics and Automation Letters. 7(2):1447-1454, 2021.
Stéphane Dauzère-Pése Pérès and Jan Paulli. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research, 70(0):281-306, 1997.
Stéphane Dauzère-Pénn Pérès, Junwen Ding, Liji Shen, and Karim Tamssaouet. The flexible job shop scheduling problem: A review. European Journal of Operational Research, 2023.
Dingzhu Du and Panos M Pardalos. Handbook of combinatorial optimization, volume 4. Springer Science & Business Media, 1998.
Imanol Echeverria, Maialen Murua, and Roberto Santana. Solving large flexible job shop scheduling instances by generating diverse set of scheduling policies with deep reinforcement learning. arXiv preprint 10Xiv:2310.15777 2023.
Mohammad Fattahi and Kannan Govindan. Data-driven rolling horizon approach for dynamic de- sign supply chain distribution networks under disruption and demand uncertainty. Decision Sciences, 53(1):150-11) 2022.
11

---

Published as a conference paper at ICLR 2025
Giuseppe Franze and Walter Lucia. A receding horizon control strategy for autonomous vehicles in dynamic environments. IEEE Transactions on Control Systems Technology, 24(2):695-702, 2015.
Carlos E Garcia, David M Prett, and Manfred Morari. Model predictive control: Theory and prac- tice-a survey. Automatica, 25(3):335-3455 1989.
Lukas Glomb, Frauke Liers, and Florian Rösel. A rolling-hone horizon approach for multi-period opti- mization. European Journal of Operational Research, 300(1):189-000
2022. 2022.
Google. Or-tools ep-sat solver, 2023. URL BRLL_attass//deeeeorrssccoo
/atiioncp//p__at ppl_//er____e
Keld Helsgaun. An extension of the lin-kernighan-helseen tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966 990666980,,00 2017.
Pascal Van Hentenryck and Russell Bent. Online stochastic combinatorial optimization. The MIT Press, 2006.
Pedro Hespanhol, Rien Quirynen, and Stefano Di Cairano. A structure exploiting branch-and- algorithm for mixed-integer model predictive control. In 2019 18th European Control Conference (ECC), pages 2763-2768. IEEE, 2019.
Kuo-Hao Ho, Ruei Yu Jheng, Ji-Han Wu, Fan Chiang, Yen-Chi Chen, Yuan-Y Wu, and I-Chen Wu. Residual scheduling: A new reinforcement learning approach to solving job shop scheduling problem, 2023. URL htt https::p:////c.t /ttp::///pppeeeiiiiiee
net / forum? idd dadddsuuIlEhhhhhh
Taoan Huang, Jiaoyang Li, Sven Koenig, and Bistra Dilkina. Anytime multi-agent path finding via machine learning- guided large neighborhood search. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 9368 037889936,2220 2022.
Taoan Huang, Aaron Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In International Conference on Machine Learning, pages 18869-13890 PMLR, 2023.
Johann Hurink, Bernd Jurisch, and Monika Thole. Tabu search for the job-shop scheduling problem 15:205-215, 1994.
with multi-purpose machines. Opprratioss-Reeeerc--SSpepe
Youngseo Kim, Danushka Edirimanna, Michael Wilbur, Philip Pugliese, Aron Laszka, Abhishek Dubey, and Samitha Samaranayake. Rolling horizon based temporal decomposition for the offline pickup and delivery problem with time windows. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 5151-5159, 2023.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint TrXXiv:1003.080 08475, 2018
Abdel Ghani Labassi, Didier Chételat, and Andrea Lodi. Learning compare nodes in branch and bound with graph neural networks. arXiv preprint wrXiv:2210.169/2 2022.
Sangbok Lee and Yuehwern Yih. Reducing patient-flow delays in surgical suites through determin- ing start-times of surgical cases. European Journal of Operational Research, 232(2):62 2014.
Kun Lei, Peng Guo, Yi Wang, Jian Zhang, Xiangyin Meng, and Linmao Qian. Large-scale dynamic scheduling for flexible job-shop with random arrivals of new jobs by hierarchical reinforcement learning. IEEE Transactions on Industrial Informatics, 20(1): 20(1):1007-101 2023.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. Ad- vances in Neural Information Processing Systems, 34:26198-2621 2021.
Sirui Li, Wenbin Ouyang, Max Paulus, and Cathy Wu. Learning configure separators in branch- and-cut. Advances in Newral Information Processing Systems, 36, 2024.
Xinyu Li and Liang Gao. An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. International Journal of Production Economics, 174:93-110 10, 2016.
12

---

Published as a conference paper at ICLR 2025
Qiong Liu, Mengmeng Zhan, Freddy O Chekem, Xinyu Shao, Baosheng Ying, and John W Suther- land. A hybrid fruit fly algorithm for solving flexible job-shop scheduling to reduce manufacturing carbon footprint. Journal of Cleaner Production, 168:668 668,, 2017.
Gongyuan Lu, Jia Ning, Xiaobo Liu, and Yu Marco Nie. Train platforming and rescheduling with flexible interlocking mechanisms: An aggregate approach. Transportation Research Part E: Lo- gisties and Transportation Review, 159:102622, 2022.
Fu Luo, Xi Lin, Zhenkun Wang, Tong Xialiang. Mingxuan Yuan, and Qingfu Zhang. Self-improved learning for scalable neural combinatorial optimization. arXiv preprint arXiv:2403.19561, 2024,
Shu Luo, Linxuan Zhang, and Yushun Fan. Real-time scheduling for dynamic partial-no-wai mul- tiobjective flexible job shop by deep reinforcement learning. IEEE Transactions on Automation Science and Engineering, 99(4):3020-3033) 2021.
Yining Ma, Zhiguang Cao, and Yeow Meng Chee. Learning to search feasible and infeasible re- gions of routing problems with flexible neural k-opt. Advances Neural Information Processing Systems, 36, 2024.
Tobia Mareucei and Russ Tedrake. Warm start of mixed-integer programs for model predictive control of hybrid systems. IEEE Transactions on Automatic Control, 66(6):2433-2448, 2020.
Jacob Mattingley, Yang Wang, and Stephen Boyd. Receding horizon control. IEEE Control Systems Magazine, 31(3):52-65, 2011.
Dario Pacino and Pascal Van Hentenryck. Large neighborhood search and adaptive randomized decompositions for flexible jobshop scheduling, In Proceedings of the International Joint Con- ference on Artificial Intelligence. AAAI Press, 2011.
Laurent Perron and Frédéric Didier. Cp-sat. URL httpss//ddveelpprrsccoo.ee.... t wwnizaatiio//ppppppolleeee
Dinh-Nguyen Pham and Andreas Klinkert. Surgical case scheduling generalized job shop scheduling problem. European Journal of Operational Research, 181(3):0011-1025, 2008.
David Pisinger and Stefan Ropke. Large neighborhood search. Handbook of metaheuristics, pages 99-127, 2019.
David Pisinger and Mikkel Sigurd. Using decomposition techniques and constraint programming for solving the two-dimensional bin-packing problem. INFORMS Journal on Computing, 19(1); 36-51, 2007.
Lara Scavuzzo, Feng Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning branch with tree mdps. Advances in Neural Information Processing Systems,
2022.
Alexander Schrijver al. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003.
Suresh Sethi and Gerhard Sorger. A theory of rolling horizon decision making, Annals of operations research, 29(1):387-415, 1991.
Wen Song, Xinyang Chen, Qiqiang Li, and Zhiguang Cao. Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Transactions Industrial Informatics, 19(2):100-1160,, 2022.
Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neigh- borhood. Computers Operations Research, 140: 145640,, 2022.
Runqing Wang, Gang Wang, Jian Sun, Fang Deng, and Jie Chen. Flexible job shop scheduling via dual attention network-based reinforcement learning. JEEE Transactions on Neural Networks and Learning Systems, 2023a.
13

---

Published as a conference paper at ICLR 2025
Runzhong Wang. Yunhao Zhang. Ziao Guo, Tianyi Chen, Xiaokang Yang, and Junchi Yan. Lin- satnet: the positive linear satisfiability neural networks. In International Conference on Machine Learning. pages (66605366623 PMLR, 2023b.
Zhenkun Wang, Hui-Ling Zhen, Jingda Deng, Qingfu Zhang, Xijun Li, Mingxuan Yuan, and Jia Zeng. Multiobjective aptimization-aider decision- system for large-scale manufacturing planning. IEEE Transactions on Cybernetics, 52(8):8326-8339 2021.
Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yuan, Jia Zeng, Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integel linear programming via hierarchical sequence model. arXiv preprint 2rXiv:2302.00244, 2023c.
Shirantha Welikala and Christos G Cassandras. Event-driven receding horizon control for distributed persistent monitoring in network systems. Automatica, 127:109513 2021.
Jin Xie, Liang Gao, Kunkun Peng. Xinyu Li, and Haoran Li. Review on flexible job shop scheduling. IET collaborative intelligent manafacturing, 133:67777, 2019.
Hegen Xiong, Shuangyuan Shi, Danni Ren, and Jinjin Hu. A survey of job shop scheduling problem: The types and models. Computers & Operations Research, 142: 105731, 2022.
Shengxiang Yang, Yong Jiang, and Trung Thanh Nguyen. Metaheuristics for dynamic combinatorial optimization problems. IMA Journal of Management Mathematics, (4(4):451-480) 2013.
Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, and Yong Li. Deepaco: Neural-enhanced ant systems for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024a.
Haoran Ye, Jiarui Wang, Helan Liang, Zhiguang Cao, Yong Li, and Fanzhang Li. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20284-20292 2024b.
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. Advances in neural information processing systems, 33:1621-18 162--62,, 2020.
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, 2024a. URL nattpa://openreviiee net.
for weaet//formmmie woodmmmmijjaa
W.CmrsHHs
Cong Zhang, Zhiguang Cao, Yaoxin Wu, Wen Song, and Jing Sun. Learning topological represen- tations with bidirectional graph attention network for solving job shop scheduling problem. The Conference on Uncertainty in Artificial Intelligence (UAI), 2024b.
Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in Neural Information Processing Systems, 36, 2024c.
Qiao Zhang, Hervé Manier, and M-A Manier. A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times. Computers & Operations Research, 3917)11133-1723, 2012.
Sicheng Zhang and Tak Nam Wong. Flexible job-shop schedulingrescheeuling dynamic en- vironment: a hybrid mas/aco approach. International Journal of Production Research, 55(11): 3173-3196, 2017.
Hong Zhou, Waiman Cheung, and Lawrence C Leung. Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. European Journal of Operational Research, 194(3): 637-649, 2009.
Zefang Zong, Hansen Wang. Jingwei Wang, Meng Zheng, and Yong Li. Rbg: Hierarchically solving large-scale routing problems in logistic systems via reinforcement learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4648-4658, 2022.
14

---

Published as a conference paper at ICLR 2025
A
SUPPLEMENTARY MATERIAL:
Rolling Horizon
Optimization for Long- Hong-Horizon Flexible Job- Lob-Shop Scheduling
CONTENTS
A.1
Notations
16
A.2
Algorithm: Learning- Guinded Rolling Horizon Optimization
18
A.3
Input Features,
19
A.4
Architecture, train and evaluation setup,
23
A.5
Experimental Details
24
A.5.1
FJSP Instance Distribution, Machine Breakdown and Observation Noise.
24
A,5.2
FJSP Formulation
27
A.5.3
Baseline Details
30
A.5.4
Rolling Horizon Parameter Search
32
A.5.5
Performance of RHO methods for FJSP (30, 30, 24).
33
A.5.6
Performance RHO methods under the same RHO parameter,
33
A.6
Additional Experimental Results
35
A.6.1
Performance on Real World Dataset (Dauzère- Pérés and Paulli 1997)
35
A.6.2
Accuracy, TPR, TNR, Precision, and Recall of the Learning Method,
35
A.6.3
Ablation Study: Detailed Comparison with Attention Based Architecture,
35
A.6.4
Performance Comparison with DRL under the same number of FJSP train-
ing instance.
38
A.6.5
Performance of Default RHO with Longer Time Limits
38
Detailed Theoretical Probabilistic Analysis
39
A.7.I
Details of all considered RHO methods
39
A.7.2
Empirical validation of the linear decay assumption for p7
40
A.7.3
Derivations of E / and
n /n. for each method
40
A.7.4
Qualitative Relationship between (E fp and and (objective, solve
time)
A.7.5
Detailed Derivation of Table 20
44
A.7.6
Interpretation of Prop.
45
15

---

Published as a conference paper at ICLR 2025
A.1 NOTATIONS
We provide detailed lists of notations for the Flexible Job-shop Scheduling Problem (FISP) and Rolling Horizon Optimization (RHO) in Table Table
Table Notations for the Flexible Job-shop Scheduling Problem (FISP).
FJSP Related
M T
A set of machines. The machines indexed by ...
A set of job. The jobs indexed by T.
Problem P
A set of operations. The operations indexed by 03.t O. Each job E consists
of ny operations {0,, E SO. 18y
required processed predefined precedence order
0,1 02,2
Oy,,,.
After sorting the operations by their respective release time (see below), each operation (10) O {O(") .... 0110) } indexed by
Compatible Machines Miak
Each operation 3 can processed on any machine among suhset M,,s S M compatible machines.
Process Duration F
P5, denotes the process duration operation O₁,² on machine m MyA-
Under delay-based objectives, each operation O,.e has a release time sjkk, which respects the precedence orders of operations within the same joh: operations 2 and Oj with Vkk < lz, we assume 5 S 83. Each operation can only processed after release time.
Release Time $y.8 (Target Start Time)
Under the
delay objective, each operation O5,s a is associated with a target end time f,A. which represents a target time to finish operation and similarly respects the operation precedence orders.
Target End Time fys
Ordering the operations
{0,,>); used to divide the full operation O into overlapping RHO subproblems. ordered by
For the makespon objective, the operations their relative position in the jobs based on the precedence order: For job j with n, operations in precedence order (),1
Operations' Ordering {O()) O0))
O).ny
give operation O3. score of k/ny. and choose each RHO subproblem as the first H non executed operations with the lowest score.
For delay-based objectives, the operations are ordered hy
their release time g(1) S
g(10))
-M represents the machine assignment of each operation,
Assignment m
with m0OO,)) E M, for all
Solution II = =(m,r)
Schedule (Process Start Time)
x: [O Vj. N. where the process start time
of each operation O5.s satisfies m(O,a) 8/A-
The process end time of operation Oz.: is m,(O,.))
Process End Time ne
mm(0,.) is the process duration. m(Os,a) where P5,A ((O,,) + P2,k
Makespan
max (O(,,)), see Alg. 0
Objective
Total Start Delay
Σ T0OAa) SJA. Alg. 7
O
Total Start and End Delay
Σ (0,aa) - 88.A + max(m;(O,.) - ty.4, 0), see Alg.
O,
16

---

Published as a conference paper at ICLR 2025
Table 4: Notations for the Rolling Horizon Optimization (RHO).
RHO Related: RHO Iteration
planning window size (H operations current planning window).
8
An execution step size (S If operations executed each iteration).
Parameters
T
A solve time limit of T seconds per RHO subproblem.
We early terminate solver if the value the best feasible solution does not improve within Tea seconds, (see Appendix. |A.5.4
Tes
FISP subproblem P. given by subset of operations O with additional constraints to ensure Opton, are processed after the previously exccuted operations within the same job same machine (see Appendix A.5.2 Alg
Unrestricted P.
FJSP Optim. Subproblem
Given a subset fix,r. we can construct a simpler, restricted FISP subproblem P. from P. by setting the compatible machines My.a- {m,, [0,,, Og,x O
Restricted P.
Operations included in the current RHO subproblem P, or P,: The first non-executed operations with carliest RHO sequence order.
Opiani
See Appendix Sec. A.2 Alg.
Executed operations based on the solution of P. Pr: The first operations with the earliest process start time Carlicst (pperations(Tt.(( (O) Opten.r)). See Alg
Oategie
Relevant Operations
Overlapping operations in consecutive RHO iterations 1 and O anerlapur plen, I' plan.r-1
Ooverlager
Subset
New operations iteration but not in 1:
Onew,r
Onew Opton.o 1ptan.r-1
The (look-ahead Oracle) subset of operations in O Doverlay. with the same machine assignment RHO subprohlems P. and P. P.-
consecutive unrestricted
O+ Ney = {0 E Onverdap.r m,( (0)}
That is, given the solution to the previous subproblem P,-1.
lookahead by solving current subproblem P. and identify operations with the same machine assignments.
The fixed operations subset given by specific method. Given
Opa
Oue C Oovertag.rs we can construct P. from P, by setting the compatible machines M = (M, (O)aa) for operations О₃д Ofee
Subproblem Assignment m,
My Opton.r M represents the machine assignment each operation in the subproblem, with m00),)) C My, for all O₁, O Opann.r
Subproblem Solution
(m. m.)
Subproblem Schedule
u, Opien,r + N. where the (solution) start time each operation the subproblem O,,a Opton. x(O,a) ) 83.-
Each RHO iteration solves
Default (Cold Sturt)
unrestricted FJSP subproblems P, from scratch (cold start, Oxr, E O).
Each RHO iteration solves a restricted FISP subproblem P. associated with the fixed operation set O fuz,, constructed by sampling each operation O aeeelopur with probubility zn uniformly random.
Random or
Each RHO iteration solves a restricted FJSP subproblem P. associated with the fixed operation set Over obtained as the first oF fraction of operations in Overtoppr with the earliest RHO sequence order (determined by operation precedence for makespan based ohjectives).
First dr
Methods
release time for delay-based
At each RHO iteration, we apply CP-SAT's internal warm-start techniques to solve unrestricted FJSP subproblems P.. Specifically, provide the machine assignments of the overlapping operations in the previous iteration (m) A O e O Omvertap. } as hints to the solver.
Warm Start
See: /ndees///eeelopsrrs wtw.://ssooooocoooooooooiiiiiiia pythom/san /st///////ppy////y/yy thon//ppppppppo maddeeeadddiiii"
com/opptiiiizatiie/eeeeeeee
Follow our data collection pipeline (Fig. T b) top. omit the solve time for the unrestricted P.), where each RHO iteration solves a restricted FJSP
Oracle
suhproblem P, associated with the omacce fixed operation set O ;
Follow inference procedure RHOO in Fig. bottom, where each RHO iteration solves restricted FISP subprohlem P; associated with the fixed operation set O frrrr predicted by learning model
L-RHO (Ours)
17

---

Published as a conference paper at ICLR 2025
A.2 ALGORITHM: LEARNING-GUIDED ROLLING HORIZON OPTIMIZATION
The inference procedure for the learning gugdded rolling horizon algorithm (Fig. ! is provided as follows, where each RHO iteration, we use neural network Sa to identify set of fixed oper- restricted subproblem P. (Line
ation faa. (Line 10), resulting in the machine assignment- 15). We note that the heuristic RHO baselines considered in Sec. and (c.g. First oF and Random RR) we follow the same algorithm but use the associated heuristics to find the set O Ozz,, instead (Line 10).
Algorithm 1: Learning Guided Rolling Horizon Optimization for FISP
Input: FJSP problem instance P = (M, O, (piihh J. {s (G,,)), RHO planning window size operations, execution step size S operations, and solve time limit T per subproblem.;
Output: Solution (m, π) of the FJSP problem instance Initialize m 0 ():
for Iteration r = 1: 10/5S do Obtain first I1 non-executed operations M,r,m,T) 11 Generate FJSP subproblem (see Appendix 6.5.2
O plan.r t- GGeellaOpeeratoon(((
P. + FJSP Subproblem(P.OO p.pmm M.
Iteration r 2 2 then
11 Learn to identify fy fixed operations in O Ooverlaper
Jurr t fo(P,, overlap, Py-1, my-1, my-1);
10
else
O fin.r f 0:
12
end
// Obtain the sesignment-based restricted FJSP subproblem P, Restricted_FISS Subprohlem(P,..) P.ariicdd fixr):
14
// Solve the restricted FJSP subproblem
(my; x,) t FISP Solver(P,;T):
16
17
11 Execute first S operations in Optan. with earliest start times
Ostepar + GerStepOperaaiios(@oaaaaa // Fix final solution for executed operations
S, T.);
19
for O0 E Ostepr do m(Ol0) + m, (0(): T(O()) - n., (00)):
29
21
23
end for
24 end for
Algorithm 2: GetPlanOperatiios
Input: Operations
O = {OO), O(10)) ordered based on the precedence or release time (Table 3
RHO plamning window size (H operations), RHO current iteration r, executed solutions (m, π)
Output: Operations in the current RHO planning window Olann,
O Opann + i
select the first H non-executed operations based on the sorted order
while O Optan,r H and < |O] do
if O $ (m, then
ppan...
end if
i i+1
end while
18

---

Published as a conference paper at ICLR 2025
Algorithm 3: GeeStepOperations
Input: Operations in the current window Oplan.r, RHO execution step size (S operations), RHO current iteration r, solution 11, (m,, Ts.r) of the Th FJSP subproblem
Output:
Operations executed after the ndhh RHO iteration Steepr
1// select the first 5 non-executed operations with the earliest process start time
Optan,r + Sort Optan, by the process start time (O popan
( Ostepir - (1 plan,r plan.r
A.3 INPUT FEATURES.
This section provides a detailed description of all input features, which can be categorized as the following three main parts:
For each operation in Optan,r overrtop.r U O new.r, design input features cap- ture the FISP instance information such as the earliest process start time of the operation (considering previously executed operations within the same job), the duration (mean / min max / std) to complete the operation by the compatible machines, and the operation's 's release time (for delay-based objectives);
(2) For each operation in Oovertap.r. we design additional input features to encode the solution information from the previous RHO iteration, including the duration, machine assignment of the operation and end time / delay.
(3) For each machine in M, further design input features that include the earliest process start time of the machine (considering previously executed operations by the machine), and the duration (mean / assigned to the machine.
min / max std) of the overlapping operations Ovverlap.r previously
As we consider the following different FJSP scenarios in our experiments (Sec. 5 we adjust the input features accordingly as follows
Makespan objective without observation noise: we use all input features as listed in Table
Makespan objective under machine breakdowns: we use all input features listed in Table 5] and the additional input features as listed in Table 6 to incorporate the machine breakdown information.
Total Start Delay objective without observation noise: we use all input features as listed in Table 7 where the delay input feature the start time delay for each operation based on the previous RHO iteration's 's solution, i.c. ( Sj
Total Start and End Delay objective without observation noise: we use all input fea- tures as listed in Table 7 where the delay input feature is the start and end time delay for each operation based on the previous RHO iteration's 's solution, i.e. T
$j + (Ox) fj 0) where (O,,) TT- (0,,x) + PEA m. mm--1(0,,.)) We further consider the end time related input features as listed in Table
Total Start and End Delay objective with observation noise: we use all input features in Table 7 and g Additionally, as described in Appendix A.5] we obtain noisy observations of each operation's 's duration each RHO iteration (the observation of the same operation may vary across different RHO iterations). That is, given the same machine assignment and
start time (f -1 from the previous (r- 1t)) iteration, the observed duration and end time for each overlapping operation can differ between the previous (r 1hh and current (zthh) iteration. As result, we compute the delay and end time delay in Table 7 and using the noisy observation from the previous RHO iteration, and further re-evaluate the delay, duration, and end time for the overlapping operations based on the current RHO iteration's 's noisy observation, detailed in Table 9
19

---

Published as a conference paper at ICLR 2025
We normalize all input features with mean and standard deviation computed the training set Kdatt-
Table 5: Input Features for the Operations and Machines for the makespan objective.
Type
Feature
Description
The earfiest start time of the job j associuted with the operation O,.. given by .n
job.start.time
the latest process end time of all executed operutions for the same job
avg.duu
Average duration of all compatible machine assignments for the operation
std dor
Duration standard deviation all compatible machine assignments for the operation
min dur
Minimum duration of all compatible machine assignments for the operation
max dur
Maximum duration of all computible machine ussignments for the operation
job
Job id for operation (j E (1,...77) before nornaliattion
ops_id
Operation id for the operation (k E (I,...ny) before normalization)
in_overlup
The operation Ojs E Qwerttppr at the current RHO iteration
prev machine
Machine assignment of the operation in the solution of...
(-1 if not onveverlap)
the previous RHO iteration (mn(O),e) E (O....IM I|} before normalization)
Operations
(-1 if not in overlap)
prev duration
Operation's 's process duration given by the previous machine assignment PiA
(00a)
prev_end_iime
End time of the operation
solution of
(-1 if not in (nveerl)
the previous RHO iteration ( (00,aa)
alt avg dur
Average process duration of all other machines.
(-1 if not ovverpp
... (not prey_ machine) to process the operation
alt std dur
Standard deviation of duration of all other machines...
(-1 if not invovrrlup)
(not prev_ machine) to process the operation
ali_min_dur
Minimum duration of all
machines...
(-1 if not in overlap)
(not prey machine) process the operation
alt.max.dur
Maximum durution of all other machines
(-1 if not in overlap)
.. (not prev machine) to process the operation
The earliest start time of the machine m. given by the latest process... ...
machine.starti sime
... end time of all executed operations assigned machine m.
Number of overlapping operations assigned to the machine m....
num overlap
in the solution of the previous RHO iteration ZoCOoseripp 10m = m)
Machines
avg end time
Average end time of overlapping operations aesigned to the machine
(-1 if num_ooo overlla is 0)
in the solution of the previous RHO iteration
std_end_time time
Standard deviation of the end
overlapping operations assigned to... ...
(-1 if aum, overlap is 0)
the machine the solution of the previous RHO iteration
max end time
Maximum end time of overlapping operations assigned to the machine
(-1 if num overlap is 0)
in the solution of the previous RHO iteration
min_end time
Minimum end time of overlapping operations assigned to the machine
(-1 if mum_mmmelllaa is 0)
in the solution of the previous RHO iteration
avg. duration
Average duration of overlapping operations assigned the machine
(-1 if num overlap is 0)
in the solution of the previcus RHO iteration
std_duration
Standard deviation of the duration of overlapping operations ussigned to
(-1 num overlap is 0)
the machine
solution of the previous RHO iteration
maxratration
Maximum duration of overlapping operations assigned to the machine...
(-1 if num, overlap is 0)
in the solution of the previous RHO iteration
duration
Minimum duration of overlapping operations assigned machine
(-1 if mummmmmnn ooverlp is 0)
in the solution of the previous RHO iteration
Table 6: Additional Input Features for the Machine Breakdown.
Type
Feature
Description
is break down
The current RHO subproblem has some machine breakdown
The machine assigned the operation the previous RHO suhprohlem.... ...
Operations
is ops break down
is broken down in the current RHO subproblem
The operation's machine assignment choices was restricted ...
reccvverd
in the previous RHO subproblem due machine breakdown,
but the breakdown is recovered in the current subprobime
is brcak down is_machine_heak.dddwy
The current RHO subproblem has some machine brcakdown
The machine itself is broken down in the current RHO subproblem
Machines
prev_start
Process start time of the operation in the solution of
(-1 if not in overlap))
the previous RHO iteration (O,,)
prev_end
Process end time of the operation in the solution of ...
(-1 if not overrap)
the previous RIIO iteration u.r 1,.--(000m)) (0,,)) - (0,a)) PAA
(0,,)
20

---

Published as a conference paper at ICLR 2025
Table Input Features for the Operations and Machines for delay-based objectives.
Type
Feature
Description
The carliest time of the job associated with operation O,.. given by ...
jom_start_time
the latest process end time of all executed operutions for the same job
ops_relense_time
The release time 5y, of the operation O,
avg.dur
Average duration
compatible machine assignments for operation
std_dur
Duration standard deviation of all compatible machine assignments for the operation
min dur dur
Minimum duration of all compatible machine assignments for the operation
Maximum duration of computible machine ussignments for the operation
joh_id
Joh id for the operation (j E (1, (1... hefore normalization)
ops
Operation
the operation (k (I,...ry | before normalization)
overlap
The operation O3a Onverlap.> the current RHO iteration
prev_delay
Delay operation
solution of the previous RHO iteration (0)a) - 8y,4
Operations
(-1 if not overlap)
prev machine
Machine ussignment of the operation in the solution of...
(-1 not in overlap)
the previous RHO iteration (m (O,x)) E (0,...IM - 11} before normalization)
prev. duration
Operation' 's process duration given by the previous machine assignment Py.
mh (9,a))
(-1 if not in_overlap)
alt ava.vvdee ddur
Average duration all other machines
(-1 if not in overlap)
(not prev machine) process the operution
alt_std_dur
Standard deviation of duration of all other machines....
(-1 if overlp))
(not prev machine) process the operation
min.mind
Minimum duration of all other machines
(-1 if not in overlap)
(not prey machine) to process the operation
alt dur
Maximum duration of all other machines
(-1 if not invoellppp
(not prev_ machine) process the operation
The earliest time of the machine m, given by the latest process
machine start_tims
end time of all executed operations assigned to machine m
Number of overlapping operations assigned to the machine m....
num overlap
in the solution of the previous RHO iteration Eogomentoo 1/m,-1 =000))m)]
Machines
avg.delay
Averuge delay of overlapping operations assigned to the machine
(-1 overlap is 0)
the solution of previous RHO iteration
std std_yelay
Standard deviation of the delay of overlapping operations assigned to
(-1 if num_overlap is 0)
the machine
solution of the previous RHO iteration
max delay
Maximum delay of overlapping operations assigned to the machine
(-1 if mum_mmooriii ovverla is 0)
in the solution of the previous RHO iteration
min_delay
Minimum delay of overlapping operations assigned to the machine
(-1 if overlverlap is
the solution of the previous RHO iteration
Table 8: Additional Input Features for the Total Start and End Delay Objective.
Type
Feature
Description
gap__arget_duu_tiing
The target time (3a operation O,,
prev start
Process start time of the operation in the solution of
Operations
(-1 if not ovverlap))
... the previous RIOO iteration (0;aa) Process end time the operation the solution of
prev_end
(-1 if not in overlap))
the previous RHO iteration (0,,) (0,,(0 +p, mm--100m
(0,a)
21

---

Published as a conference paper at ICLR 2025
Table 9: Additional Input Features for Observation Noise: given the solution from the previous RHO iteration, we re-evaluate the delay, duration, end time the overlapping operation based on the noisy observation at the current RHO iteration.
Type
Feature
Description
prev duration reeeval
Currently observed process duration of operation O ...
in.overlap)
(given the machine assignment from the previous RHO iteration)
Process end time
operation (given the machine
prev_end_reeval
Operations
assignment from the previous RHO iteration).
(-1 in.overlap)
reevaluated based on the current observed process duration
Delay of the operation (given the machine
prev srey_delayrreve
assignment from the previous RHO iteration)
(-1 not in.overlap)
reevaluated based on current observed prucess duration
Average delay overlapping operations assigned to the machine
avg deeelyyyeeeeee
solution of the previous RHO iteration,
(-1 num_overlap is 0)
observed process duration Standard deviation of the delay of overlapping operations assigned
reevaluated based the
selddllyyrooee reeval
the machine in the solution of the previous RHO iteration,
num_overlap 0)
Machines
reevaluated based on the current observed process duration
Maximum delay of overlapping operations assigned to the machinc solution the previous RIIO iteration,
max wel.ayyycevvlll
(-1 num_overlap 0)
observed process duration Minimum delay of overlapping operations assigned to the machine
reevaluated based the
min.delay reoeaal celveal
in the solution of the previous RIIO iteration
num_overlap 0)
reevaluated based on the current observed process duration
Maximum process end time overlapping operations
machine ceweeennd.iii time
assigned to the machine the solution of the previous RITO iteration,
(-1 num_mumaatt coverlp is 0)
based the previous iteration's observed process duration
Maximum process end time overlapping operations...
machine.end and_time_reent num overlap 0)
ussigned to the machine in the solution of the previous RI1O iteration,
reevaluated based on the current observed process duration
22

---

Published as a conference paper at ICLR 2025
Table 11: Training hyperpa- rameters.
Table 10: Architecture hyperparameters. The input dimen- sions (dg, dm) = (15, 11), (18, 13), (16. 6). (19, 6), (22, 12) for the five settings detailed Table and
Optimizer
Adam
Input Dimension
MLP Layers
2 ReLU
Learning rate
10-3
Operation 10plan.r do
IR 8)xda
Batch size
64
Activation
Machine [7] x dm
Positive Label
0.5
Embedding dimension duidden
Output Dimension
Weight ppp
64
R (H=S))
Num. of
5 x 106
Gradient Steps
A.4 ARCHITECTURE, TRAIN AND EVALUATION SETUP.
We use the neural architecture fa in Fig. 2 to identify the fixed operation subset Siz,r- The network takes as input a set of input features assoctated with each operation and machine, with the aggregated size R Rlotten.-(Xd, and R and outputs the predicted probability fo [0,1]]o.vrriap.. of whether each overlapping operation O E Ovverlap.- should be included in Fix,, The architecture consists of the following four main components:
(1) Input Embedding: We first embed the input vector of the operations Optan.- = Owwrllaper U O new,r and machines T, each with a input dimension of Rdd and TR into hidden representa- tions, each with hidden dimension of I Idduadden, We use two separate MLPs for the operations and machines.
(2) Machine/Operation Concatenation: We then concatenate the hidden feature of each operation O E plan.. with the hidden feature of the previously assigned machine m,-1(O) (the local feature), and global feature obtained by a mean pooling on the hidden features from all op- erations and machines. The concatenation results in hidden dimension of R 3-daaddden for each operation, and we apply another MI.P to project the dimension down Reduiden.
(3) Output:
Lastly, we pass the hidden feature of each overlapping operation O Ovverlap, through another MLP, which outputs the predicted probability that each operation O E O overlap,r should be included in fix,r-
We train the proposed architecture with Adam optimizer with learning rate le and batch size of 64 for 500 epochs with around 5 x 10a gradient steps. All hyperparameters are selected on the validation set and frozen before evaluating on the test set. Table 10 and IT provide a list of hyperparameters.
Training and Evaluation Setup. For each FJSP setting, we collect a small set Kps of 10 instances for parameter search on all RHO methods (default, baseline and learning), and large training set Kirain of 450 instances for neural network training. By default, we hold out validation set KCpal of 20 instances and test Krest of 100 instances each. We collect data, train, validate and test all methods on a distributed compute cluster using nodes equipped with 48 Intel AVX512 CPUs. A Nvidia Volta V100 GPU is used train all neural networks. The model training time is within 12 hours for all FJSP settings. The parameter search for all RHO methods (A (Appendix A.5.4) requires approximately 48-96 hours for each FJSP setting in the experiment Sec. 5 based on the problem size. Furthermore, the FJSP constraint programming solver CP-SAT allows multi-processing, we
12 CPUs when solving each RHO subproblem (P, / P,,) for all RHO methods (Default. Baselines and Learning) for both training and testing; we also use 12 CPUs to evaluate the Full FISP baseline. When collecting training labels, training data collection takes around 24-72 hours for each FJSP setting based on the problem size. In the experiment section, we report the solve time for different methods the test set Kreat (Table and Appendix A.6)
solve each unrestricted subproblem P. five times (Q 5); the
Table
Fig. 3
23

---

Published as a conference paper at ICLR 2025
A.5 EXPERIMENTAL DETAILS
A.5.1 FJSP INSTANCE DISTRIBUTION, MACHINE BREAKDOWN AND OBSERVATION NOISE.
Makespan-based Data Distribution.
We follow the similar data distribution as in the previous learning literature (Wang al. 2023a) but significantly increase the FISP problem sizes from 200 operations (previously) to up to 2000 operations (this work). Each FJSP instance is generated by sampling the following attributes:
(Rmachines: Rjobe, Poppeatiion.per.joll
(IM), |0/T( we fix [M] |0,17|
20 and consider a range of Roperations per. job E {30, 40, 1003. That is, we have (IM), (0,TT E {[10, 20, 30), (10, 20, 40), (10, 20, 60), (10, 20, 100)], with the total number of operations ranging from 600 to 2000.
Compatible Machines My For each operation Oj,t E O, we randomly select a sub- set of machines M3.e E MM with size [Mjall ~ Uniform [1. |MB as the compatible machines for the operation.
Process Duration PJA we sample the duration of operation Oj,x O processed by ma- chine .M from a uniform distribution U[1, 99).
Machine Breakdown, As a step towards online / dynamics FISP, ours experiments in Fig. (right) accounts for machine breakdowns during the RHO solution process. The intensity of machine break- downs is determined by two factors: 1) the frequency of breakdowns 2) the proportion of unavailable machines during each breakdown. For each FJSP instance, we simulate a series of machine break- down events represented by set of time intervals [t1.12...... For each breakdown event, we randomly sample a subset of machines M S. SM, which become unavailable during the event. Specifically, the first breakdown event starts at time 13 ~ U[50, 150] and lasts for a duration of dur. Each subsequent breakdown occurs at time 1 1/-1+ + dur + U[wn, Wab) and similarly lasts for a duration of dur. We sample the subset of breakdown machines . by selecting each machine in M i.i.d. with a probability p². In our experiments, we explore three levels of breakdown intensities : 1) Low: we set dur 100, wio = 400, Wid = 600. p" = 0.2, 2) Mid: we set dur = 100, wis = 175, Wab = 300, pd 0.35, and 3) High: we set dur 50, wib 100, Wab 200, p 0.5.
Following dynamic FJSP literature (Zhang and Wong 2017). we combine periodic RHO subproblem optimization with event-based rescheduling: when machine breakdown event starts or ends, we re-optimize the updated RHO subproblem using the updated machine availability. This event-based rescheduling affects (1) the RHO subproblem step size, which may be reduced due to breakdown- triggered re-optimizations. Specifically, for each RHO iteration, we execute the set of operations Oezea, in order of their scheduled end times. a breakdown occurs during an operation's 's execu- tion window, we halt that operation and any subsequent ones, and reformulate the RHO subproblem with the updated set of the first W unexecuted operations, incorporating the updated machine avail- ability for re-optimization. (2) If all compatible machines for operation are down, defer that operation, along with any subsequent operations in the same same until the breakdown ends.
Implementation-wise (1) is formally described in Alg. [] which replaces Alg. 3 for the RHO op- eration execution step; (2) is formally described in Alg. which replaces Alg. to construct each RHO subproblem.
Delay-based Data Distribution. Following common FJSP instance generation procedure in the literature (Behnke and Geiger 2012), we generate each FJSP instance by sampling the following attributes:
(Amanhhnnes: Nijohe; Ploperations perr _job)ah)) (I T 10/T): we consider series of large scale settings {(25, 25, (30, 30, 24), (35, 35, 30), (40, 40, 40)}. with the total number of operations ranging from 600 1600. We further set the compatible machines M M for all operations O E O.
Process Duration p we sample the duration of operation O₁,t O processed by ma- chine m E A from uniform distribution U [oow [nigh], with how ~ Uniform((3, 5, 7, ))) and lhigh Low + Uniform( 12, 15, 18, 21,), resulting in the duration range pM
[3, 30::
24

---

Published as a conference paper at ICLR 2025
Release time: sample the release time for all operations 10 I within each job j as $ ~ U[0,, 15)) and 8y,k = $j + ([0, 15)) for all k >>1
Target end time: we sample the target end time for each operation Oj, k as jj.h 8 +
U U[0,, 30]): this attribute is used when the objective contains total end delay (Sec. 5.2).
Observation noise. In the observation noise setting (Sec. 5.2). the process duration Pj. Specifically, we generate the clean (true) process duration Pf.k for all operations and machines (which is only partially observed) following the procedure described above. Then, each RHO iteration, perturb process duration as follows: consider the oper- ations O plon.r {O(1) ..... } (ordered by their release times) in the current iteration's 's plan- ning horizon. We assume perfect observation
have noisy observation of
the first S < H operations with earlier release O(5),, and we have noisy observation for a randomly selected subset Operturb.r of the remaining operations with later release times, where we select each operation in Optan,r 'Oenean r to be included in Perturrb, uniformly at random with probability of = 20%. We then set the noisy observation of the process duration for each operation Oj,x Oplan.r by machine m E Miik at the current RHO iteration r as:
times Oclean.r = {O(2)
m PJ.k
PIA clip(p", + U,,5,55,,,330 if operation Oj E O Pperurrb,
if operation Oj.6 E Oeleannr
Notably, we may have different noisy observations for the same overlapping operation in different RHO iterations. That is, we may have 1 mm.--1 # Pi
mm.r for the same operation Oj, and machine m.
Operation execution under observation noise. After obtaining the solutions (m, म. to the noisy FISP subproblem, we execute subset of S operation and update the final full FISP solution (m, π as follows (replacing Line 17-21 in Alg. with the procedure in Alg. ( We first determine Ostepar as the operations with the earliest process start time according to the noisy solution म,. Then, for each operation Oj,A Ostepir (ordered by the solution start time (0,,)) we assign the process
(O,xx,
operation to the machine m(0 = m, (O,a), which takes a true duration of Pj.k the operation. Due to discrepancy between observed duration at planning and the actual duration execution, the operation may be able start at its solution start time म (O,.a) given by the solution. We hence further adjust the actual start time ((Oj.A) at execution to maintain solution feasibility. The detailed exccution procedure provided in Alg.
Algorithm 4: GelPlanOperatiion Under Machine Breakdown
Input: Operations O
(O(1),.. O(101) ordered based on the precedence order or release time ('Table RHO planning window size (H operations), RHO current iteration r, executed solutions (m, TT)
Output: Operations in the current RHO planning window O Opton.
O plan, + [ 0
lobo = Set()
// select the first И non non-executed operations based on the
sorted order
while O Optan.rl < H and < |0| do
if' Ol0) & (m, then
if All compatible machines of ( are down then Ignored Jobs add( ob of O(1)) continue end if
if Job_of _ _ continue end if
Ignored then
12
O Optan appennd(p
13
14
end if
15
i d i 11
16 end while
25

---

Published as a conference paper at ICLR 2025
Algorithm 5: Execute Operations Under Machine Breakdown
Input: Operations the current window plan.r, RHO execution step size (S operations), RHO current iteration r, solution II, (mys T. of the Thhh FJSP subproblem
Output: Operations executed after the yd RHO iteration Ostep.r
Opaan, f- Sort Oplan,r by the process start time (O()))(())))))) 100
Ostep.r +
for Oz.k E Stepp. (sorted by the solution process start time) do if machhne breakdown starts or ends during the operation 's execution window (T(O),)) Ti (Og,)) then // End the current RHO subproblem. Do not execute any more operations.
break
end if else
O append-)
10
end if
end for
Algorithm 6: Execute Operations Under Observation Noise
Input: Operations in the current window Opton. RHO execution step size (S operations): RHO current iteration (partial) solution II (m, x) of the full FJSP problem instance P before the current iteration r; solution II, (m, *t,) of the n FISP
MEM subproblem under the noisy observation; clean process duration (27 C0
Output: Updated (partial) solution 11 = (m, x) of the FISP problem instance P after the current RHO iteration based on the clean process duration
/// Find executed operat ions for the current RHO iteration, using (m,, 7
plan, + Sort Optan,r by the process start time (ow
Ostep.r f (1 plan plan,r]
(S)
// Auxiliary variables to track solution feasibility
machine end time {alt: max T0(0,,)) for each machine alt M)
Og,EE(m,x)
m(O,
job_end_time sind_time (:: (g,.E(m,T))
(O,,)) for each job ET}
7/ Fix the final solution for the executed operations based on the clean process duration.
for Oji E Ostepr (sorted by the solution process start time) do
m(Ox,x) + (,,0
// Update the process start time to the earliest feasible start time
(O,,,) max,),(O;,), machine end time(m((s,x)), job end timelj])
12
// Re-eva luate the process end time based on the clean process duration
T. + (0,,)) + m(0,,x)
// Update the auxiliary variables to track feasibility machine_end.ce (idetimm(((( max (machine (im time job_end.time|j] < max (job_end.time/]) mt)
15
16
17 end for
26

---

Published as a conference paper at ICLR 2025
A.5.2 FJSP FORMULATION
Decision Variables. Given a FJSP problem instance
P = TM,,O, o, process duration (p7)k) 03
meM,,,
(optional) release time { (optional) target end time (tz,)),,,eo)
The constraint programming formulation for the FJSP is obtained by introducing additional boolean variables denoting whether an operation is assigned to a machine That is, we define the following set of decision variables
x
(=(0,,)),;,.s0 (dur(O,,:)),,, to. // process start time, duration, and end time (lnt(O;,)) OALEO, afteM1a
boolean variable: whether O is assigned to machine alt
(Tat((0).)) O, allEMMaa
process start time if Og & is assigned machine all
(dur (0,,k)} O0,E0, alreM,, )
// process duration if O3,a is assigned to machine alt
(Tr 0,,Eo) alreM,,..
// process end time if Oj is assigned to machine alt
(3)
where the target end time and the decision variables related to the process end time are only used when the objective contains total end delay. From the above decision variables, the machine as- signment of operation jj can be found as m(Oj.k) process start time of the operation can be found as i (O),k.
all E Mi,k. wher late (Oza)) = 1, and the
FJSP Full and Subproblem Formuation. Given the above decision variables, the Constraint Pro- gramming (CP) formulation for the full FJSP problem given in Alg.
Unrestricted Subproblem P.: Given the of operations in the current planning horizon O plan.r we can obtain the the subproblem instance P, and the set of decision variables X, associated with the restricted operation set O plann,r. Then use the same CP formulation in Alg. 7 on the decision variables X,; we additionally introduce new constraints in Alg. 8 which requires operations Oplan.r be processed after all previously executed operations within the same job or the same machine.
Assignment- Based Restricted Subproblem P,: Given set of operations in the current plan- ning horizon plan.r, we follow the same CP formulation in Alg. 7 and 8 as for the unrestricted subproblem P,. Given the fixed operations Oftrr S Ovverlap.rs we further restrict the compat- ible machines for each fixed operation as the single machine from the previous RHO iteration's s solution, i.e. we restrict M,,e = (0= for all operations Oj. E O fiz.r.
'Our implementation is based on the CP-SAT's immiittttionnn http::///...tttpttttttttt......t
/googl Pooogle/or-ton tool 8// stabl http:/saaleeeeeeeeeeeeeee ob
27

---

Published as a conference paper at ICLR 2025
Algorithm 7: FISP Constraint Programming Formulation
Decision Variables: X (see Eq. equation Objective:
Makespan:
min max (((0,,k) X 23NEO
Total start delay:
min Σ T(O,,)) - -jik
(4)
OS,EO
Total start and end delay:
min Σ T(O,,k) 8j,k + max(F,(O5.)) tg,2.00
O3NEO
Constraints:
// Machine gnment definition for each operation for each operation On, O do // Operation end time definition
= =x0,,,))(0,,)))) + dO,.))
(5)
for each possible machine assignment alt E M, do // Operation duration definition for machine assignment
10
alt duratr(O;,)) Pj
(6)
// Operation end time definition for alternative assignment
(O,a) = Tate(Oj,x) + durauu(Oji.) // Enforce solution linking if alt is selected
(7)
13
(m(O),,) = Tall Tatt (nforce())))))))(((:):(()))))) = 1)
(8)
15
(d. dur (O Enforcelf((( (nd 1)
(9)
16
(TT(O,,)) Ttaate (O Enforcell(llr 1)
(10)
17
end for
18
// Only one machine assignment alternative can be selected
19
Eracttonee(la:((0.k (at))))))(((ttMMa.. (aleEM,
(11)
20
end for
21
// operation precedence constraints for each job
22
for each job j E do for each operation O₁ with 1 1 S n2 do
23
24
(O,,,) S (0,
(12)
25
end for
26 end for
27 Non-overlapping Operation constraints on each machine
28 for each machine alt E M do
29
NoOverlap
(Interval[TTar (arerv (t (0a0 (13)
30 end for
28

---

Published as a conference paper at ICLR 2025
Algorithm 8: Additional Constraints for FJSP RHO Subproblems P.
Decision Variables: X, for the operation set O Ovvertap.r in the planning horizon (see
Eq. equation 3)
Solutions of Previously Executed Operations: (m, π)
Additional Constraints:
// Compl aance with previously executed operations (if exists)
if (m, is not empty then
prev srev_machine_ere end _nd_time time + (alt: max m,(O,,)) for each machine alt e M
E(m,()
=(0,
prevejob.end.co time {j: max
(O,k)) for each job j E ET
E(,.E(
for each operation Oj. E O do
// Ensure processing after all executed operations within the same job
T(O,,) 2 prev.job.end.tmme])
11
// Ensure processing after all executed operations on the same machine
12
for each possible machine assignment alt E Mj,x do
(O 2 prev machine end timefall) end for
14
15
end for
16 end if
29

---

Published as a conference paper at ICLR 2025
Machie Conatannt
Oberaton Pracederro
92 e(0kg)
Machine
Og
Og
Og
Machine 2
Oy
Og
Og
Machine 3
On
Oz
Og
Machine 9
Dg
Time
makhapen
massepon
(9) atsp
(b) Construct Subproblem
Mechine
Oiy
Op
Machine
Oy
Ozz
Ogs
Machine 2
On
Op
O₂-
Machine
Ou
Machine 3
Og
Time
makeespan
(4) Solve Subproblem
[4] LNS step r
Figure 5: The Large Neighborhood Search (LNS) Pipeline from PPacino and Van Hentenryck 2011
(a) At the th LNS iteration, we start with a complete solution IT for the full FISP. The solution at the first iteration given by solving the full FSJP for short duration (30s). (b) We construct FJSP subproblem by selecting subset of FJSP operations to update their solution. Two subproblem selection methods are considered based on time and machine based decomposition methods. When constructing the FJSP subproblem, we include additional constraints on the operation's 's start time and each machine's 's available time so that the subproblem's 's solution is compatible with the solution of the non-selected FJSP operations. (c) We feed the FJSP subproblem into subsolver to get new solution II,- The old solution of the subproblem is given to warm start the solve, as it empirically improves the performance. (d) We update the complete solution IT with the new subproblem' 's solution II, and repeat (a)-(d).
A.5.3 BASELINE DETAILS
Traditional solver w/o decomposition The CP-SAT and Genetic Algorithm (GA) results are, respectively, obtained by applying the competitive constraint programming solver OR-Tools CP- SAT (Perron and Didier), and the widely used hybrid genetic algorithm with tabu search meta- heuristics (Li and Gao 2016). to solve the full FJSPs without decomposition. These comparisons emphasize the significance of decomposition in solving long-horizon FJSP.
Learning-based solver w/o decomposition. For each setting, we train DRL model (Wang et al. 2023cp on the same set of 450 training instances as L-RHO and also on a larger set of 20,000 instances, following the original paper" and Sampling strategies (100 and 500 samples).
(7) At inference time, we decode the DRL model using Greedy
Traditional solver w/ decomposition. Fig. provides an illustration of the Large Neighborhood Search (LNS) algorithm that we compare as a baseline in the offline setting. In particular, (Pa-) cino and Van Hentenryek] (201)) introduces Time Decomposition and Machine Decomposition to select different LNS neighborhoods for large-scale FISP. The implementation details for each LNS iteration are as follows:
The ARD-LNS (Time-based) leverages temporal locality to select random start and end time of a contiguous time interval to define the LNS subproblem. imposes additional machine availability constraints and operation precedence constraints in defining the subproblem. The former restricts the start and end time of each machine to be compatible of fixed operations, and the later restricts the start and end time of each selected operations to be compatible with the fixed operations within the same job. It further includes (1) adaptive LNS subproblem size: The contiguous time interval starts at length of 20% of the horizon. If no improvement is found within 5 iterations, the size of time window increases by 5%, with the longest time window length capped at 50%. If improvement is found, the size returns 20%. (2) New objective for each LNS subproblem: Instead of makespan, it instead maximizes the distance between
We use the publicly available implementation from the authors at wttphttt///// // www..bcw.wwwgc.....
30

---

Published as a conference paper at ICLR 2025
each operation's 's end time and its latest feasible completion time the surrogate objective when solving each LNS subproblem.
The ARD-LNS Mlachine-basedd in each LNS iteration selects a subset of machines and define the subproblem as the set of operations on those machines. As we select all operations on each machine, the subproblem only requires the operation precedence constraint. The subproblem solved with Makespan as the objective.
In the original paper by (Pacino and Van Hentenryck 2011p, the LNS procedures are benchmarked on the dataset from (Hurink et 1194)) where the largest instance consists of 225 operations (15 machines, 15 jobs, and 15 operations per job). We successfully reproduced their reported results on these instances; however, when applying their algorithm to the significantly larger-scale setting considered in Table [ we observed dramatic degradation in LNS performance. In contrast, the RHO-based algorithm maintains competitive performance on these long-horizon FJSP instances.
gearning-guidess solver w/ decomposition: Oracle-LNS (Time-based). We use LookAhead Oracle similar to the one in previous learning-guided LNS studies (Huang et al. 2022 Li et al., 2021]. each LNS iteration, we first select K = 10 Time Decomposition LNS subproblems candidates. We then look ahead by solving these subproblems and choose the one that gives the biggest improvement in makespan. We randomly decide whether to evaluate the improvement based on the local makespan (for the current subproblem) the global makespan (for the full FJSP problem), as this approach works better than focusing on just one objective. The local objective helps LNS prioritize subproblems needing the most fine-tuning, even though updating them doesn't immediately impact the final makespan. Meanwhile, the global objective encourages selecting sub- problems toward the end of the time horizon optimize the overall makespan. This differs from prior studies on Vehicle Routing (Li et al., (2021), Multi-Agent Path Finding (Huang et al. (0022) or Graph-Bane Mixed Integer Linear Programming (Huang al. 2023). where improving the local subproblem directly enhances the global objective.
RHO decomposition. Detailed descriptions of different RHO baselines (Default, Warm Start, Random, First) can be found in Table 4 In Table [ for Default RHO, Warm Start RHO, and L- RHO, we set the RHO parameters (H, S, T, Tes) ) = (80, 30, 60, 3). That is. each RHO subproblem involves H 80 operations, and each execution steps move forward S 30 operations. The time limit of solving each RHO subproblem is T = 60s, and we early terminate the CP-SAT (with callback) if the best objective does not change after Te. = 3s. For Default RHO (Long), we use more generous early stop time Te. = 10s, where we see the Default RHO's performance improves the expense of substantially longer solve time. In Table 2 the RHO parameters are determined based on an extensive parameter grid search procedure, as described in Appendix A
31

---

Published as a conference paper at ICLR 2025
Oseecive
9.00
glth
Random 30%
Rendom 41%
Random 20%
Defout
3500
3000
Random 40%
Random 20%
Random 30%
Dafbut
2000
d0, RG,
Firs: 2015
2500
30%
2014
Fiss:
Whrm Start
-500
ag hn
Werm
Crosio
600
2000
Oracle
Sotra Times
Solve Time
Figure 6: The objective and solve time for a variety methods and RHO parameter settings, average across set Kps of FISP instances with sizes (25, 25, 24) on the left and (30, 30, 24) on the right. Each dot represents a method and a RHO parameter setting (H, SeT.TTe) We label the selected best parameter setting for each method with text.
A.5.4 ROLLING HORIZON PARAMETER SEARCH
We perform grid search to find the best parameter setting for each RHO variant (default, baselines and our learning method). We consider the following four parameters as a joint parameter setting
{ RHO Planning Window Size H, RHO Execution Step Size S
Time Limit T of each RHO FJSP Subproblem,
Early Stopping Time Tes for each RHO Subproblem}
In particular, the Early Stopping Time Tes represents the time to early terminate the CP-SAT (with callback) if the best objective does not change after Tes seconds. We introduce this parameter due to the empirical observation that under a (relaxed) time limit, the objective of the best feasible solution obtained by CP-SAT may stuck at given value for a long period of time.
We perform a grid search to evaluate the performances on a set Kps of FISP instances for each FJSP data distribution in the experiment Sec. 5 on the following parameter settings
H = =(Window Size, Step Size) x (Time Limit, Early Stop Time) [[(50, 15), (50, 20), (50, 25), (50,30) 30),
(80, 20), (80, 25), (80, 30), 35), (80, 40), (100, 20), (100, 30), (100, 40), (100,50) 50)}
(14)
x (115s, 2s), (30s, 3s). (60s, 3s)}
We visualize the objective and solve time for all methods and parameters in Fig. 6 where each dot represents the objective and solve time (averaged over Kps) of each method evaluated under a parameter setting. For each method, the dots of all parameters define Pareto frontier for the objective and solve time trade-off. As we aim reduce solve time with minimal impact on the objective, we use the following procedure to identify the individual best parameter setting of each method:
Let obj" be the best objective across all methods and all parameter settings. We empirically find that obj* is typically achieved by Oracle data collection method, which offer an objective improvement from default RHO.
For each method M, we perform a line search with a step size T3 = 0.1 to find the best parameter setting: starting with iteration i 0, let H.M C H be the parameters whose objectives are within the 7th bucket [(1 + x i) x obj", (1+r) x (i 1)) x obj*]. If H.M" + 0, we then select the parameter setting H M+ E H, with the shortest solve time as the individual best parameter setting for the method M; if H.M. 0. we then move on to the next iteration i + 1 and repeat the procedure, until we find the individual best parameter setting.
The line search procedure ensures that if there are two parameter settings with similar objectives, but results in much shorter solve time than the other, would select the parameter setting with a shorter solve time as the best parameter setting for the method. In Table We provide a list of the best parameter setting for each method, identified through the line search procedure.
32

---

Published as a conference paper at ICLR 2025
In Table 2 we apply the best parameter setting selected for each RHO variant to evaluate the method's performance. L-RHO is evaluated using the same parameters as Oracle. Since the best pa- rameters for Default, Warm Start, and Oracle consistent across different settings, we use fixed set of RHO parameters (H,S, )s)) = (80,30 30, 60, 3) in Table I to avoid additional computation for parameter search.
Table 12:
Best RHO parameter settings S,T, of various RHO methods for the different FJSP settings presented in Table 2 Parameter settings highlighted in bold are the same as the Oracle's best parameter setting for each FJSP setting.
25, 25, 24
30, 30,
35, 35, 30
40, 40, 40
Default
(80, 20, 60. 3)
(80, 25, 60, 3)
(80, 30, 60, 3)
(80, 20, 60, 3)
Warm Start
(80, 35, 60, 3)
(80, 25, 60. 3)
(80, 25, 60, 3)
(80, 20, 60, 3)
Fix first 20%
(80, 20. 60. 3)
(100, 30. 60, 3)
(100, 40. 60. 3)
(100, 40, 60. 3)
Fix first 30%
(80, 20, 60, 3)
(100, 30, 60. 3)
(100, 40, 60. 3)
(100, 40, 60.
Fix first 40%
(80, 20. 60. 3)
(100, 30. 60, 3)
(100, 30, 30, 3)
(100, 30, 30. 3)
Fix first 50%
(80, 30, 30, 3)
(100, 20, 30. 3)
(100, 40, 30, 3)
(100, 40, 30.
Random 10%
(80, 25, 60, 3)
(80, 25, 60,
(80, 25, 60, 3)
(80, 25, 60, 3)
Random 20
(80, 20, 30, 3)
(80, 25, 60,
(80, 25, 30, 3)
(80, 25, 60, 3)
Random 30 %
(80, 20, 30, 3)
(80, 30, 60, 3)
(100, 30, 30, 3)
(80, 25, 30, 3)
Oracle
(80, 25, 60, 3)
(80, 25, 3)
(80, 25, 60, 3)
(80, 20, 60, 3)
A.5.5 PERFORMANCE OF RHO METHODS FOR FJSP (00,30, 24).
In Table 13 we provide the detailed results of all RHO baseline methods' performance under both the individual best RHO parameter setting (Individual Best Param.) and fixed RHO parameter setting (the Oracle's best parameter, Same Param.) for FJSP (30, 30, 24) with the total start delay objective and no observation noise, which is used as the base setting in Fig. 3 middle, (ii), of Sec.
Table 13: Time and Objective improvements (TI%, 01%) of different RHO variants for FJSP (30, 30, 24) under the start delay objective. We report the mean values (higher the better, nega- tive indicates degradation) and two standard errors. The best TI% and 01% among the RHO meth- ods (excluding Oracle) are bold-faced. L-RHO significantly outperforms all baseline methods in the objective with substantially reduced solve time. Additionally, L-RHO closely aligns with the performance of the Look-Ahead Oracle, demonstrating its learning effectiveness.
Individual Best Param.
Same Param.
30, 30, 24
TI
Of %
TI %
O1 %
26.9s
Defunlt
(0.0% =: 0.0%%
(0.0% :: 0.0%)
0.0% à 0.0%
0.0% 1: 0.0%
Warm
-0.1% 1.3%
0.8%
-0.1% 1.3%
2.25
first
1.5%
-14.3%
19.4%
-23,1%
3,8%
Fix first 30%
12.4%
1.6%
-21.5% 4: 3.8%
20.9%
1.7%
-57.9%
5.1%
Fix first 40%
19.5%
+ 1.7%
-41.2%
+ 4.4%
17.3%
2.0%
-131,4%
7.7%
Fix first 50%
7.9%
d: 2.0%
-78.1% 1: 5.5%
19.0% + 2.1%
-288.5%
1: 13.0%
Fix first 60%
33.6%
d: 1.7%
225.88%
4: 11.8%
26.9% #: 2.3%
.16.00 à: 19.9%
51.0%
-727.
50.251
-84.8%
Random 10%
1.8% 1.7%
-20.2%
1.69%
-20.2% 3.1%
Rundom 20%
0.3%
2.0%
-54.7% 4: 4.6%
1.8% 1.7%
-20.2% 3.1%
Rundom 30
9.9% +: 2.3%
-153.6% +: 8.1%
-0.3% +: 2.4%
-103.8%
7.2%
Random 40 %
-10.9% + 3.3%
-105.0%
7.2%%
2.0% 2.5%
16%.68% 9.43%
(Oracle)
(49.9%
4: 7.i%) 7 (15.3%
2.225%)
(49.9%)
1.1%)
(15.3%
+ 2.2%)
L-RHO (Ours)
41.5% 2 6.1%
14.0%
10.2%
41.5% 6.4%
14.0% 1 10.2%
A.5.6 PERFORMANCE OF RHO METHODS UNDER THE SAME RHO PARAMETER.
In Table 14 present the performance of all RHO variants under the same RHO parameter setting
(the Oracle's best parameter), for all three FJSP settings in Table 2 The TI% and 01% is relative
to Default RHO under Default's best parameter (same as in Table 2 From Table 13 and 14
33

---

Published as a conference paper at ICLR 2025
observe that although the First of baseline substantially reduce the solve time when of is high, the associated objective drastically deteriorates at the same time. In contrast, our learning method L-RHO not only significantly significantly accelerates Default RHO, but it is also the only method that simultaneously achieves a notable improvement in the objective.
Table 14: Time and Objective improvements (TT%, 01%) of different RHO methods in comparison
with Default RHO (with Default's best parameter) for three FJSP settings in Table all the methods are evaluated on the same RHO parameter setting (Oracle's 's best RHO parameter). We report the mean values (higher the better, negative indicates degradation) and two standard errors. The best TI% and O1% among the RHO methods (excluding Oracle) are bold-faced. L-RHO significantly outperforms baseline methods the objective with substantially reduced solve time.
25, 25, 24
35, 35,35, 30
40, 40, 40
%
OI %
01
Default
17.6% 1.3%
-6.9% 4.3%
-16.0% = 2.1%
5.1% 3.8%
0.0% : 0.0%
0.0% : 0.0%
1.3%
11.2%
first 20
36.2% 1.2%
-3.78%
4.0%
Fix first 30%
41.6%
1.2%
-14.6%
3.0%
40.9% 1.7%%
-91.5%
2 5.4%
1.5% +: 4.2%
-207.7% :: 17.3%
Fix first 40%
42.1% + 1.3%
-16.8%
4.2%
-5.1%
2.69%
-222.2%
11.1%
4.7% 7.7%
-423.2% 1: 30.6%
Fix first 50%
43.8%
1.2%
-100.9%
6.8%
3.21% + 3.0%6
-359 2%
16.6%
24.5%
3.7%
-748.0% +: 46.2%
first 60%
46.9% 1.4%
-218.%
12.1%
17.2%
2.7%
-600,
29.1
40.7% 2.5%
-1118.0%% 80.6%
first
-594.5%
138.9%
Random 10%
2.7%
-16.8%
Random 20%
24.2%
1.5%
-32.8%
3.668
-18.8%
2,099
-58.0% 5.7%
-1.6% 4: 3.15
-61.8%
10.0%
Random 30%
23.6%
=: 1.7%
-75.1%
5.99
-17.4% = 2,3%
-104.1%
7.3%
-0.8% 3.3%
-131.8%% :: 12.8%
Random 40%
27.4%
2.0%
-153.3%
9.1%
-14.4%
3.1%
-24.99%
11.4%
1.4% d: 3.6%%
-202.6% 1: 20.9%
(Oracle)
(60.366
1.0%)
(18.5%
1.7%)
(10.5%
1.0%)
(22.4%
1: 2.3%)
(53.2%
1.3%)
(12.8%
4.4%)
L-RHO (Ours)
53.05 1.0%
16.0%
1.9%
38.1% 1.3%
21.0%
2.4%
47.3%
2.2%
13.13% + 4.4%
34

---

Published as a conference paper at ICLR 2025
A.6 ADDITIONAL EXPERIMENTAL RESULTS
A.6.1 PERFORMANCE ON REAL WORLD DATASET DAUZÈRE-PÉRÉS AND PAULLI 1997
We find most of the traditional benchmarks on small scale (< 500 operations), We benchmark the performance on Pauzère-Pérés and Paulli (997), 1997, which is the largest traditional benchmarks available, containing 16 instances evenly divided to three different sizes (respectively. 196, 293, and 387 operations). We exclude 4 instances from the dataset, which is simple and take < 2s for RHO methods to solve. To mimic large scale settings with more operations, We further replicate all operations for each job k times, with k 3, 6, 9 to mimic long horizon scale settings with more operations. We provide the performance comparison in Table [5] For DRL and L-RHO, we both directly transfer the model learned on 600 operations (I0, 20, 30) setting the real world instances. The best known solution for the Dauzere original setting has an average makespan of 2/20 with standard deviation 78.
We find that the direct transfer setting, our L-RHO outperforms DRL in the real world dataset, achieving a close gap with respect to best known solution in the literature for the smallest non- augmented setting, and the performance advantage further holds for longer-horizon augmented set- tings. Furthermore, L-RHO significantly speeds up Default RHO in all settings, demonstrating the benefit of introducing learning to accelerate RHO. We further note there exists slight mismatch in the training distribution and the real world dataset, and it an interesting future work to train the model on a diverse set of distribution to further improve L-RHO's transfer learning performance.
Table 15: Performance Comparison on the Dauzère- Péries and Paulli 1997) dataset. The best known solution of the original dataset (the first result column) has makespan of 2120 + 78. In the last three result column, we randomly sample (with replacement) x k operations for each job to mimic the long horizon settings.
Original
Augment
Augment
Augment
Time
Makespan
Time
Makespan
Time
Makespan
Time
Makespan
DRL-208 (Wang)- Greedy
2:1
2493
44
6 0.5
7279 1: 69
12:2 1.0
14337 4: 218
22 d: 2.6
21218 :: 250
DRK (Wang) Sumple
8++1 1
2279
+ 9.6
6946
235 42
13935 + 1664
534 + 95.2
20784 + 226
DRL-20X (Wang)- Sample 500
35 6
2253
321 + 58
6887 79
1341 4 231
13884 :: 162
3014 + 516
20722 +: 216
DRL-20K (Wang)- Sample T0UD
72+ 13
2247
20
670 + 116
6858 + 83
2679 +: 458
13859 :: 1.56
6068 + 1038
207066 +: 217
Default RHO
83 1. 33
2174
68
290 1 84
6505 4. 132
509 1 150
13065 1 428
794 241
19689 1. 592
Warm RHO
75++
68
241
450
13034
19589 609
L-RHO Transfer
65 : 23
2183 66
199 + 70
6499 :: 254
345 : 134
13015 4: 504
492 :: 200
19593 :: 725
A.6.2 ACCURACY, TPR, TNR, PRECISION, AND RECALL OF THE LEARNING METHOD.
We provide the accuracy, true positive rate (TPR), true negative rate (TNR) precision, and recall of the learning architecture (Fig. 2 in Table 16
A.6.3 ABLATION STUDY: A DETAILED COMPARISON WITH ATTENTION-BASED ARCIITECTURE.
We compare the architecture in Fig. 2 with a more advanced attention based architecture shown in Fig. 7 We make the following two modifications to obtain the new architecture:
First, at the machine/operation concatenation block, for each new operation O E Onew.r that does not have a machine assignment m we concatenate it a dummy machine embedding (all-zero feature) and the global embedding from mean pooling on all entities (operations and machines).
Then, after the machine/operation concatenation block of the original architecture, we perform a Multi-Head Attention between the overlapping operations Ovvertap.r and the new operations Onew.r (with attention heads), and we also include a residual connection for the overlapping operations.
For the Multi-Head Attention, we take the overlapping operations' embeddings as queries (Q), and consider the following three setup for the attention keys (K) and values (V): (1) New operations only, (2) Overlapping operations only, and (3) Both overlapping and new operations.
35

---

Published as a conference paper at ICLR 2025
Table 16: Accuracy, True Positive Rate (TPR), True Negative Rate (TNR), Precision, and Recall of the learning architecture in Fig. on the hold out validation set for each setting in Table 1 and
Accuracy
True Positive Rate
True Negative Rate
Precision
Recall
Table
600 (10, 20, 30)
0.77
0.81
0.67
0.86
0.81
(10, 40)
0.79
0.67
1200 (10, 20, 60)
0.76
0.77
0.73
0.87
0.77
Table
625 (25, 25, 25)
0.78
0.71
0.85
0.83
0.71
1225 (35, 35, 35) 1600 (40, 40,
0.72
0.87
0.79
0.81
0.69
0.90
0.83
0.69
In Table 17 we find that for option (1) and (2) the introduction of the attention architecture leads to slightly higher True Negative Rate (TNR) but lower True Positive Rate (TPR) and a slight reduction accuracy, when compared with the architecture without attention. Furthermore, when evaluating the performance on 600 operations FJSP (10, 20, 30) in Table I we see that option (1) and (2) results in longer solve time but improved makespan from the architecture without attention. We also note that option (3) is strictly dominated by the performance of the architecture without attention.
We that the TNR-TPR tradeoff the performance and solve time aligns with our theoretical analysis, as fixing something that should not have been (low TNR) harms the objective but helps the solve time, while failing fix something that should have been (low TPR) harms the solve time and also indirectly harms the objective (under fixed time limit).
Due to the time benefit of the architecture without attention and the relatively competitive objective, we believe it makes sense to keep the simpler architecture without attention in the main paper.
Operotion-wise Concat.
Resicual
MLP Operation-atee wdse Sigmokd
0.6
Overlopping Operations
MLP Operation)
0.3 (not
Openraliont
Multi hnee- Cinos Attention
0.7 (ts)
Mean
New Opeaaiion
Pool
I can
Fool
Machines
Input Fosrure
Maclénc/Oparrtiónn Concaleration
Overlp//New Operaton Cross Attention
Figure 7: Ablation neural architecture: Attention among the overlapping and new operations. The architecture follows Fig. 2 but introduces an additional cross attention among the overlapping and new operations before output the predicted probability for each overlapping operation.
Table 17: Comparison of the learning architecture in Fig. and the attention-based learning archi- tecture in Fig. 7 on the hold out validation set for the 600 operations setting (10, 20, 30) in Table [
Accuracy
TPR
TNR
Precision
Recall
Time
Makespan
No Attention
0.77
0.81
0.67
0.86
0.81
126
1513
Attention
(K& V: New Ops.)
0.76
0.77
0.74
0.88
0.77
170 + 18
1504
Attention
(K&V: Overlapping Ops.)
0.75
0.75
0.75
0.88
0.75
179 +
1507
Attention
(K&V: Overlapping and New Ops.)
0.76
0.76
0.74
0.88
0.76
133 +: 14
1527 +: 68
36

---

Published as a conference paper at ICLR 2025
New Op vilee
Von Coertto
New (ecvire
(a) Only the new operations as keys K and values V.
Ove Tage
Ore
Overappin Operations
Ovedapping Operations
Operabors
0.10 61
(b) Only the overlapping operations as keys K and values V.
1.0
201
33
35
32
12
20
50
20
20
35
Orertggitg Opestton
22
Cowcapping
Duwcapeing
0.5
0.10
0.15
0.25
(c) Both overlapping and new operations as keys K and values V.
Figure 8: Comparison of Learned Attention Maps. set the overlapping operations as the query Q (the rows) and consider three different types of keys K and values V (the columns).
37

---

Published as a conference paper at ICLR 2025
A.6.4 PERFORMANCE COMPARISON WITH DRL UNDER THE SAME NUMBER OF FJSP TRAINING INSTANCE.
In Table 18 we compare L-RHO with DRL Wang et al. 2023a when training on the same set of 450 FJSP instances. We observe that DRL's performance degrades with 450 training instances, especially at larger scales, highlighting L-RHO's unique advantage with lighter training set. This can be beneficial under situations where FISP training instances are harder to acquire.
Table 18: Compare I-RHO with DLR Wang et al. 2023a) under the same number of FJSP training instances (DRL-450).
600 (10, 20, 30)
800 (10, 20, 10)
1200 (10, 20, 60)
2000 (10. 20. 100), Transfer
Time (8)
Makespan
Time (5)
Makesspan
Time (S)
Millespnn
Time (4)
Milesspnn J
CP-SAT
1800
2274
1800
4017 1: 413
1800
10825 +: 1013
1800
39585
2707
1800
DRL-4500 Greedy
4. 0.04
1635 1:
6 0.04
2178 85
1:
3307 1: 115
0.5
5415 1. 134
DRL-4500 Sample 100
30
1563 1: 62
48
2093 1. 70
111 1.3
3237 91
301 1.8
5341 1: 108
DRL- Sample 500
143 =
1546 +: 50
261 8
2070 +: 68
610 d:
3210 94
1751 +: 30
5311 +: 111
DRI-2UK, Greedy
4 0.02
1628
0.04
2128 1. M0
3141 9:97
5184 114
DRI- Sampie
0.3 146
1551
DRL-20K, Sample 500
1537 61
261 1
2031 68
597 16
3015 1.
1738 16
5062 98
Default RHO
244 1. 21
1558 1. 73
348 = 26
2103 1. 78
515 36
3136 91
862 42
$207 1. 114
Warm Start RHO
203 23
1521 1: 67
278 22
2055 1. 75
420
3081
716 4:
5057 1: 106
L-RHO (450)
126
1513
23
2015
259 1.37
3011
5:5.1.52
4982 132
A.6.5 PERFORMANCE OF DEFAULT RHO WITH LONGER TIME LIMITS
parameters control the time limit per RHO subproblem: 1) total time limit, where solving terminates if the time exceeds T' seconds; 2) early stop time, where solving terminates early if the objective does not improve within Te, seconds. In Table ??, we evaluate the default RHO with increased T and Tes. The results show that, as the time limit increases by over 10x, the default RHO achieves better objectives than our L-RHO, albeit with prohibitively long runtime. Our L--HO delivers superior performance under practical time constraints, offering benefits especially in online cases.
As described in Appendix [A.5.4
Table 19: Comparison of Default RHO's performance across different time limit parameters and Te, for RHO.
(10, 20, 30)
800 (10, 20, 40)
1200 (10, 20, 60)
T. T..
Time (s)
Makespan
Time
Makespan
Time (s)
Makespan
60, (reported)
244 = 21
1558
348 + 26
2103
545 + 36
3136 + 91
60,
599.1
728 1: 98
2044
1109 + 108
3002 1: 87
60. 30
923 - 71
1502 1
1099 + 130
2028
1697 = 175
2963 + 78
60, 60
819 117
1494 67
1096 + 156
2018 71
1714 = 154
2968 + 89
120, 60
1476 - 312
1497 1: 70
1811 1: 241
1997
70
2809 1: 308
2932 1 75
180, 120
2142 - 461
1490 70
2509 + 346
1994 + 76
3932 + 590
2924
1 83
360, 180
3631 1 816
1476
1: 64
3673 1 797
1987
1 68
5663 1: 900
2924
1 86
L-RI1
126 1 19
1513
2015
259 1 37
3011
106
38

---

Published as a conference paper at ICLR 2025
H-S
55
=[ri]] = 0.50 0.36
6(0ty) = 0.45(11-S) 0.35
Elr = 0.60(11-S) 0.27
0.8
Empriical
Empirical
Empriical
PM/0 0.85 0.7
Pi 0.80 0.7kp
0.8
PE 0.87 2.55
0.6
0.6
0.4
0.4
0.2
0.2
0.4
10
30 Operation O
20
Operation OHI
Operation O
(a) (25, 25, 24) Start Delay
(b) (30, 30, 24) Start Delay
(c) (30, 30, 24) Start + End Delay
H 0.27 [[0;]] -- 0.400H-5)--0001
H-S
60
[[n - (.41())))))))-1--)0 0.32
<[n - 0.447(H-) - D.33
0..8
Emprncal
Empricel Date 0.74 205..
Empincal Data
2200 0.76 0.76-0.55. 0.55,'s
PL 0.74 0.54,
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
10
20
40
50
10
30
40
10
20
30
60
Operation O
Operation Off
Operation Of!
(d) (30,30, 24) Start and End De-
(e) (35, 30) Start Delay
(f) (10, 40, 40) Start Delay
lay & Ohservation Noise
Figure 9: The empirical Pi (i) distribution across a variety of FJSP settings. We plot the empirical distribution calculated by Eq. equation [5] with the solid green curve, and the fitted linear approximation pi (i) b m म'S with the dashed red line. We also plot the empirical standard error (the shaded green area) computed across all RHO iterations, with Nater ranging from 20 to 75 (based on the FJSP problem size). We observe a consistent linear decreasing trend across all FJSP distributions, and the low standard errors further indicate consistency across RHO iterations.
with
A.7 DETAILED THEORETICAL PROBABILISTIC ANALYSIS
Following the main paper. we analyze a generic subproblem P, == P at each RHO iteration r. For ease of notation, we omit the r subscript for the rest of this section when it is clear from the context.
A.7.1 DETAILS OF ALL CONSIDERED RHO METHODS
We consider set of assignment- based RHO warm start procedure, where we follow the RHO test procedure in Fig. [b), bottom but obtain O Oziz at each RHO iteration with different methods de- scribed as follows. For tractability analysis, we consider the same RHO window size H and step size S, which results in H S overlapping operations (Ooeettapl = H - S in consecutive RHO iterations.
Osr is obtained by selecting each operation in Owveriap with probability on uniformly at random.
Random oR:
Ofts is obtained as the first oF fraction of operations in Oonerlap with the earliest RHO sequence order (determined by release time for delay-based objectives or operation precedence for makespan). Notably, Random/First
First op:
exactly matches the default RHO procedure.
L-RHO (Ours): Ozi is predicted by the learning model fo as described in Sec. (Fig. I (b)
bottom).
Oracle: the look- ahead Oracle with Ojte. which is empirically obtained by applying the same
procedure as in Fig. 1 (b) top but only includes the solve time of the restricted subproblem f As illustrated in Fig. (Teft), we analyze the performance of each method (Random, First, L-RHO) based on the closeness of Ofiz to the Oracle 0/..-
39

---

Published as a conference paper at ICLR 2025
A.7.2 EMPIRICAL VALIDATION OF THE LINEAR DECAY ASSUMPTION FOR Pfin
We compute the distribution of pr (t) using the training set Ktroin Specifically, for each FISP training instance P and RHO iteration v, we have a training label with the form yf J where the index E {l..... H - -S} of cach operations O6)) follows the RHO (V P.rt
sequence order, and the associated Oj Jis. {O()) E O Ovverlapy Yoc 1}. For each RHO iteration r, we calculate the empirical
1 NP
Σ
P.re Yol
Pfzzr
FISP
where Np is the number of training instances, from which we obtain the empirical distribution averaged across all RHO iterations and the associated standard error
cmmp (i) = Nater RHO itemttion r
Σ
temp (i);
Pft
Pfter
(15)
S.e.(yfie semp (i)) s.L.(( {p)
pompp() RHO ieeration r) // N Meer
fix,r
where Nater is the number of RHO iterations. In Fig we visualize the empirical Pfiz (() butions (and the associated two standard errors) across variety of FISP settings, under the Oracle's best RHO parameter setting from grid search (H = 80, S = 25 for most settings). We also plot the linear approximation ( H-S
(om distri-
m H-8 through fitting the empirical distribution, resulting in E E Pice (1) E E H-5
m (H S) m
2
Observations from the Pise distribution in Fig. 9 We observe consistent linear decreasing trend across all distributions, with varying slopes and intercepts. The empirical distribution closely aligns with our fitted linear approximation, hence validating our Assump. [ the low standard error further reflects the consistency across RHO iterations. Intuitively, this is because the new operations O in the current RHO subproblem P are closer in the precedence order release time with the later overlapping operations in O Overltap, making them more likely to be scheduled around similar time and thus have more effect on each other's solution.
Moreover, E [mnja jiz. is around 0.5( H S) for all settings, with a higher B(n in (c) for (30, 30, 24) with Start and End Delay, but lower B for larger FJSP sizes (35, 35, 30) and (40, 40, 40) in (c) and (f). We have the following noteworthy comparisons:
1. Comparing FJSP (30, 30, 24) (c) Start and End Delay and (b) Start Delay, our analysi sis indicates that the larger number of Oracle fixed operations (high Be in (c) enhances the performance of the Random and First heuristics (reducing performance gap relative to Default RHO) com- pared with (b). This aligns with our empirically observation when comparing (i) and (ii) of Fig (Right).
2. Comparing FJSP (30, 30, 24) (d) Start and End Delay Observation Noise with (c), our anal- ysis indicates a performance decline of Random and First under observation noise, as (d) has significantly lower [ than (c). This is consistent with our empirical observation when comparing (iii) and (ii) in Fig 3 (Right). Moreover, comparing (d) with (b), we see that (d) has similar Ein r but notably lower slope m than (b). Our analysis indicates that this reduces the performance advantage of First over Random, which is reflected by our empirical comparison of (iii) and (i) in Fig. (Rghht)
A.7.3 DERIVATIONS OF E(n AND E f(n FOR EACH METHOD
Proposition 1. The closed-form of T[nnpp and E(( for Random a First o and L-RHO can be found in Table 20 for a general P'aa (i) and a linearly decreasing (i) distribution (Assump. 7 Furthermore, ignoring an 7 term in E(ri) [ for ease of exposition, The FPR and FNR of First OF
and Random on are (0F,3r) m
f= mar)
or(b wor) and (ORR, 3n) = (an, -R).
40

---

Published as a conference paper at ICLR 2025
Table 20: Closed-form expressions of [o and E[n for Default, Random, First, and the learn- ing method L-RHO with False Positive and Negative Rates (),
Random oR
First
L-RHO (a,
General (fzx
Bluypl
E (1 -PPP(
Σ (1 (()
1 p(a
1
IsiSor 5)
Blyys]
(1 - σR) Σ p)((0)
Σ
Piial()
Σ pho(()
1515N-8
"r 5)11sisH-
Linear Decreasing P7.0 (6)
m mx=3
B|aypl
Øn|(1 - 5- 7) 9) T1
ar - b+ Bor) +)++
a(l1 - b- 3 9)+
[[jas]]
(1 0x]((0- 7) 5) W]
(1-ap)[1 7
8ibb IH
Equivalently, Given Bln Pi (2 T
B|uypl
au( - S ((H---BBnja) Blujaa))
or (H-S-- -innja) 7 [-(1,))1:
-
a (H - S- Binjal)
B]pya]
(1 11-apa Bn]jj
(1- - Tox(H 5)
Proof. See Appendix A.7.5 for the detailed derivation of Table 20 Since have B[m E,Pri (i) (b m [H 5) 7. we can substitute the corresponding terms in the table with Eln and arrive at the last equivalent closed-forms as in the main paper Prop. !
Ignoring the m [p(n E (m.) to the FP and FN rates (a, ()) involves scaling the axes by S E(n (1 b +++ m (H - S) and E/n = (b - (H - 5), respectively, from which we obtain the FPR and FNR for First OF and Random RR For example.
2 E [0, 1] term in jin the coordinate transformation from the FP and FN errors
E f
(1 (b m -F 8)
m m OF
bo m2 OF
m 2
8r =
E n
(b 2 [ S)
b
m 2
b
or(b 00F) b + 2 OF
m
m 2
A.7.4 QUALITATIVE RELATIONSHIP BETWEEN (E(m)pp AND E((nn.) AND (ORJECTIVE, SOLVE TIME)
Based on empirical observation and analytical insights, we interpret the effects of B[n and E[nss]] on the objective and solve time in the table below (and also in Fig. 4 left), where + and - reflects positive and negative correlations, respectively.
Objective
Solve Time
+ (small B(nypD
B nyyl
+
(large BB(r,)))
E[nya]
+
+
Specifically,
The objective is significantly affected by E[nsy], the number of operations with incorrectly fixed machine assignments. A higher E[n indicates fixing more sub-optimal decision variables in the restricted subproblem P,, and hence worsens the objective value (often exponentially, as observed in Appendix A.6 when a increases for Random First). Therefore, reducing E[n improves the objective.
41

---

Published as a conference paper at ICLR 2025
The solve time is heavily influenced by ffl the number of operations that have the same machine assignments but are failed to be identified. A higher E'n indicates a larger search space of the optimization subproblem Pr, hence increasing the solve time (often exponentially, as observed when decreases for Random / First). Hence, a lower E[nfal reduces the solve time.
Fp] has a mixed contribution to the solve time. On one hand, an increasing fpm reduces the size of the subproblem Pr, which could reduce the solve time; the other hand, an increasing E[n leads to more sub-optimal assignment fixing in P,, which potentially complicates the optimization landscapes and hence can increase the solve time, especially when [[ is small. Generally speaking, we observe that higher E[ngp] slightly increases the solve time in the low ppl regime (positive correlation) but reduces the solve time when E[myp] is close to (negative correlation). Specifically. Appendix A.6 we see that when E[[ is low, L-RHO typically solves faster than First d baselines with a similar E[n fu] but a higher [8] [n]p likewise, Oracle generally has similar solve time as First 80%, whose E[nyp] is much higher than Oracle.
improve the objective under given time limit, as the correctly restricted subproblem P, from a low E[nya]] can simplify the optimization landscape. This effect espe- cialy evident in the low E/mspp regime. where the baseline RHO methods often reach the time limit with suboptimal solution, whereas our L-RHO with a lower EE E[(ynl can often solve the subproblem P, optimally with shorter solve time.
Reducing F[
Therefore, to achieve objectives comparable to Default RHO while reducing the solve time, an ef- fective RHO method should first reduce E[ to mitigate objective degradation, and subsequently reduce E. n,), which can further reduces both solve time and objective in the small E|rt regime.
More Visualizations. We provide additional visualizations of different FISP variants in Fig. TO using the same plotting procedure as in Fig. 4 (Right). The (0 of L--HO selected as the False Positive and Negative Rates on the validation set Kval- Empirically, our L-RHO outperforms all baseline methods (Random, First, Default RHO) with a lower objective and has a similar solve time as First 60%; the pink regions in Fig. 10 illustrates the empirical dominance relationship of L-RHO over the respective First and Random baselines. Based on the above analysis, the effectiveness of our learning method L-RHO is due to its ability to simultaneously achieve a small [p] (which ensures low objective) and small F[nr=]] (which improves both the objective and solve time). In contrast, the hcuristic baselines Random or First trades-off E[[zn]] and E(n /pl by adjusting o, but cannot obtain low E [[n and [B(n pl at the same time.
42

---

Published as a conference paper at ICLR 2025
Rate
Rate
0
0.15
0.29
0.44
0.59
0.73
0.88
0
0.16
0.33
0.49
0.65
0.82
0.98
First
40%
12
First
40%
0.39
10
Random
0.36
Random
10
0.33
FP errot =(ne]
error =lnp]
Better
0.29
Better Time
0.26
40%
Time
Obj.
0.22
FP Rate
40%
ObJ
20%
0.20
0.14
0.13
2
L-RHO
20%
0.07
L-RHO
20%
0
0
16
20
20
FN error =[0m]
FN error [[Dm)
(a) (25, 25, 24) Start Delay
(b) (30, 30, 24)
Start Delay
Rate
Rate B
0
0.12 0.24 0.36 0.49 0.61 0.73 0.85 0.97
0.15
0.30
0.45
0.60
0.75
0.90
First
Random
40%
0.45
Random
FP error Elnel
Better
40%
0.36
error :10ml
40%
Detter
0.28
40%
Time
Obj.
0.27
C Rate
& Obj.
20%
0.21
L-RHO
20%
0.18
0.14
20%
2
20%
0.09
L-RHO
0.07
0
0
12
32
24
FN error E[mm]
FN error E[nm]
(c) (30, 30, 24) Start and End Delay
(d) (30, 30, 24) Start and End Delay & Obs. Noise
FN Rate
FN Rate $
0.18
0.35
0.53
0.70
0.88
0.17
0.35
0.52
0.70
0.87
First
40%
40%
1.2
0.37
12
0.37
Random
Random
eiror =((e))
10
0.31
error s[me]
10
0.31
40%
Better Time & Obj
40%
Better
FP Rate
Time & &.Obj
20%
0.19
20%
0.19
2
20%
0.12
20%
0.12
L-RHO
L-RHO
0
20
16
20
FN error F[0ml
FN error F[nml
(e) (35, 35, 30) Start Delay
(f) (40, 40, 40) Start Delay
Figure 10: For a variety of FJSP distributions, we depict E[nyn] and E [n of Random, First. and L-RHO in the low E[n region, using empirically validated pi (i) distribution from Fig. 9 and L-RHO FPR-FNR (a,, 8) on the validation set. The pink region illustrates the empirical dominating region where our L-RHO has a better solve time and objective than all the baseline methods in the region; in particular, L-RHO has better objective than all baseline methods, and better solve time for a large range of a values (up to First 50% 60%). as it can achieve low E[n and /m] simultaneously. Additionally, we can transform the coordinates to the FP and FN rates (a, 3). as depicted by the right and top axes, to provide insights on what FP and FN rates should L-RHO achieve for learning to be effective.
43

---

Published as a conference paper at ICLR 2025
A.7.5 DETAILED DERIVATION OF TABLE 20
Proof. (1) General Pizz (1) distribution.
. Random ont by independence from the i.i.d. random sampling procedure, we have
fp.
Random an) Jp.
Σ
Pr(operation O' E fonr and jjt,,)
1515H-8
Σ
Pr(operation 0 (1m,)) Prr000rr(00)))) E (irr))
1
Σ
on(1- - (fsx)),,
15
B
Random an) fur
Σ
Pr(operation O fuur and O (jrr)
1515H-8
Σ
Pr(operation 00 & (rnr))r(OO0)) E jiir)
1
Σ
(1 - 0m) (1),
15SSH-5
where the sum is over all overlapping operations in Ooverlap.r-
First o as it always selects the first o S) operations, we have
for
Σ
Pr(pperation (00) (ja,,)) Σ
(1 (1- (ia)),(()),
ISiSor(H-S)
18iSor(8-8)
B Fng
Σ
Pr(operation O Oj,r)) =
Σ
P)rr()),
(H
SYSiS(H
arlll SySIS(1 S)
where the sum is over the first k(H - 5) overlapping operations in O Ovverlap.r-
-L-HH (ax, (): Given the the relationship between FP, FN rates and FP, FN errors, we have Ein
a(l 5 - Elmfiz,)))
Σ a(1 (f).
1sIsH
LRRHO Juur
Σ
8 (i).
ISiSH-S
(2) Linearly decreasing Pjiz (1) - m 5-
We have 1 - P]ic (1) = = (1- 111-b) b) +m H-
and we first compute the following quantities
Σ
i
14 11 S
Σ
i
OF o o S)
H S
2
H
2
ISSST- 8
ISiSoF (H- -H-8)
Σ
i
Σ
Σ
i
(1- + +(1 (1
H-S
H
H-S
2
((
Isi (I-
Σ (1)=
Σ
m H
(b
m
(H S) m
1SiSH-S
15iSH-5
Σ
(1) = Σ
b m
0r
T
Or - S) or m
ISiSo
Σ
(1) (1 (b
m
OF H 5) (1 OF) m
2
#n(H 8)4155H(
Σ
(1 (1- (I-P)(c(i))= = Σ
(1 + m
i
(1 - b+
= (H - 9) + m
m
H-S
2
2
IsiS(I- S)
Σ (1 -1- (i]((())))
Σ
(1- +m 1- S dF (1 b aF (H S) + o m
(8-S
(H
We hence have
44

---

Published as a conference paper at ICLR 2025
Random Øx:
E F[
Σ
IR(1 - -Pfin = 0R(1 - -b+
m
2 [ 5) + 2 m
1
E E[nfa]
Σ
(1
on) (1) (1 oz)(
m
(H 5) (1 on))
2
1
First oet
Bin
First Fo
Σ
(1 (fjr oF -b ア oF
) [H - S) + oF m
2
(H-S
B m or
Σ
= (1-)))
2 - - S) - 00 -1-0f) m
m
m
JF)
(((H-S)+1S((HH-3)
L-RHO (a, 3):
E fp.r
L.RIO1
Σ
a(1 - (Tz(1)) = a(1 - b+ m
2 [H S) + +
ISiSH
B|n Bin
Σ
8 P (1) B(b
m
マ ) S) - 3
1
A.7.6 INTERPRETATION OF PROP. 1
We obtain the following insights by interpreting Prop.
1. The Fi (i) distribution determines the strength of the Random and First baselines and thus the potential for improvement by learning methods. Specifically, E governs the performance of Random: when E[n]iel
0.5, Random suffers from either high FP error or high FN error fiz = 0 (or 1), then Random on 0 (or 100%) can simultaneously achieve zero FP and FN errors. Moreover, the magnitude of the slope indicates how much First can improve over Random, with a larger m leading to greater improvement (Fig. 4 (middle)).
across all n, but when fiz
2.
The qualitative relationship between the FP FN errors and objective & solve time illustrated in Fig. (left) and further elaborated in Appendix [A.7.4] Specifically, the FP error represents sub-optimal assignments incorrectly fixed in P. which harms the objective, whereas the FN error corresponds (near)-optimal assignments failed be fixed in P. which negatively impacts both metrics (solve time and objective) when time limit is imposed. Thus, effective RHO methods should maintain low FP error for competitive objective and low FN error to further improve both metrics; this is indeed achieved by our L-RHO, as evident in Fig. (right).
3. We can further convert the FP and FN errors (E y (p), E[n (n)) into the FP and FN rates (ax, B). shown by the right and top axes in Fig. 4 (right). In this case, aF and 3p in Prop. I can interpreted as the FPR and FNR that L-RHO's s learned model should achieve to match the performance of First ap. This provides valuable estimate identify what (a,, should we aim for when training L-RHO and to assess the effectiveness of the learned model before deployment.
45


Reviews:
[{"review_id": "DPyxTg85M0", "reviewer": "Reviewer_S42P", "summary": "The paper proposes a learning-augmented approach for the Flexible Job Shop Scheduling Problem (FJSP) with a long horizon. The authors consider rolling horizon optimization (RHO) where overlapping ordered subproblems are solved sequentially. The idea is to predict which decisions should remain unchanged from one subproblem to the next in order to restrict the subproblem sizes. This may have two impacts: it can accelerate the solving and/or for a fixed time budget per subproblem, improve the quality of the solutions. More precisely, the paper proposes to learn a model which predicts which of the overlapping operations should keep their previous machine assignment. The model is trained in a supervised way where the ground truth is provided by performing RHO and extracting the operations with unchanged assignments. The approach is evaluated on several variants of the FSSP, with varying objectives, distributions and additionnal noise.", "questions": "* The paper considers several settings as first steps towards the online setting. Why not consider the purely online setting? What kind of adaptations would be needed?\n* What's the impact of the time budget per subproblem on the final performance? I imagine if the budget is large enough, standard RHO would lead to the best solutions.\n\nRemarks:\n* CP-SAT being exact solver, it would be interesting to have the optimal value as a reference to assess the quality of the other methods. Clearly restricting it to 1800 sec is not eniugh to get high qulity solutions esp for |O|=2000 in Table 1.\n* \"Enhancing the efficiency and scalability of Combinatorial Optimization Problems (COPs) has been a central focus..\" --> missing \"solving\" or \"methods\" or such.\nL151: \"Each sub-problem is limited to T seconds\". We understand later that T is the solving time, but It would be nice to make it explicit already here.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper makes an original contribution by introducing learning in RHO for the FJSP\n* The paper manages to solve much longer horizon problems than existing methods\n* In-depth analysis of the performance of the proposed approach in various settings\n* The paper is generally clear and well organized.", "weaknesses": "* The main weakness is the focus on the FJSP which limits its scope. The idea seems quite generic, so illustrating it on more long-horizon CO problems, e.g. other scheduling variants, would strengthen the contributions and broaden the scope.\n\n* In the theoretical analysis (Sec 6), while the intuition that \"the more irregular the operations to be fixed (O∗ fix), the more advantageous LRHO can be, because of the greater potential gain from prediction\" is clear, I did not understand how proposition 1 was proving this point. I found the technical part difficult to follow.\n\n* In the experiments, I found that the comparison to DRL-450 is not so informative. While the learning task of proposed L-RHO is a classification on the subproblems, so 450x[the number of supbroblems per instance] samples seem a reasonable training set size, the \"DRL\" baseline is  an end-to-end constructive method, and it makes sense that its training requires more data than 450 instances.", "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": "BPr0TSTtGR", "reviewer": "Reviewer_qP8G", "summary": "This paper proposes L-RHO, a rolling horizon optimization algorithm designed for the flexible job-shop scheduling problem (FJSP) that leverages learning to select overlapping variables in subproblems. As the first study to guide the RHO algorithm with a learning-based approach, L-RHO demonstrated performance improvements across diverse FJSP settings.", "questions": "1. Could the learning guide proposed in this study potentially be adapted for use in other algorithms beyond RHO?\n2. Would the ideas proposed in this paper be adaptable for subproblem decomposition in various types of long-horizon combinatorial optimization problems?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper is noteworthy as an initial study that guides the decomposition process of subproblems in the RHO algorithm using a learning-based neural network. It also stands out for conducting comprehensive experiments and analyses across diverse FJSP settings.", "weaknesses": "The specific details about making RHO learnable are mostly presented in the supplementary material rather than the main sections, making it challenging to fully grasp the proposed learning framework. Given the extensive content of the paper, focusing more on the learning aspects in the main text would improve clarity and comprehension. Additionally, it is somewhat disappointing that in Table 1, the performance of L-RHO is not markedly superior to other baseline comparisons.", "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": "uuoGkRuHFq", "reviewer": "Reviewer_ppet", "summary": "Rolling horizon optimization (RHO) [1] is a widely used approach for tackling long-horizon production planning problems in stochastic environments. RHO solves these problems by breaking them into overlapping, shorter-horizon subproblems that roll forward over time. This overlap ensures continuity between consecutive subproblems.\n\nThis paper proposes a machine learning framework to identify decision variables that should be predetermined based on the prior horizons, allowing them to be treated as fixed for the current horizon. This helps to reduce the size of the optimization problem for each horizon.\nExperimental results show the proposed approach is not only fast but also result in better solutions.\n\n\n1: Sethi, Suresh, and Gerhard Sorger. \"A theory of rolling horizon decision making.\" Annals of Operations Research 29.1 (1991): 387-415.", "questions": "- Can you provide intuitive explanation of $q^\\star$ (line 219)? Is it the assignment which has most number of overlapping assignments? What is the significance of this? I do not get the motivation for setting $y_O^\\star = y_O^{q^\\star}$​. Could you provide some insight/intuition into the reasoning behind this? \n- What does $w_{pos}$ represent? \n- Can you comment on what features turn out to be important in identifying decision variables that should be fixed?\n- When increasing the congestion level (line 424), did you train a new model or use the one trained with low congestion?\n- Have you explored the attention map? Is it possible draw a significant conclusion form that? For example, an operation is more likely to be fixed if a machine has been running for a long time!\n- It is mentioned in the text that the operations are divided into subproblems of fixed duration T. How did you predetermine the value of T in your experiments? Should not it depend on the execution time of the operations?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "**Significance**: This paper studies an important problem relevant in many production planning operations. The proposed approach seem to surpass the state of the art, a significant contribution.\n\n**Originality**: I am not entirely familiar with the relevant literature. I searched articles published in the last five years. This work seems to take a novel direction to tackle the RHO problem.\n\n**Quality**: Quality of the paper is good as it covers both theoretical and empirical analysis. \n\n**Clarity**: The overall objective and methodology of the paper are easy to understand at a high level. However, some of the introduced notations are difficult to follow, and the intuitive explanations provided are sometimes lacking\n(See weakness).", "weaknesses": "- $m$ is used to denote a machine $m \\in M$ as well as an assignment $m: O \\rightarrow M$ (line 133 and 134).\n\n- How can default RHO be suboptimal compared to proposed L-RHO? If I  understood correctly, default RHO solves the true problem till optimality, hence it might be computation-intensive but should have the best performance. Is it due to the fact that all algorithms have been run with a timelimit? If that's the case, can default RHO perfrom better than L-RHO if both are allowed to run for more amount of runtime?\n\n-  It seems that the accuracy, precision, and recall of the classifier were not reported. I expect these metrics to be high for the model to demonstrate good performance. I would recommend to report this in the paper to provide a clearer picture of the ML model's performance.", "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": "kEwHTx7pNi", "reviewer": "Reviewer_PSPu", "summary": "This paper presents L-RHO, the first learning-guided Rolling Horizon Optimization (RHO) framework for long-horizon FJSP.  Empirically, this paper shows that L-RHO accelerates RHO by up to 54% while showing significantly improved solution quality, enabling it to outperform other heuristic and learning-based baselines.", "questions": "1. Look-ahead oracle is unclear. An introduction and framework should be added, probably in appendix. \n2. What is the value of the weight (W_pos) of loss function?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This paper claims to be the first learning-based framework to guide RHO for long-horizon Combinatorial Optimization Problems (COP).\n2. In their experiments, L-RHO reduces RHO solve times by up to 54% and improves solution quality by up to 21% compared to various heuristic and learning-based baselines, across a range of FJSP settings and distributions.\n3. Test on large instances, which operations are over 600, much larger than previous benchmarks.", "weaknesses": "**The novelty for learning-based RHO is limited.** L-RHO is very similar to RHO except for the customized attention based model. When compared to RHO, the experiment results (in Table 1) show only a slight improvement (less than 3% in Table 1 and also for the issue of large operations mentioned in the next item).\n\n**The experiments are unconvincing.**\n1. First, more comparisons to others are expected. For example, [1] and [2]. \n2. Second, although it seems impressive to perform well for “long-horizon” FJSP (e.g., 2000 operations in Table 1), unfortunately it is commonly agreed in this area that the more operations, the better performance. For example, in [3], the performance is nearly the optimal for large operations. \n\n[1] Echeverria, I., Murua, M., & Santana, R. (2023). Solving large flexible job shop scheduling instances by generating a diverse set of scheduling policies with deep reinforcement learning. arXiv preprint arXiv:2310.15706.\n\n[2] Han, B., & Yang, J. (2021). A deep reinforcement learning based solution for flexible job shop scheduling problem. International Journal of Simulation Modelling, 20(2), 375-386.\n\n[3] Ho, K. H., Cheng, J. Y., Wu, J. H., Chiang, F., Chen, Y. C., Wu, Y. Y., & Wu, I. C. (2024). Residual scheduling: A new reinforcement learning approach to solving job shop scheduling problem. IEEE Access.\n\n3. Third, from the above argument, it is also interesting and important to see the performances for some traditional benchmarks, such as those mentioned in line 289 (Wang et al., 2023a; Behnke and Geiger, 2012; Dauzere-P ` er´ es and Paulli ` , 1997; Hurink et al., 1994; Brandimarte, 1993). \n4. Fourth, for CP-SAT or GA, as the problem size increases, the required time for CP-SAT and GA apparently grows a lot. It seems meaningless to compare these methods with 1800 second computation.\n\n**Unclear theoretical analysis** \nIn the section of theoretical analysis, the authors present notations and formulas of “Assump 1.” and “Prop.1” without interpretation. Some are not defined, such as $n_{fn}$, $n_{pn}$, $n_{fix}$, etc. Note that they leave partial interpretation to Appendix A.5, which readers are not obligated to read. In the main text, it still needs to be self-contained.\n\n**Minor comments.**\n1. Symbol is inconsistent: \\Tau in Section 3 (e.g.: line 130) and 5 (e.g.: line 267) means jobs set, but in Section 4 (e.g.: line 235), it means machines.\n2. Figure 4 should be presented in the main text. \n3. About \"Machine/Operation Concatenation\" (In Section LEARNING-GUIDED ROLLING HORIZON OPTIMIZATION), it needs to add \" For each new operation that does not have a machine assignment, the concatenated machine feature is a dummy all-zero feature \", as mentioned in Appendix.", "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)