Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling

[Unclear Theoretical Analysis]

Sorry for the confusion. Additional discussions on the theoretical analysis were originally included in the appendix due to space constraint. We agree that the main paper should clearly illustrate the findings. Therefore, we have followed the suggestions and updated the main text to improve the clarity of the theoretical analysis. We also note that in the updated paper, the False Positive and Negative Errors, $n_{fp}$ and $n_{fn}$, are defined in the notation section.

Specifically, we provide expanded interpretations of the analysis, including:

• At the beginning of the section, we introduce the high level idea of comparing different RHO variants by analyzing their False Positive (FP) and Negative (FN) Errors. We also explain the effect of FP and FN on the solve time and objective.
• Before Assumption 1, we explain the intuition of the linear decay assumption, which is used in Prop. 1.
• At the end of the section, we interpret Prop. 1 and provide the following insights from the analysis: (i) the performance of the RHO heuristics (Random and First) is affected by the Oracle distribution $p^*_{fix}$, (ii) The linear decay’s strength further affects how much the First RHO can improve from Random RHO, and (iii) the theory further reveals the FP and FN rates that L-RHO needs to achieve to outperform the RHO baselines.

[Look-Ahead Oracle (Q1)]

Thank you for the suggestion! We have provided more details in Appendix Table 4: see $O^*_{fix, r}$ under operation subset and Oracle under Methods.

[Value of Weight W_pos (Q2)]

We set $w_{pos} = 0.5$ in our experiments, as noted in Table 11 of the Appendix. A lower $w_{pos}$ prioritizes avoiding False Positives, where the learned model incorrectly fixes operations with changing assignments. The lowered $w_{pos}$ can improve the objective but may increase solve time, as explained in our analysis.

For the rest of your minor comments, we have carefully followed your suggestions and revised the submission accordingly. We hope our detailed responses, along with the extensive new results and new comparisons, address your concerns!

[Regarding “the more operations, the better performance”]

The reviewer commented that -

…, 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.

We believe there may be a misunderstanding and kindly ask the reviewer to clarify this point. Large-scale FJSP introduces significant complexity to problem-solving, as larger COPs lead to exponentially larger action spaces, making them more challenging than small-scale COPs. Moreover, we note that in [3], the majority of experiments focus on Job Shop Scheduling (without machine assignment) rather than FJSP stuided in this paper. For the more challenging FJSP, where machine assignment adds considerable complexity, they do not address large-scale scenarios, with their largest benchmark being only 200 operations (10, 20, 10)—significantly smaller than our setting of 600–2000 operations.

We further examined [3] in details, and find the performance gap in the paper is defined with respect to running OR-Tools for half a day (which is not optimal solution). When the problem scale increases, OR-Tools’ performance becomes significantly worse, making the “performance gap” smaller; however, this does not mean the performance is close to optimal as the comparison is not with respect to the optimal solution — as seen in the updated paper, we run OR-Tools for 10 hours in each setting, and we find OR-Tools’ performance significantly worse than RHO based methods.

[Performance on Benchmark Instances]

Thank you for the suggestion! We find most of the traditional benchmarks on small scale (< 500 operations). We thus benchmark the performance on Dauzere-Peres and Paulli, 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. We further randomly sample with replacement $\times k$ operations for each job, with $k=3,6,9$ to mimic large scale settings with more operations: that is, if a job has 20 operations before, for $k=3$ we sample with replacement 60 operations within this set, where each operation maintains the same compatible machine and duration set as in the original dataset.

We compare L-RHO with DRL-20K, the state-of-the-art deep learning method that we compare with in the submitted paper, and provide the performance comparison in the table below. For both methods, we directly transfer the model learned on 600 operations (10, 20, 30) setting to the real world instances. The best known solution for the Dauzere original setting has an average makespan of 2120.

Our L-RHO outperforms DRL-20K 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 settings. 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 is an interesting future work is to train the model on a diverse set of distribution to further improve L-RHO’s transfer learning performance.

We thank the reviewer for recognizing our L-RHO as the first learning-based framework for long-horizon COP with significantly more operations than previous benchmarks. We understand that the main concerns are regarding additional experiments and the significance of the performance. We hope our response below will clarify any misunderstandings and concerns about our work.

[Novelty and Significance of L-RHO]

