acceptodds
Under review as a conference paper at ICLR 2027

Solving in Imagination: Multi-Step Latent Planning for Combinatorial Scheduling

Abstract

Neural constructive policies have attracted increasing attention for combinatorial scheduling by learning to construct schedules through sequential decisions. However, existing methods primarily optimize representations for immediate action selection and recompute them by re-encoding the exact state after each action rather than explicitly modeling how decision-relevant representations evolve across successive scheduling steps. Moreover, repeatedly re-encoding the evolving partial schedule introduces substantial redundant computation during inference. To address these limitations, we introduce the Multi-Step Latent Planning Model (MSLPM) for constructive combinatorial scheduling. We develop a solve-then-imagine training scheme that first jointly trains an Encoder and Actor to establish a decision-relevant latent space, and then freezes both modules while learning Dynamics to propagate this fixed representation under scheduling actions through latent alignment and decision-consistency supervision. Building on these learned latent dynamics, we introduce a multi-step latent planning mechanism that recursively generates an -step action prefix from a single exact-state encoding by alternating the Actor and Dynamics, while exact scheduling operators maintain feasibility. Across three benchmarks, i.e., PFSP, JSSP, and FJSP, MSLPM achieves lower average gaps than the greedy neural baselines considered, while multi-step latent planning substantially reduces inference time by replacing intermediate re-encoding with latent transitions.The code will be publicly released upon acceptance.

Primary area:
optimization
Keywords:
Combinatorial Scheduling, Latent World Models, Multi-Step Planning, Neural Combinatorial Optimization, Constructive Policies.

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_kQUrOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes MSLPM, a constructive scheduling framework for PFSP, JSSP, and FJSP that combines multi-step decision-making with a latent world model. By learning to propagate scheduling representations, it reduces repeated exact-state encoding and achieves substantial inference speedups while retaining competitive solution quality. This conceptual connection is appealing, but the current experiments do not sufficiently isolate the benefits of learned latent updates over simpler representation reuse. The evaluation is also limited in baseline coverage, problem scope, and decoding strategies. Furthermore, the sources of the runtime gains and the reproducibility of the horizon-dependent quality improvements remain insufficiently analyzed, leaving the method’s incremental contribution unclear.

Critical strengths

This work presents a strong and general constructive approach applicable to PFSP, JSSP, and FJSP. It cleverly combines multi-step decision-making with latent world modeling, substantially accelerating solution construction.

Critical weaknesses

The paper attributes its inference speedup to replacing repeated exact-state re-encoding with learned latent transitions. However, MACSIM [5] already constructs a joint assignment through multiple steps that reuse the same logits, without intermediate re-encoding or learned latent updates. This demonstrates a simpler way to reduce inference cost and raises a central question: what does the additional world model contribute beyond direct representation reuse? The comparison between H = 1 and H > 1 does not answer this question, because it changes both the re-encoding frequency and the use of Dynamics. Likewise, removing the latent alignment, decision consistency, and one-step anchor losses only evaluates how Dynamics is trained; it does not establish the value of updating latent representations in the first place. A necessary control is to keep the root embeddings fixed, update the exact feasibility mask, and rerun the Actor at each step under the same horizon and re-encoding schedule. Without this comparison, the current experiments do not justify the additional world-model complexity over simple representation reuse in terms of the quality–runtime trade-off.

Despite its broad framing around “combinatorial scheduling,” the experimental evaluation of MSLPM is incomplete in both baseline coverage and problem scope. Relevant recent methods, including BOPO[4] for JSSP and MACSIM[5] for FJSP, are missing from the comparisons. Moreover, FFSP, which is evaluated in ReSched[2] and MACSIM[5], is not considered, leaving the broader applicability of the framework insufficiently assessed. Although the authors explicitly adopt greedy strategy across neural methods to avoid introducing unequal sampling budgets, the evaluation remains limited to this setting and does not examine sampling decoding strategy, a common strategy for constructive solvers[1,2,3,4,5]. In addition, the sources of the reported runtime gains are not clearly disentangled. It remains unclear how much of the acceleration comes from replacing Encoder forward passes with Dynamics and how much comes from changes in state construction costs. A runtime breakdown separating Encoder/Dynamics network forward pass time from state-construction time would help clarify the efficiency benefits.