We would like to first clarify that our main contribution is not about the neural network design, but the idea that by learning which overlapping solutions in consecutive RHO iterations do not need to be re-optimized, our method substantially reduces RHO subproblem sizes and thus accelerates their solve time. That is, we are the first to introduce learning to RHO, and we find the combined algorithm highly effective for solving long-horizon COPs such as the exemplar FJSP. Your comment prompted us to revise and clarify our contributions (General Response 1/4), so we are grateful for that.

We kindly refer the reviewer to our responses [Restating our contributions and impact] [Significance of L-RHO Results] in the general response above for further discussion. Regarding the significance of the performance gains, we highlight the following points:

1. L-RHO significantly accelerate the default RHO by 35-54% while enhancing its performance by 3-21%.
2. L-RHO consistently delivers state-of-the-art results across diverse scheduling variants.
3. L-RHO outperforms DRL baselines with less information and broader applicability.
4. L-RHO excels in its simplicity and effectiveness, outperforming numerous complex baselines across a range of practical FJSP variations.
5. L-RHO can have real-world impact. As discussed in the general response, L-RHO achieves a 2.7% gap lower than the DRL baseline on real-world instances. While the number may look small, performance improvements that approach optimality are indeed challenging. As such, a 2.7% performance improvement is significant, and is typical for novel research in this area. In addition, such 2.7% improvement can translate in practice to a 2.7% revenue increase—an enormous benefit for companies managing billion-dollar operations.

[More Comparisons to Other Baselines]

Thank you for suggesting other DRL baselines to compare! Following your suggestions, we compare with the two suggested baselines [1] and [3] since we are not able to find the source code for [2]. We both directly load [1] and [3]’s checkpoint to evaluate the performance and retrain the model with the provided source code (see the table below)*. Unfortunately, we find [1] and [3]’s performance significantly worse than the DRL method that we benchmark in the original paper. We note that [1]’s greedy solve time is not as competitive as other DRL methods as it trains a suite of ensemble models and take the best one as the final result.

* We note that, when we tried to retrain the model in [1] and [3], we find that the training is very inefficient . For example, Echeverria et al.’s code uses Bayesian Optimization to train multiple models and select a subset of models for testing based on performance dominance; [3] uses a heuristic dispatch rule as the RL baseline, and the time for computing the RL baseline substantially increases for longer-horizon instances. In the paper of [1] and [3], they only learn on much smaller FJSP instances (up to 200 operations) with a large number of episodes (>100K). However, we find that, when training on our FJSP distributions, training for 800-1000 episodes (the retrained setting we use) already takes 1.5-2 days. This makes the implementation of [1]-[3] not suitable for learning on longer-horizon FJSP instances.

[1] Solving large flexible job shop scheduling instances by generating a diverse set of scheduling policies with deep reinforcement learning (arXiv 2023)

[2] A deep reinforcement learning based solution for flexible job shop scheduling problem. International Journal of Simulation Modelling (IJSIMM, 2021)

[3] Residual scheduling: A new reinforcement learning approach to solving job shop scheduling problem (IEEE Access 2024)

[CP-SAT with Prolonged Runtime]

Following your suggestion, we have further updated the result table to include CP-SAT results with a prolonged runtime of 36,000 seconds (10 hours). Even under this generous time limit, CP-SAT performs worse than RHO-based methods. We would also like to emphasize that the comparison with CP-SAT and GA highlights the importance of decomposition-based methods in solving large-scale, long-horizon FJSPs. This further underscores the challenges of addressing long-horizon FJSPs with existing approaches and demonstrates the significant impact of our proposed L-RHO.

I am glad that authors addressed most of my concerns. In addition, the performance reaches sota, after comparing some more sota works. Therefore, I am happy to raise the score up to 8.

We appreciate the reviewer’s positive and valuable feedback! We are delighted that the reviewer recognizes our paper’s significant contributions and novel direction. We hope the following response addresses any remaining concerns on clarity.

[Notation $m$ (W1)]

Sorry for the confusion! We update the first notation to $\bar{m} \in \mathcal{M}_{j, k}^{\bar{m}}$.

[Timelimit in RHO (W2)]