Much of MSLPM’s advantage in solution quality over the compared baselines is already achieved by the Encoder and Actor trained in Stage 1. However, the effect of latent planning on solution quality remains insufficiently analyzed. In particular, FJSP solution quality varies nonmonotonically with the planning horizon: H = 3 performs worse than H = 1, whereas H = 5 outperforms both. This warrants further explanation given that Stage 2 trains Dynamics to reproduce the frozen Encoder’s representations and the corresponding Actor decisions. Exact reproduction would yield the same decisions and solution quality as direct Encoder–Actor decoding, yet Dynamics based rollouts sometimes produce better solutions. The paper does not adequately explain the source of these improvements or establish their reproducibility. Results across multiple independent training seeds, with means and standard deviations, are needed to establish the reproducibility of the reported quality differences and the robustness of the balance between solution quality and runtime.

[1]. Flexible Job Shop Scheduling via Dual Attention Network-Based Reinforcement Learning. IEEE Transactions on Neural Networks and Learning Systems, 2024.

[2]. RESCHED: Rethinking Flexible Job Shop Scheduling from a Transformer-based Architecture with Simplified States. International Conference on Learning Representations, 2026.

[3]. Self-Labeling the Job Shop Scheduling Problem. Advances in Neural Information Processing Systems, 2024.

[4]. BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization. International Conference on Machine Learning, 2025.

[5]. Multi-Action Self-Improvement for Neural Combinatorial Optimization. International Conference on Learning Representations, 2026.

[6]. Matrix Encoding Networks for Neural Combinatorial Optimization. Advances in Neural Information Processing Systems, 2021.

Questions for authors
  1. How does MSLPM compare with a simpler version that directly reuses embeddings without learned latent updates?
  2. The baseline coverage is insufficient. Can the authors include additional recent methods, such as BOPO for JSSP and MACSIM for FJSP?
  3. Can the authors separately report network forward pass time and state construction time to clarify the sources of acceleration?
  4. While acknowledging the consistent use of greedy decoding, how does MSLPM perform with sampling?
  5. Are the results reproducible across multiple training seeds? Please report means and standard deviations for different H values.
  6. Can the authors provide results on FFSP?
  7. Given that Stage 2 trains Dynamics to imitate the original policy, what explains the improvements over H = 1 in some settings?
  8. What explains the nonmonotonic relationship between H and solution quality?
5 comments

Dear Reviewer,

Thank you for proposing the fixed-embedding control, asking us to separate network time from state construction, and pointing out the nonmonotonic FJSP gaps. We address those questions and the requested evaluations below.

W1: The benefit of Dynamics needs a fixed-embedding control.

A1: Thank you for the suggestion. Dynamics updates the information used for action ranking after each scheduling decision. Reusing root embeddings lets the Actor re-contextualize the current feasible set. Dynamics additionally conditions the token update on the selected action, carrying changes in job and machine readiness into successor representations through latent alignment and decision consistency (Sections 4.2 and 4.4).

Our original fixed-horizon experiments showed that increasing the number of imagined steps could improve solution quality. Motivated by this observation, we introduce a new Latent Regret Gate (LRG) in the revision to decide, from predicted local decision regret, when to continue solving in imagination and when to refresh the representation through the Encoder. We denote this adaptive variant as Auto and evaluate its benefit against fixed horizons in the revised experiments below.

Table R2 reports the benefit of using these latent updates together with adaptive refreshing. With the same frozen Encoder-Actor, Auto reduces FJSP gap from 8.44% to 7.11% and time from 0.20 s to 0.07 s relative to H=1H=1. Holding Dynamics fixed, Auto and fixed H=5H=5 both take 0.07 s, with gaps of 7.11% and 7.92%. These results show how action-conditioned representation propagation and regret-guided refreshing work together in the scheduling procedure.

W2: Comparisons with BOPO and MACSIM under matched decoding settings are needed.

A2: Thank you for recommending these comparisons. The revision includes BOPO on JSSP and FJSP, and MACSIM on FJSP, under greedy decoding. On JSSP, Auto lowers BOPO's overall mean gap from 14.44% to 10.80% and runtime from 1.40 s to 1.24 s. Auto has lower gaps on all three benchmark families; on Lawrence, BOPO is faster at 0.39 s versus 0.67 s for Auto (Sections 5.1 and 5.2).

The FJSP benchmark comparison includes MACSIM and BOPO on FJSP. Under greedy decoding, MACSIM uses the same checkpoint across Brandimarte and Hurink, and its gaps use the same instance-wise CP-SAT reference as the other methods. Auto reaches 7.11% in 0.07 s overall, compared with 8.32% in 1.29 s for MACSIM and 8.93% in 0.33 s for BOPO. MACSIM gives a lower gap on Hurink rdata (6.52% versus 8.94%), and BOPO gives a lower gap on Hurink vdata (0.47% versus 1.10%).