Yes, it is due to the time limit that we impose on the RHO algorithm. With significantly longer (albeit prohibitively long) time limit, the default RHO can achieve a better objective. To address this comprehensively, we have followed the suggestion and included additional results as follows. As detailed in Appendix A5.4, two parameters control the time limit per subproblem: 1) total time limit, where solving terminates if the time exceeds $T$=60s; 2) early stop time, where solving terminates early if the objective does not improve within $T_{es}$=3s. In the table below, we evaluate the default RHO with increased $T$ and $T_{es}$. 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-RHO delivers superior performance under practical time constraints, offering benefits especially in online cases.

[Report More Metrics (W3)]

Thank you for the great suggestion! We have provided the accuracy, precision, and recall in Appendix A.6.2. We copy the results here for clarity.

[Intuitive explanation of $q^*$ and $y_O^* = y_O^{q^*}$ (Q1)]

Thank you for the question! Yes, it is the solution with most number of overlapping assignments. The intuition behind this choice is, typically, the solve time of the subproblem reduces when more operations are fixed. As we would like the learning method to reduce the solve time of Default RHO, this label seems to be a natural choice. One caveat is that, the solution quality (the objective value) may be tempered if too many operations are fixed incorrectly. In our experiments, we find that this choice of $q^*$ has decent solution quality and substantially reducing the subproblem solve time, and hence it is chosen by us.

[What is $w_{pos}$? (Q2)]

The weight $w_{pos}$ adjusts the balance between reducing False Positive and False Negative Rate in learning. Specifically, a lower $w_{pos}$ emphasizes avoiding predicting False Positives, i.e., cases where the learned model incorrectly fixes operations whose true assignments change. The lowered $w_{pos}$ can improve the objective but may increase the solve time, as pointed out in our analysis. We set $w_{pos} = 0.5$ in our experiments.

[Importance of the Features (Q3)]

Good question! Summarizing and interpreting the black-box neural model into white-box decision rules understandable by humans is indeed exciting yet non-trivial. Below, we provide some discussions to uncover some potential insights.

Our input features are divided into three groups (1) Problem Characteristics: Features for each operation that capture the problem's inherent characteristics, such as the operation’s order within the same job (the id), average durations across all potential assignments, release time to the system (for delay based objectives); (2) Previous Solution Information: Features for each overlapping operation, such as whether it is overlapping, its machine assignment, solution start time, and solution end time; (3) Machine Features: Features specific to each machine, such as the number of overlapping operations assigned to the machine in the previous solution, and the end time of the machine to process all those operations.

We find that the second group of the features currently is the most important - the network cannot learn if we disable this subset, whereas disabling the reset of the features leads to roughly 1%-2% accuracy reduction. This makes sense as decisions of fixing or not should be made based on the quality of the previous solution. Our preliminary exploration also seems to indicate that the features in the group are similarly important — we tried to train a model with only one feature out of this set enabled (and the rest masked to 0). In this case, we find that no single feature alone can successfully learn meaningful information. Given the limited time for the rebuttal, we will further explore this and include additional discussions in the final version.

[Explore the Attention Maps (Q4)]

We are really grateful for the reviewer’s question, which lead us to identify an implementation issue in the submitted paper that makes the weights of the attention layer converge to 0 (so only the residual connection is effective). Please refer to our general response (4/4) for more details. We have fixed the implementation issue and take great effort to compare the reported architecture and the architecture with attention. We refer the reviewer to Appendix A.6.3 for the detailed results and visualizations of the attention map.

[Setup for Different Congestion Levels]

We train a new model for each congestion level.

[How to choose value $T$]

We first note that the subproblem solve time T is different from and irrelevant to the scheduling start and end time for the FJSP. The operations are divided into subproblems of fixed size (H operations per subproblem), and we solve each subproblem with a solve time limit up to T seconds. As mentioned in Appendix A.5.4, we perform a parameter grid search to find the best parameter value.

[Zero-Shot Generalization to Real-World Benchmarks]

We also evaluated the zero-shot generalization of the model trained on synthetic data by testing it directly on real-world benchmarks [5] with varying problem sizes ($|M|, |T|, n$) and data distribution. This demonstrates L-RHO's ability to generalize by training on one FJSP setup and solving others. As mentioned in our general response 2/4 and in the newly added Table 15 (Appendix A.6.1), our L-RHO model trained on synthetic data with FJSP 600 (10, 20, 30) setup achieves a 2.7% lower gap than DRL-20K compared to the best-known solution in zero-shot generalization setup. It also delivers near-optimal performance in smaller settings, maintains its advantage in larger ones without fine-tuning, and accelerates Default RHO by 24%-38%, demonstrating its practical impact and the benefits of learning to enhance RHO.