W3: Network and state-construction costs need separate timing.

A3: Thank you for asking where the speedup comes from. On FJSP, the Encoder time saved exceeds the added Dynamics and gate time. Table R1 summarizes Encoder calls, Encoder time, Dynamics and LRG costs, and total time for H=1H=1 and Auto; Appendix E provides the full breakdown. From H=1H=1 to Auto, Encoder time falls from 2565.61 to 522.19 ms on PFSP, 1996.62 to 486.19 ms on JSSP, and 152.66 to 38.64 ms on FJSP (Appendix E).

On FJSP, mean Encoder calls fall from 149.34 to 49.18 per case. Auto spends 27.84 ms in Dynamics and 1.91 ms in the gate, with 70.00 ms end to end compared with 200.00 ms at H=1H=1. Together, Auto's Encoder, Dynamics, and gate take less time than the Encoder alone at H=1H=1. In Appendix E, Other is the end-to-end total minus the listed module times and aggregates the remaining unitemized runtime. The end-to-end timing scope is specified in Appendix D.5; state construction is included in the total and has no separate component measurement.

On FFSP, mean Encoder calls decrease from 60.00 to 56.40 per instance, and Encoder time falls from 66.10 to 31.70 ms. Auto spends 7.58 ms in Dynamics and 4.24 ms in LRG. The 34.40 ms saved in Encoder time exceeds the combined 11.82 ms cost of Dynamics and LRG, while total time falls from 69.34 to 46.44 ms, an approximately 33.0% reduction (Table R1). These FFSP times measure amortized per-instance throughput under the batched GPU protocol in Appendix D.5; fixed-horizon and Auto evaluation use local per-rank batch sizes 128 and 64, respectively. The reduction therefore describes the evaluated execution configurations.

Table R1: Runtime summary for H=1H=1 and Auto. Calls are mean Encoder calls; all times are ms per instance. FFSP uses amortized batched timing (Appendix D.5). Appendix E reports all horizons, remaining components, and percentages.

TaskHorizonCallsEncoderDynamicsLRGTotal
PFSPH=1H=1693.752565.61––4110.00
PFSPAuto91.01522.1984.5611.47690.00
JSSPH=1H=1561.251996.62––2940.00
JSSPAuto142.03486.19476.9276.591240.00
FJSPH=1H=1149.34152.66––200.00
FJSPAuto49.1838.6427.841.9170.00
FFSPH=1H=160.0066.10––69.34
FFSPAuto56.4031.707.584.2446.44

Q1: How does best-of-100 sampling compare with greedy decoding?

A4: Thank you for this question. Best-of-100 sampling improves the overall mean gap at a higher inference-time cost. On FJSP, Auto's gap falls from 7.11% to 6.20%, while runtime rises from 0.07 s to 5.55 s. Auto has the lowest overall gap in both decoding modes, and fixed H=5H=5 is fastest under sampling at 4.23 s. Gains vary by subset: on Hurink vdata, greedy Auto gives 1.10% and sampled Auto gives 1.86% (Table R2).

Table R2: Overall FJSP gap (%) / time (s), over 130 instances. Frozen Greedy and Sampling share the same solver; Sampling selects the best of 100 schedules. Unfrozen uses greedy decoding after joint Stage-2 training. Full subset results appear in revised manuscript Table 6.

HorizonFrozen GreedySamplingUnfrozen
H=1H=18.44/0.207.74/9.658.92/0.20
H=3H=39.20/0.096.92/5.1610.06/0.09
H=5H=57.92/0.076.38/4.2311.13/0.07
Auto7.11/0.076.20/5.558.58/0.08

Q2: Are the improvements consistent across independent training seeds?

A5: Thank you for asking about reproducibility. We could not complete independent-seed retraining within the available discussion time. Mechanistically, freezing the Encoder-Actor gives Dynamics fixed latent and decision targets, avoiding simultaneous changes in these targets during training. Multi-step alignment and decision consistency further supervise recursive predictions at each rollout depth. We expect this combination to help stabilize Dynamics training across seeds.

Q3: How does the method compare with ReSCHED and MatNet on FFSP?

A6: Thank you for suggesting FFSP evaluation. Table R3 reports results on 3,000 instances. Auto achieves an overall mean makespan of 56.29, compared with 56.72 for ReSched20 and 57.10 for MatNet100. Relative to H=1H=1, Auto lowers mean makespan from 56.36 to 56.29 and reduces mean inference time from 69.34 to 46.44 ms, an approximately 33.0% reduction. Auto matches the H=1H=1 makespan on FFSP50 and improves it on FFSP20 and FFSP100. Fixed H=5H=5 is faster at 42.06 ms, with a higher mean makespan of 57.57 versus 56.29 for Auto. On FFSP20, ReSched20 achieves a lower makespan of 26.60 than Auto's 26.87. Table R1 reports the corresponding FFSP runtime summary. Appendices D.1 to D.5 specify the data splits, training settings, and batched timing protocol.

Table R3: FFSP mean makespan / time (ms). Overall averages 3,000 instances equally across sizes. Full horizon results appear in revised manuscript Table 4.

DatasetReSched20MatNet100H=1H=1H=5H=5Auto
FFSP2026.60/11.9527.68/59.5726.96/4.7128.17/2.2026.87/2.99
FFSP5051.17/42.9351.82/78.2450.55/28.3051.69/15.7650.55/17.13
FFSP10092.39/157.6791.80/118.9191.57/175.0292.86/108.2291.46/119.21
Overall56.72/70.8557.10/85.5756.36/69.3457.57/42.0656.29/46.44

Q4: Why can latent rollouts outperform stepwise re-encoding?

A7: Thank you for raising this apparent paradox. Latent rollouts can outperform H=1H=1 because they change the action rankings of a greedy policy. A different feasible choice can lead to a shorter final makespan, and LRG controls when to refresh the representation using predicted decision regret. Table R2 also shows an improvement with fixed refreshes: the frozen solver's mean FJSP gap falls from 8.44% at H=1H=1 to 7.92% at H=5H=5.

Auto uses predicted decision cost to decide when to re-encode. During gate training, if the predicted latent and fresh encoding lead to different actions at the same state under the same exact feasibility mask, we complete both schedules with the same policy and measure the signed makespan difference on FJSP. At inference, Auto re-encodes when the predicted regret score reaches its threshold (revised Section 4.3 and Appendix C.3).

Q5: Why does solution quality vary nonmonotonically with rollout horizon?

A8: Thank you for highlighting this behavior. Changing the horizon changes both the refresh positions and the subsequent scheduling trajectory, so solution quality need not vary monotonically. For example, H=3H=3 refreshes before the fourth action and uses a predicted latent before the sixth; H=5H=5 does the reverse. Different rankings change machine availability and later decisions, making the final makespan depend on where the trajectories diverge.

The Stage-2 loss ablation shows that removing latent alignment increases the FJSP gap by 1.62 percentage points at H=3H=3 and 4.67 points at H=5H=5. The longer rollout is more sensitive to this loss. Table R2 shows that the ranking also depends on the trained model. The frozen setting gives gaps of 8.44%, 9.20%, and 7.92% at H=1H=1, H=3H=3, and H=5H=5, respectively. In the unfrozen setting, the gaps at H=3H=3 and H=5H=5 are 10.06% and 11.13%, reversing their order. Auto chooses when to re-encode based on predicted decision regret and achieves the lowest mean gap in both settings.

Reviewer_pg3mOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes the Multi-Step Latent Planning Model (MSLPM) for constructive combinatorial scheduling. The method adopts a two-stage "solve-then-imagine" strategy: first training an Encoder–Actor policy using solver-generated supervision, and then freezing these components to learn latent dynamics through alignment and decision-consistency objectives. During inference, the model generates multi-step action sequences using learned latent transitions while maintaining exact feasibility constraints. Experiments on PFSP, JSSP, and FJSP demonstrate improved solution quality over selected greedy neural baselines and reduced inference time relative to the H=1 model.

Critical strengths

1. Feasibility-preserving latent dynamics.

The separation of learned latent transitions from exact scheduling operators is a practical design choice. It allows the model to reduce repeated encoding while ensuring that prediction errors do not directly violate scheduling constraints.

2. Consistent within-model inference acceleration.

Experiments across PFSP, JSSP, and FJSP demonstrate substantial speedups over the H=1 model. The Stage-2 ablations further indicate that latent alignment, decision consistency, and one-step anchoring contribute to maintaining rollout quality.

Critical weaknesses

1. Insufficient evidence for the novelty and necessity of the proposed latent planning mechanism.

The proposed mechanism mainly performs greedy action selection with learned latent transitions, without explicit look-ahead search or comparison of alternative future trajectories. Its distinction from existing world-model-based policy decoding is therefore limited.

More importantly, the strongest solution-quality improvements over existing baselines are already achieved at H=1, without using Dynamics. Increasing H primarily improves efficiency and can degrade solution quality: the average gap increases from 11.08% to 12.16% on PFSP and from 12.14% to 12.58% on JSSP when H increases from 1 to 5.