Reference:

[5] An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. (Annals of Operations Research, 1997)

[Generalizability of L-RHO to Practical Applications]

We fully agree with the reviewer that FJSPs in real-world applications are highly nuanced. This recognition motivates our detailed study in Sec. 5.2, where we explore a broader range of FJSP variations, including different objectives (start/end delay), noisy observations, and machine breakdowns. These scenarios introduce new constraints, such as release times in start/end delay variants that require operations to be scheduled only after their release, and machine unavailability during breakdown periods. In these diverse settings, L-RHO consistently outperforms baseline methods, achieving significant speedups over Default RHO.

We believe learning-based approaches have significant potential to enhance RHO performance under real-world constraints. While solvers like CP-SAT are capable of handling practical constraints, they could face inefficiencies with non-standard variants, leading to longer solve times or suboptimal solutions within a fixed time limit. In these cases, learning to fix variables is particularly valuable, as it reduces problem size and simplifies subproblems for the solver. This advantage is evident in Table 2, where L-RHO achieves greater improvements in solve time and objectives for delay-based problems compared to makespan-based ones in Table 1, demonstrating its superior ability to accelerate RHO on more complex FJSP variants.

Additionally, our theoretical analysis in Sec. 6 provides valuable insights into when learning can effectively enhance RHO's performance, and it can be adopted to analyze the effectiveness of deploying L-RHO in practice. As this analysis applies broadly to general FJSP settings, we believe it can provide practitioners useful guidance on whether to leverage learning to address real-world scenarios.

We sincerely thank you for your valuable feedback in strengthening and supporting our work. We will further refine the paper based on our discussions here. Please feel free to follow up with any additional questions. We look forward to your further reply!

We appreciate the reviewer's valuable feedback! We are pleased that the reviewer finds our paper to be noteworthy with comprehensive experiments and analyses across diverse FJSP settings. We understand your main concern about performance significance and hope our response below addresses it clearly.

[Details of L-RHO]

Following your suggestion, we have carefully reorganized our paper to include more details of L-RHO in the main text. Specifically, we have moved the architecture figure to the main paper (Figure 2 in the updated version) to complement the high-level concept illustrated in Figure 1, which explains how we aim to learn which operations retain the same assignments across subsequent RHO subproblems. Other critical details about the learning process—such as training data collection, input feature summaries, the loss function, and inference steps—have already be included in the main paper. The Appendix primarily serves as a resource for completeness, providing step-by-step RHO pseudocode, implementation details for FJSP and L-RHO on varies settings to facilitate algorithm re-implementation, as well as additional experiments and theoretical proofs. We believe the updated main paper covers all critical information. However, if you have specific suggestions on areas to emphasize further, we would be happy to incorporate them. Additionally, our code will be made publicly available, and can also be found in the supplementary materials.

[Significance of L-RHO Results]

Our L-RHO achieves state-of-the-art performance, outperforming various traditional and learning-based baselines both with and without decomposition in various challenging settings. This is significant for the following reasons:

1. L-RHO significantly accelerate the default RHO by 35-54% while enhancing its performance by 3-21%, as demonstrated in Tables 1 and 2. This represent a major advancement for long-horizon FJSP and we are the first to showcase this finding.
2. L-RHO consistently delivers state-of-the-art results across diverse scheduling variants. This is evidenced by Tables 1 and 2 and Figure 3, across different problem sizes, data distributions, objectives, under online observation noise and machine disruption.
3. L-RHO outperforms DRL baselines with less information and broader applicability. While the DRL baselines rely on complete problem information and is unsuitable for online problems, L-RHO operates effectively within a limited RHO window, achieving much better objectives with comparable or even shorter solve times.
4. L-RHO excels in its simplicity and effectiveness. Beyond merely competing on performance benchmarks, where algorithms in the literature are becoming increasingly complex, L-RHO stands out for its remarkable simplicity and effectiveness, outperforming numerous complex baselines across a range of pratical FJSP variations. 5.L-RHO can have real-world impact. L-RHO achieves a 2.7% gap lower than the DRL baseline on real-world instances. While the number may look small, performance improvements that approach optimality are indeed challenging. As such, a 2.7% performance improvement is significant, and is typical for novel research in this area [1, 2]. In addition, such 2.7% improvement can translate in practice to a 2.7% revenue increase—an enormous benefit for companies managing billion-dollar operations.