The paper lacks essential comparisons with simpler alternatives, such as fixed-representation reuse or lightweight incremental updates. It also does not compare the proposed two-stage training strategy against joint optimization. Consequently, the necessity of the learned Dynamics model and the proposed training procedure remains insufficiently established.

2. Incomplete validation of the practical efficiency–quality advantage.

The reported speedups are primarily relative to MSLPM at H=1, rather than existing efficient neural solvers. For example, MSLPM at H=5 requires 0.80 s on PFSP compared with 0.11 s for Graph-IL, and 1.36 s on JSSP compared with 0.70 s for SLIM. Although MSLPM achieves better solution quality, its overall efficiency–quality advantage requires more systematic evaluation.

Furthermore, baseline training and checkpoint protocols differ, potentially affecting comparison fairness. The absence of multiple training seeds and uncertainty estimates also limits the reliability of the reported improvements. Finally, FJSP gaps are measured against bounded CP-SAT solutions rather than certified optima or established best-known solutions, making their interpretation less straightforward.

Questions for authors

Q1. How essential is the learned Dynamics model compared with simpler representation-reuse mechanisms?

Could the authors provide comparisons against a baseline that keeps the Encoder representation fixed for H steps while updating only the exact feasibility masks, and against a lightweight incremental latent-update baseline? Such comparisons would help establish whether the proposed learned Dynamics model provides a meaningful advantage beyond reducing re-encoding frequency.

Q2. What evidence supports the necessity of the two-stage solve-then-imagine training strategy?

Could the authors compare the proposed frozen Encoder–Actor approach with joint training or another straightforward dynamics-distillation strategy? The current loss-term ablations are informative but do not establish that separating policy learning and dynamics learning is essential.

Q3. Can the authors provide stronger evidence for the practical quality–runtime trade-off?

In particular, could the authors report comparisons under matched inference-time budgets, training-time costs, and instance-wise quality–runtime trade-offs? Multiple training seeds and paired uncertainty estimates would also help determine whether the small solution-quality differences between different values of H are statistically reliable.

Q4. Can the authors clarify and strengthen the FJSP evaluation reference?

Why are the FJSP gaps computed relative to a bounded CP-SAT solution rather than established benchmark best-known solutions or certified lower bounds? Can the authors provide results using standard reference values and explain the effect of negative gaps on their reported averages?

3 comments

Dear Reviewer,

Thank you for asking which gains come from the Stage 1 policy, which come from rollout, and how the resulting schedules compare at practical inference budgets.

W1: The role of Dynamics and planning beyond Stage-1 greedy decoding is unclear.

A1: Thank you for asking us to clarify the contribution. Our original fixed-horizon experiments showed that increasing the number of imagined steps could improve solution quality. Motivated by this observation, we introduce a new Latent Regret Gate (LRG) in the revision to decide, from predicted local decision regret, when to continue solving in imagination and when to refresh the representation through the Encoder. We denote this adaptive variant as Auto and evaluate its benefit against fixed horizons in the revised experiments below. The gain beyond Stage 1 comes from evolving the policy's representation between encodings and adapting the refresh times. Table R1 uses the same frozen Encoder-Actor and shows lower mean gap and runtime for Auto on PFSP, JSSP, and FJSP. Here, latent planning advances this decision representation along a greedy trajectory using Dynamics and LRG.

Dynamics carries the effect of a selected action into the representations used for later rankings. Cached embeddings allow candidate re-contextualization through the updated mask, while Dynamics also updates the underlying tokens as the partial schedule evolves. Multi-step alignment and decision consistency train this action-conditioned evolution against exact successor encodings and the frozen Actor's preferences (Section 4.4).

The Auto versus fixed-HH comparison evaluates the refresh rule with Dynamics held fixed. On FJSP, Auto and fixed H=5H=5 both take 0.07 s, with gaps of 7.11% and 7.92%. Adaptive refreshing thus improves the quality-time trade-off of the latent rollout procedure.

W2: Freezing the Encoder and Actor needs justification against joint training.

A2: Thank you for this question. Freezing outperforms joint training in our FJSP evaluation and provides stable targets for Dynamics. The frozen setting yields lower mean gaps at all four horizons with comparable runtimes; at Auto, the gaps are 7.11% with freezing and 8.58% with joint training. Fixing the Encoder-Actor keeps both the successor representation and the decision rule stable during Stage 2 (Section 5.3).

The Stage-2 loss ablation in revised Section 5.3 isolates the loss terms: the Encoder-Actor stays frozen and only the Dynamics losses vary.

W3: Fair comparisons, training costs, and result uncertainty need clearer evaluation.

A3: Thank you for raising these evaluation questions. Our comparisons report solution quality and inference time under a common greedy-decoding protocol. Table R1 uses the same benchmark instances and hardware; Appendix D.3 specifies checkpoint and retraining settings. On FJSP, Auto improves the gap from 9.01% to 7.11% and time from 1.19 s to 0.07 s relative to ReSCHED. On PFSP and JSSP, lower gaps than Graph-IL and SLIM come with higher runtimes. Revised manuscript Tables 2 and 3 report the full BOPO and MACSIM results and subset differences.

Training cost. Appendix D.4 reports 24 epochs for Stage 1 and 48 for Stage 2, both on three GPUs. Stage 3 trains LRG with the backbone frozen. These settings describe the training procedure; stage-wise wall-clock costs remain unmeasured.

Uncertainty. The reported results characterize the evaluated checkpoints. Variability across independent training seeds and paired uncertainty across test instances remain unquantified. We therefore interpret the reported mean improvements within this evaluated setting.

Table R1: Overall greedy results, reported as mean gap (%) / time (s). MSLPM horizons share the same frozen Encoder-Actor. Selected neural baselines are listed for comparison; full benchmark and solver results appear in revised manuscript Tables 1 to 3.

TaskH=1H=1H=3H=3H=5H=5AutoSelected baselines
PFSP11.08/4.1112.02/2.3612.16/1.9610.47/0.69Graph-IL 23.35/0.11
JSSP12.14/2.9412.08/1.6312.58/1.3610.80/1.24SLIM 16.37/0.70; BOPO 14.44/1.40
FJSP8.44/0.209.20/0.097.92/0.077.11/0.07ReSCHED 9.01/1.19; BOPO 8.93/0.33; MACSIM 8.32/1.29

Q1: Why use CP-SAT references, and how are negative gaps averaged?

A4: Thank you for asking about the reference and averaging rule. For JSSP and PFSP, the public benchmarks provide best-known solution (BKS) values, which we use as the reference makespans. The FJSP instance files used in our evaluation do not include a unified BKS reference table, so we generate feasible reference solutions with CP-SAT, using eight workers and a 1,800-second limit per instance (Appendix D.3). We then fix one reference makespan per instance and evaluate every baseline and our model against exactly the same reference, using the same gap formula and signed averaging rule. Thus, the reported FJSP gaps compare all methods under a common evaluation protocol. The CP-SAT references are feasible incumbents, so a method that finds a shorter makespan receives a negative gap.

There is precedent for the solver comparison, although the gap denominator varies. ReSCHED reports OR-Tools results with a 1,800-second cap on Brandimarte and Hurink and computes the benchmark gaps against published best-known upper bounds. DANIEL uses time-limited OR-Tools makespans as the gap reference on its generated FJSP instances and published best-known makespans on public benchmarks. ReSCHED, Table 1 DANIEL, Sec. IV-C

How negative gaps enter the mean. If a method finds a shorter makespan than the CP-SAT incumbent, its gap is negative. We average those signed gaps across cases. For Auto, the five-case mean of -3.80% on Hurink vdata 15×1515\times15 alone implies that keeping negative values lowers the 130-case mean by at least 0.14 percentage points compared with clipping them to zero. The exact adjustment depends on the negative gaps across all cases.

A published best-known makespan provides a feasible reference for comparison with prior work. A positive certified lower bound gives an upper bound on relative suboptimality.

Dear Reviewer,

To better address your concern about the contribution of Dynamics beyond the learned Stage-1 policy, we added an embedding-reuse control with the policy and encoding schedule held fixed. We would like to share its setup and results as a supplement to our earlier response.

The experiment covers all 130 FJSP test instances. Both variants use the same frozen Encoder and Actor, greedy decoding, and exact feasibility masks, with matched Encoder calls and refresh positions. Fixed Reuse retains the cached embeddings between Encoder calls while recomputing candidate contextualization and action scores at each step. Learned Dynamics additionally updates the embeddings after each action. For Auto, Fixed Reuse replays the learned solver's refresh schedule.

Table R1: Overall mean gap (%) across all 130 FJSP test instances under greedy decoding. Encoder calls and refresh positions are matched.

Rollout settingFixed ReuseLearned Dynamics
H=1H=18.448.44
H=3H=315.989.20
H=5H=521.917.92
Auto15.857.11