[1] Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problem (UAI 2024)

[2] Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling (ICLR 2024)

Note the above two papers only study Job Shop Scheduling (JSP, no machine assignments).

Moreover, we have added several new baselines, including two additional state-of-the-art DRL methods, in the revised paper and have tested our L-RHO on real-world benchmark instances. Kindly refer to [Updated Table 1 with More Baselines and Comparison] and [Performance of L-RHO on Real-World Benchmark Instances] for more results and discussions the general response above. In summary, L-RHO achieves a 2.7% gap lower than DRL-20K, when both are compared to the best known solution. Notably, our L-RHO achieves near-optimal performance in the smallest setting, and maintains its advantage in larger settings without any fine-tuning. It also significantly accelerates Default RHO by 24%-38%, highlighting the benefits of learning to enhance RHO and its practical impact on real-world deployment.

[Apply Learning to Guide Other Algorithms (Q1)]

Interesting question! Our learning method can be applied to guide other search-based algorithms, such as large neighborhood search (LNS). LNS begins with a complete solution and iteratively refines it by selecting and solving subproblems. In this context, the variables within a subproblem can be treated as “overlapping” variables. As the LNS iterations progress, an increasing number of these overlapping variables remain unchanged between consecutive iterations. Our learning method could be leveraged to identify and fix a subset of these variables, thereby accelerating the solution of LNS subproblems. Notably, learning-guided LNS for FJSP has not been explored before, making this an exciting and promising direction for future research.

[Apply L-RHO to Other COPs (Q2)].

Thank you for the question regarding the applicability of L-RHO to other long-horizon COPs! This suggestion prompted us to revise our contributions statement; as stated there (General Response 1/4), L-RHO can be applied to any long-horizon COP for which rolling-horizon optimization can be applied. However, we note that the effectiveness of such an approach may vary from application to application and is an important direction of future research. As such, the theoretical analysis in our paper complements our FJSP-focused evaluation to provide application-agnostic insights into when such an approach would be advantageous.

Within FJSP, we do demonstrate the effectiveness of L-RHO on a rich set of variants: we investigate multiple scheduling objectives, including makespan, start delay, and combined start-end delay, while considering addressing more complex scheduling variants including observation noise and dynamic scenarios like machine breakdowns. Our evaluation methodology is consistent with (or arguably richer than) learning-for-COP literature published in leading ML conferences, which for various reasons, including compute costs and benchmark availability, tend to focus on canonical problems within a COP class (e.g., routing [1-3] or scheduling [4-5]).

Beyond FJSP, we provide a few demonstrative examples on how one can apply L-RHO to other COPs. (1) In Multi-item Inventory Management, one needs to decide the quantity of inventory to hold over multiple periods. When solving this using a RHO framework, one can fix the quantity of a subset of items and only re-optimize the rest to improve the efficiency of the solving. (2) in Vehicle Routing with Time Windows, vehicles visit customers in increasing time order; as new customers come in, instead of re-optimizing the entire route, one can identify which segments of the route can stay the same and only re-optimize a partial segment. To apply L-RHO, the key is to identify fixing which variables in the overlapping subproblems, can be fixed, are amenable to learning, and can lead to a significant time improvement. Again, these extensions are valuable and interesting future directions.

[1] Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time (ICLR 2023)

[2] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization (NeurIPS 2023)

[3] Towards Omni-generalizable Neural Methods for Vehicle Routing Problems (ICML 2023)

[4] Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problem (UAI 2024)

[5] Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling (ICLR 2024)

We thank the reviewer for the opportunity to engage in further discussion and acknowledge the soundness of our L-RHO. We understand the key remaining concern is the perception that “the learning process provides indirect assistance rather than being directly utilized in solving the problem.” However, we believe this may stem from a misunderstanding of our method, or, generally, the role of the ML component in novel work.