As shown in Table R1, the two variants agree at H=1H=1. At H=3H=3, H=5H=5, and Auto, Learned Dynamics achieves a lower overall mean gap than Fixed Reuse, with improvements on all four benchmark sets. Because the policy parameters and encoding schedule are held fixed, these results provide direct evidence for the additional contribution of Dynamics to solution quality.

We have added the protocol and full results to Appendix D.6 and Table 19 (Appendix F.3) of the revised manuscript, with an analysis in Section 5.3. We hope this direct comparison provides a more complete answer to your concerns.

Reviewer_TdwcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Multi-Step Latent Planning Model (MSLPM), which is a latent world model designed for combinatorial scheduling problems. This method first trains the encoder and actor to make scheduling decisions, then freezes them and trains a Dynamics model to predict action-conditioned latent state transitions using latent alignment and decision-consistency objectives. In this way, MSLPM can generate multiple scheduling actions through latent rollouts without repeatedly encoding the exact state.

Critical strengths

I like to motivation of this paper, which addresses the computational overhead of repeatedly encoding scheduling states, which is an important efficiency challenge in sequential combinatorial optimization.

The 2-stage framework separates policy learning from dynamics learning, providing a stable way to learn latent transitions in a decision-relevant representation space. Also, combining the learned latent dynamics with scheduling constraints ensures that predicted latent states do not lead to infeasible scheduling actions.

Critical weaknesses

My major concern is about the jusitification for the learned dynamics model. Since scheduling transitions are deterministic and exactly known, the main benefit of learning latent dynamics is computational efficiency. However, the paper lacks comparisons with simpler alternatives, such as reusing a fixed encoding with updated action masks or incremental representation updates. It is unclear whether a learned world model is necessary to achieve the reported speedups.

The encoder is trained for action selection and then frozen before learning dynamics, but the representations optimized for current decisions may not preserve sufficient information for predicting future states. The paper does not adequately investigate this potential conflict between decision relevance and multi-step predictability.

In the experiment part, ablations mainly focused on training losses, without examining important architectural choices such as sparse versus full latent updates or frozen versus jointly trained representations. These comparisons would help establish which modeling decisions are essential to the method's effectiveness.

Questions for authors

See weaknesses

3 comments

Dear Reviewer,

Thank you for asking whether learned updates justify their cost when the scheduling transitions are exact, and whether the frozen representation supports those updates over multiple steps.

W1: The benefit of learned updates over embedding reuse is unclear.

A1: Thank you for raising this point. Dynamics carries action-dependent scheduling changes into subsequent action rankings. Exact transitions update the schedule and feasible set; the Actor uses latent tokens to rank feasible actions. Embedding reuse lets the Actor re-contextualize the current candidates, while Dynamics also updates their representations as job and machine readiness change (Section 4.2).

The transition module updates structurally selected successor tokens. Multi-step latent alignment trains these updates against fresh successor encodings, and decision consistency trains them to preserve the frozen Actor's action preferences. This design carries decision-relevant information between exact encodings while the exact scheduling operators maintain feasibility.

Our original fixed-horizon experiments showed that increasing the number of imagined steps could improve solution quality. Motivated by this observation, we introduce a new Latent Regret Gate (LRG) in the revision to decide, from predicted local decision regret, when to continue solving in imagination and when to refresh the representation through the Encoder. We denote this adaptive variant as Auto and evaluate its benefit against fixed horizons in the revised experiments below.

Table R1 shows the resulting quality-time trade-off with the same frozen Encoder-Actor. On FJSP, Auto reduces mean gap from 8.44% to 7.11% and time from 0.20 s to 0.07 s relative to H=1H=1. With Dynamics held fixed, Auto and fixed H=5H=5 both take 0.07 s at the reported precision, with gaps of 7.11% and 7.92%, respectively. This comparison shows the additional benefit of choosing refresh times through LRG.

Table R1: FJSP freezing and decoding (gap % / time s).