1. Regarding indirect vs direct assistance in solving the problem, our understanding is that you may be referring to end-to-end ML methods as offering direct assistance. We take the perspective that end-to-end ML methods are only one type of ML method. Our work falls into a broader class of methods that utilize ML in one way or another. Here, we provide examples of prominent such works that provide “indirect assistance” that have made significant contribution to the field:

   • AlphaGo, where learning augments Monte Carlo Tree Search (MCTS) rather than replacing it in solving Go [1].
   • Hyperparameter optimization, using ML which assists optimization processes without directly solving them [2, 3].
   • The existing learning-guided combinatorial optimization literature, which represent a significant portion of NCO works hybridizing ML with traditional solvers to leverage the strengths of both. Examples include learning-guided local search [4-6], learning-guided ant colony algorithms [6], learning-guided dynamic/online VRPs [7], learning-guided branch and bound for Mixed Integer Linear Programming solvers [8-9], and learning-guided heuristic solvers like Neural LKH [10]. In all above novel and impactful works, learning predicts useful information that enhances traditional methods rather than providing an end-to-end solution.
   • Our L-RHO is a novel contribution within the above paradigm. To our knowledge, we are the first-of-its-kind learning-guided optimization framework for large-scale, long-horizon COPs.

2. At the same time, we clarify that we do consider the learning in our approach to be directly used utilized in solving the problem. Our neural network learns to predict a subset of variables to be fixed in both training and inference. This directly enhances CP-SAT solver by largely reducing the problem size, leading to significantly improved performance, accelerated runtime, and state-of-the-art performance across diverse data distributions and variants (see general response 2/4 [Significance of L-RHO Results]).

Please let us know if this clarifies the novelty of our work and if you have further questions or concerns. We look forward to your reply.

References

[1] Mastering the game of Go with deep neural networks and tree search (Nature 2016).

[2] How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design (STOC 2021)

[3] Learning to configure separators in branch-and-cut (NeurIPS 2023)

[4] Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt (NeurIPS 2023)

[5] Local Search GFlowNet (ICLR 2024)

[6] DeepACO: neural-enhanced ant systems for combinatorial optimization (NeurIPS 2023)

[7] EURO Meets NeurIPS 2022 Vehicle Routing Competition (NeurIPS 2022)

[8] Learning to Remove Cuts in Integer Linear Programming (ICML 2024)

[9] Rethinking Branching on Exact Combinatorial Optimization Solver: The First Deep Symbolic Discovery Framework (ICLR 2024)

[10] NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem (NeurIPS 2021)

[Purely Online Setting (Q1)]

Thank you for your thoughtful comment. We do believe that our work is largely applicable to online FJSP. However, there is a technicality regarding purely online settings, where a single operation is revealed at a time. Because our method leverages the ability to solve shifted subproblems, it is advantageous for the method to observe a batch of new operations. We wrote “one of the first steps towards online setting” simply because we did not want to over-claim that our work is applicable in the limiting case (which we did not consider or evaluate). Upon further thought, we realized that it is often practical even in online settings to consider a batch-online setting; for example, in (online) ride-hailing, it is advantageous to the platform (e.g., Uber) to batch ride requests over 30 seconds rather than match each incoming request one at a time. In response to your comment, we have revised the language to say “Next, we explore FJSP variants, including observation noise and machine breakdowns, to evaluate the applicability of L-RHO to batch-online FJSP.”

[RHO with Prolonged Runtime (Q2)]

Thanks for the Insightful question! Yes, with significantly longer (albeit prohibitively long) time limit, the default RHO can achieve a better objective. To address this comprehensively, we have followed the suggestion and included additional results as follows. As detailed in Appendix A5.4, two parameters control the time limit per subproblem: 1) total time limit, where solving terminates if the time exceeds $T$=60s; 2) early stop time, where solving terminates early if the objective does not improve within $T_{es}$=3s. In the table below, we evaluate the default RHO with increased $T$ and $T_{es}$. 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-RHO delivers superior performance under practical time constraints, offering benefits especially in online cases.

[Remarks]

Thank you for the remarks! Please see our response: 1) In the updated Table 1, we report the CP-SAT performance with a time limit of 10 hours (36000 seconds). Unfortunately, CP-SAT still performs worse than RHO based methods under this generous time limit; this further illustrates the difficulty of the long horizon FJSP and the importance of decomposition based methods in solving these problems. 2) Thanks for the suggestion. We update the text to “solving COPs” and “solving for T seconds”.

We appreciate the reviewer's positive and valuable feedback! We are pleased that the reviewer recognized our L-RHO’s originality, capability to handle longer horizons, and in-depth analysis in various FJSP settings. We hope the following response would clear the remaining concerns.

[Applicability to other COPs (W1)]

Thank you for the suggestion to elaborate on the applicability of L-RHO to other long-horizon COPs! This suggestion prompted us to revise our contributions statement; as stated there (General Response 1/4), L-RHO can be applied to any long-horizon COP for which rolling-horizon optimization can be applied. However, we note that the effectiveness of such an approach may vary from application to application and is an important direction of future research. As such, the theoretical analysis in our paper complements our FJSP-focused evaluation to provide application-agnostic insights into when such an approach would be advantageous.

Within FJSP, we do demonstrate the effectiveness of L-RHO on a rich set of variants: we investigate multiple scheduling objectives, including makespan, start delay, and combined start-end delay, while considering addressing more complex scheduling variants including observation noise and dynamic scenarios like machine breakdowns. Our evaluation methodology is consistent with (or arguably richer than) learning-for-COP literature published in leading ML conferences, which for various reasons, including compute costs and benchmark availability, tend to focus on canonical problems within a COP class (e.g., routing [1-3] or scheduling [4-5]).

Beyond FJSP, we provide a few demonstrative examples on how one can apply L-RHO to other COPs. (1) In Multi-item Inventory Management, one need to decide the quantity of inventory to hold over multiple periods. When solving this using a RHO framework, one can fix the quantity of a subset of items and only re-optimize the rest to improve the efficiency of the solving. (2) in Vehicle Routing with Time Windows, vehicles visit customers in increasing time order; as new customers come in, instead of re-optimizing the entire route, one can identify which segments of the route can stay the same and only re-optimize a partial segment. To apply L-RHO, the key is to identify fixing which variables in the overlapping subproblems, can be fixed, are amenable to learning, and can lead to a significant time improvement. Again, these extensions are valuable and interesting future directions.

[1] Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time (ICLR 2023)

[2] Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization (NeurIPS 2023)

[3] Towards Omni-generalizable Neural Methods for Vehicle Routing Problems (ICML 2023)

[4] Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problem (UAI 2024)

[5] Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling (ICLR 2024)

[Clarity on Proposition 1 (W2)]