DatasetH=1 GreedyH=1 SamplingH=1 UnfrozenH=3 GreedyH=3 SamplingH=3 UnfrozenH=5 GreedyH=5 SamplingH=5 UnfrozenAuto GreedyAuto SamplingAuto Unfrozen
Brandimarte5.47/0.455.45/11.908.79/0.448.45/0.217.74/6.0111.08/0.216.32/0.169.60/4.7916.81/0.165.45/0.145.20/8.0810.37/0.23
Hurink edata13.55/0.1810.58/9.2613.61/0.1514.91/0.099.64/5.0015.29/0.0813.24/0.079.17/4.1215.80/0.0611.72/0.059.23/4.4411.84/0.06
Hurink rdata9.69/0.1810.05/9.449.77/0.1910.73/0.098.15/5.0811.13/0.089.04/0.077.31/4.1711.00/0.068.94/0.067.75/5.219.81/0.07
Hurink vdata2.81/0.183.18/9.693.41/0.192.14/0.092.78/5.193.49/0.081.87/0.071.88/4.245.16/0.061.10/0.071.86/6.363.65/0.09
Overall8.44/0.207.74/9.658.92/0.209.20/0.096.92/5.1610.06/0.097.92/0.076.38/4.2311.13/0.077.11/0.076.20/5.558.58/0.08

W2: Frozen policy representations may not support reliable multi-step prediction.

A2: Thank you for highlighting this concern. Our FJSP results show that the frozen policy space supports effective multi-step rollout. The key is to train Dynamics against the decision representation of each successor state. Freezing keeps these targets stable, while recursive latent alignment and the frozen Actor's decision supervision preserve information used at later steps (Section 4.4; Appendix C.2).

The FJSP results support this design over multiple steps. At H=5H=5, freezing the Encoder-Actor yields a gap of 7.92%, compared with 11.13% under joint training (Table R1). Removing latent alignment raises the gap by 1.62 percentage points at H=3H=3 and 4.67 points at H=5H=5 (Table R2). The larger penalty at H=5H=5 links longer-rollout solution quality to the multi-step alignment objective.

Q1: How do sparse versus full updates and frozen versus joint training compare?

A3: Thank you for the question. Freezing gives lower gaps in our FJSP comparison, while sparse updates focus transition computation on successor tokens. Table R1 shows lower overall gaps with freezing at all four horizons and comparable runtimes. Keeping the Encoder-Actor fixed also gives Dynamics stable representation targets and a consistent decision rule during training.

We update the activity tokens at structurally selected successor positions because these positions can supply candidates for the next decision. The transition Transformer processes this subset, so it handles fewer tokens than a full update (Section 4.2). The exact mask still determines which actions are feasible. Table R2 keeps the sparse architecture fixed and shows that removing any of the three losses increases the gap at both depths. This structure focuses transition computation on the successor tokens used in upcoming decisions.

Table R2: FJSP loss ablation (gap %; Δ\Delta: increase over full model).

VariantH=3H=3 GapH=3H=3 Δ\DeltaH=5H=5 GapH=5H=5 Δ\Delta
Full MSLPM9.20–7.92–
w/o Latent Alignment Llat\mathcal{L}_{\mathrm{lat}}10.82+1.6212.59+4.67
w/o Decision Consistency Ldec\mathcal{L}_{\mathrm{dec}}10.11+0.9110.57+2.65
w/o One-Step Anchor Lanc\mathcal{L}_{\mathrm{anc}}10.24+1.0410.79+2.87

Dear Reviewer,

To better address your concerns about whether learned updates improve on embedding reuse and whether frozen policy representations can support multi-step rollout, we added a direct comparison between Fixed Reuse and Learned Dynamics. We would like to share the experimental setup and results as a supplement to our earlier response.

The experiment covers all 130 FJSP test instances. Both variants use the same frozen Encoder and Actor, greedy decoding, and exact feasibility masks, with matched Encoder calls and refresh positions. Fixed Reuse retains the cached embeddings between Encoder calls while recomputing candidate contextualization and action scores at each step. Learned Dynamics additionally updates the embeddings after each action. For Auto, Fixed Reuse replays the learned solver's refresh schedule.

Table R1: Overall mean gap (%) across all 130 FJSP test instances under greedy decoding. Encoder calls and refresh positions are matched.

Rollout settingFixed ReuseLearned Dynamics
H=1H=18.448.44
H=3H=315.989.20
H=5H=521.917.92
Auto15.857.11

As shown in Table R1, Learned Dynamics achieves a lower overall mean gap than Fixed Reuse at H=3H=3, H=5H=5, and Auto, with improvements on all four benchmark sets; the two variants agree at H=1H=1. These results show that learned latent updates improve solution quality beyond embedding reuse under the same encoding schedule and support effective multi-step rollout in the frozen policy space. In addition, H=5H=5 and Auto achieve lower overall gaps than stepwise re-encoding at H=1H=1, while H=3H=3 does not.

We have added the protocol and full results to Appendix D.6 and Table 19 (Appendix F.3) of the revised manuscript, with an analysis in Section 5.3. We hope this direct comparison provides a more complete answer to your concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.