Sorry for the confusion! We have updated the theoretical analysis section to make it more clear. Specifically, as seen in Figure 4, middle (in the updated paper) and Proposition 1, the performance of the Random and First baselines depend on the underlying structure of the Oracle distribution. For example, when the problem structure is such that $n_{fix}^*$ is high (more overlapping operations should be fixed), randomly choosing a large number of operations to fix (Random with a high $\sigma_{R}$) results in good performance reflected by low FPR and FPN. Likewise, when the linear decay structure has a higher slope (operations with an earlier precedence order are more likely to be fixed, the First baseline further offers a performance benefit (as seen by the higher $m$ term, which reduces the FPR and FNR of First). When the problem structure is less regular (e.g. more flat slope for the linear decay), we cannot determine whether each operation should be fixed — in those cases, the First baseline’s performance reduces, and that’s when learning is more beneficial.

[Remove DRL-450 Results (W3)]

Thank you for the suggestion. We initially included the DRL-450 Results to highlight that our L-RHO achieves state-of-the-art performance with significantly fewer FJSP training instances than existing DRL works, which is a critical advantage in real-world scenarios where such instances are scarce. Based on your feedback, we have removed the DRL-450 results. Notably, the included baseline DRL-20K actually utilizes more samples than the suggested “450x[the number of subproblems per instance]” — for example, L-RHO for 600 operations contain only 20 subproblems per instance. Moreover, we have added two new DRL baselines to further demonstrate that L-RHO achieves state-of-the-art performance.

We would like to share an update regarding the model architecture. When we examine the attention map as suggested by Reviewer #ppet, we realized that our reported architecture’s attention map was not actually used (weights of the attention layer converges to 0 due to an implementation issue). That is, in effect, our reported experimental results reflect a simpler neural architecture design. We are grateful for the reviewer’s comment which led us to uncover this experimental issue. We believe this highlights a strength of our work, as it shows that integrating machine learning to Rolling Horizon Optimization can be highly effective for long-horizon FJSPs, even with a simple neural architecture.

We provide the following revisions and discussions:

• We have updated the architecture figure (Figure 2) in the main paper to reflect the architecture without the multi-head attention layer and rephrased the descriptions accordingly. To ensure experimental rigor and eliminate further issues, we carefully examined the network, reloaded the previous checkpoint into the architecture without the attention layer, and verified that the results remain consistent.
• We conducted a detailed study analyzing the effects of incorporating the attention mechanism after resolving the implementation issue. Our findings show that adding the attention layer improves the True Negative Rate (TNR) but lowers the True Positive Rate (TPR), resulting in a comparable overall accuracy. Results below show that, on FJSP instances (600 operations), the architecture with attention achieves a better makespan but incurs longer solve times compared to the architecture without attention.
• We note that such observed TNR-TPR tradeoff aligns with our theoretical analysis: as the simpler architecture without attention has a higher TPR but a lower TNR (i.e. it fixed more operations that should not have been fixed), the solve time is reduced with slight sacrifices in the objective. Conversely, the architecture with attention has a higher TNR but a lower TPR (i.e. it failed to operations that should have been fixed), which improves the objective but negatively impacts solve time.
• Due to the faster architecture without attention and similar objective, we revise the article to retain the simpler architecture (without attention), and include the detailed comparison with the architecture with the attention layer in Appendix A.6.3.

[Performance of L-RHO on Real-World Benchmark Instances]

In response to Reviewer #PSPu, we add a new comparison on the instances from Dauzere-Peres and Paulli (1997) when scaling them to long-horizon. As shown in the new Table 15 in Appendix A.6.1, L-RHO achieves a 2.7% lower gap than DRL-20K, when both are compared to the best known solution. Notably, L-RHO achieves near-optimal performance in the smallest setting, and maintains its advantage in larger settings without any fine-tuning. It also significantly accelerates Default RHO by 24%-38%, highlighting the benefits of learning to enhance RHO and its practical impact on real-world deployment.

[Significance of L-RHO Results]

Our L-RHO achieves state-of-the-art performance, outperforming various traditional and learning-based baselines both with and without decomposition in various challenging settings. This is significant for the following reasons:

1. L-RHO significantly accelerate the Default RHO by 35-54% while enhancing its performance by 3-21%, as demonstrated in Tables 1 and 2.
2. L-RHO consistently delivers state-of-the-art results across diverse scheduling variants. This is evidenced by Tables 1 and 2 and Figure 3, across different problem sizes, data distributions, objectives, under online observation noise and machine disruption.
3. L-RHO outperforms DRL baselines with less information and broader applicability. While the DRL baselines rely on complete problem information and is unsuitable for online problems, L-RHO operates effectively within a limited RHO window, achieving better objectives with comparable or even shorter solve times and is well-suited for addressing online problems.
4. L-RHO excels in its simplicity and effectiveness. Beyond merely competing on performance benchmarks, where algorithms in the literature are becoming increasingly complex, L-RHO stands out for its remarkable simplicity and effectiveness, outperforming numerous complex baselines across a range of pratical FJSP variations.
5. L-RHO can have real-world impact. L-RHO achieves a 2.7% gap lower than the DRL baseline on real-world instances. While the number may look small, performance improvements that approach optimality are indeed challenging. As such, a 2.7% performance improvement is significant, and is typical for novel research in this area [3, 4]. In addition, such 2.7% improvement can translate in practice to a 2.7% revenue increase—an enormous benefit for companies managing billion-dollar operations.

[3] Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problem (UAI 2024)

[4] Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling (ICLR 2024)

[Updated Table 1 with More Baselines and Comparison]

In response to the valuable suggestions from Reviewer #ppet and #PSPu, we have updated Table 1 to include results for CP-SAT and default RHO with longer runtime, as well as two learning baselines recommended by Reviewer #PSPu (we copied the new results in the Table below):

1. We add CP-SAT result when giving a generous time limit of 10 hours (36000s). We find that CP-SAT is still subpar from the RHO based methods. This further illustrates the difficulty of solving long-horizon FJSP.
2. We add another Default RHO result with an increasing time limit. We find that, in this case, L-RHO still outperforms Default RHO in the objective with a 5 times less solve time.
3. We add two FJSP learning baselines (DRL-Echeverria [1], DRL-Ho [2]) suggested by reviewer PSPu. We find that the two learning baselines have significantly worse performance than the DRL baseline (Wang et al.) that we compared in the original paper.

[1] Solving large flexible job shop scheduling instances by generating a diverse set of scheduling policies with deep reinforcement learning (arXiv 2023)

[2] Residual scheduling: A new reinforcement learning approach to solving job shop scheduling problem (IEEE Access 2024)