acceptodds
Under review as a conference paper at ICLR 2027

Align-and-Improve: Addressing State Staleness and Plan Quality in Dual-Stream Dynamic Scheduling

Abstract

Dynamic job shop scheduling requires immediate assignments, while slower search constructs candidate rules and plans. In a dual-stream scheduler, a request may be based on an observation that becomes stale before generation starts. A returned rule may also produce an inferior continuation, and an accepted plan may lose its advantage as execution proceeds. We present Align-and-Improve (AAI), which addresses these distinct sources of mismatch at request, plan and action time. Late State Binding (LSB) associates a pending request with the latest observed state when the generator claims it. Verified Plan Update (VPU) materializes candidates on the current state and replaces an incumbent only after a feasible, strictly improving comparison and a commitment-time consistency check. Rollout-Based Action Arbitration (RAA) compares the retained plan's next action with an action from the fast dispatching rule, evaluating both with the same fast-policy continuation before executing one assignment. Across 58 instances from four benchmark families, AAI lowers mean relative percentage deviation by about five percentage points versus RACE on three shared Qwen3.5 backbones while cutting model-token usage by up to about 90%.

Primary area:
optimization
Keywords:
Dynamic Job Shop Scheduling, Dual-Stream Planning

Reviews

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

This paper proposes Align-and-Improve (AAI) for asynchronous dynamic job-shop scheduling, where a fast dispatching policy continues executing while a slower LLM produces candidate rules. AAI combines Late State Binding (LSB), which attaches the latest observed state when a request is claimed. Verified Plan Update (VPU) accepts a candidate continuation only after checking feasibility improvement over the incumbent and consistency at commitment. And Rollout-Based Action Arbitration (RAA) compares the retained plan’s next action against the fast policy under a shared continuation policy. Experiments cover 58 instances from four benchmark families and demonstrate the effectiveness of the proposed method.

Critical strengths
  • The paper addresses a meaningful deployment problem with a coherent separation of concerns. A proposal can become stale while awaiting generation, remain feasible but inferior when returned, and lose its advantage during subsequent execution.
  • VPU includes careful safeguards for concurrent execution. Evaluating the incumbent and candidate on the same state, preserving running operations, and rechecking state and plan consistency before commitment are appropriate measures. The paper also correctly limits its guarantee to the evaluated continuation and acknowledges that later events can reverse the benefit.
  • The results provide meaningful evidence of improvement over the matched RACE controls.
Critical weaknesses
  • The incremental contribution over existing validation and rollout mechanisms is insufficiently established. RACE already evaluates candidate and incumbent policies in a sandbox and uses feasibility and improvement criteria before atomic deployment. The paper should explain this distinction more explicitly and clarify whether its RACE control preserves the original validator, acceptance thresholds, and other relevant components.
  • Real-time suitability and total computational efficiency remain unverified. RAA can perform two continuation rollouts before each dispatch, while VPU introduces native search and plan verification. Token counts omit these costs. The paper does not provide sufficient end-to-end latency or scaling measurements to determine whether the method preserves the fast stream’s responsiveness.
  • The evidence for LSB is substantially narrower than the motivating staleness problem. It does not establish that actual LLM requests incorporate the intended snapshot or that waiting-time staleness materially affects deployed performance.
  • The evaluation does not yet establish a clear advantage over the strongest non-LLM alternative. A matched quality–runtime comparison with strong non-LLM optimization and rollout baselines would be more informative.
Questions for authors

Please refer to the weaknesses.

Reviewer_Aq4vOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes AAI to coordinate fast dispatching with slower LLM-based rule generation in dynamic job shop scheduling. LSB binds a request to the latest state when processing begins. VPU compares a candidate plan with the incumbent and accepts only feasible improvements. RAA compares the plan’s next action with an action from the fast dispatching rule before execution. The authors evaluate the method on 58 instances from four benchmark families, reporting better scheduling quality and lower token usage than RACE. Ablation and timing experiments examine the individual components.

Critical strengths

VPU’s update conditions are reasonably clear. The candidate and incumbent are evaluated on the same state, and the state is checked again before the update is committed. This provides a concrete procedure for updating plans in an asynchronous scheduler. The authors also acknowledge that an improvement under the current state does not guarantee a better final schedule.

Critical weaknesses
  1. The effect of VPU is not separated from the effect of additional search, and the PDR comparison has unresolved evaluation issues. Section 4.2 states that VPU uses CP-SAT and neighborhood search in addition to checking candidate plans. The gains from VPU-only could therefore come from stronger search, the acceptance condition, or both. The current ablation does not distinguish these possibilities. The paper also does not report results with the LLM removed while retaining native search and RAA. The PDR-only comparison does not resolve this concern. Appendix A explicitly states that the score definition and evaluation matching remain unconfirmed, yet the main text uses these results to discuss AAI’s advantage over fixed rules. The AAI RPD for Qwen3.5-35B is also 7.48% in Table 2 but 8.0294% in Table 7, with similar differences for the other backbones. This is not necessarily a calculation error, but the relationship between these results needs to be explained before the comparison can support the conclusion.

  2. LSB lacks sufficient validation in actual asynchronous execution, and its standalone ablation is not reported. Table 1 measures whether results are stale when they return. LSB, however, only addresses state changes between request creation and the start of processing. The paper does not show how much of the observed staleness arises during that interval. The timing experiment in Table 6 is also limited. Appendix E states that it makes no LLM, provider, or simulator calls. Instead, it assigns a weight to the critical job and computes the outcome from constructed durations and the selected action. This shows that reading the state later can expose a newly arrived job, but it does not establish how much benefit LSB provides in the actual system. Appendix D says that an LSB-only experiment was conducted, but its results are not reported. In Table 4, VPU-only and full AAI improve over RACE by 10.33% and 10.74% on average, respectively, without an uncertainty estimate for their difference. The available evidence is insufficient to establish a consistent independent benefit from LSB.

Questions for authors
  1. Why do the AAI RPD values differ between Table 2 and Tables 5 and 7? Do these results use the same instances, random seeds, and reference makespans? What exactly remains unconfirmed about the evaluation matching mentioned in Appendix A?
  2. Since the LSB-only experiment has already been conducted, could you provide its full results? In actual execution, how much state staleness occurs before processing begins, and how much occurs during model generation?
  3. Two controls would help identify the source of the gains: removing the LLM while retaining native search and RAA, and removing only the strict-improvement acceptance condition while keeping candidate sources and computational budgets fixed. How does the method perform under these settings? These controls are needed to assess the paper’s current claims.
Reviewer_VjW1OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper addresses the following problem in dual-stream dynamic job shop scheduling - the setup is that there is a fast stream that dispatches jobs based on priority dispatching rules and a slow stream that uses an LLM to generate scheduling rules/plans. Clearly the latter might be working with a “stale state” because of the asynchronous nature of the process.

The main contribution is AIA (Align-and-Improve), an execution control wrapper.

There are three ideas:

  • Late State Binding (LSB): binds the latest observed state only when the worker claims the request
  • Verified Plan Update (VPU): materializes candidate plans (from returned LLM rules + online SAT/neighborhood search) on the current state and replaces the incumbent plan when it feasible/improves makespan
  • Rollout-Based Action Arbitration (RAA): compares the retained plan's next action against the fast stream decision using a full rollout with the fast stream before executing.

The paper evaluates AAI on 58 benchmark instances - main findings are that AAI reduces mean relative % deviation by 4.3–5.5% and cuts token usage by 80-90% compared to RACE (baseline).

Critical strengths
  • The paper addresses practical considerations, though I am not sure how many places this type of dynamic job scheduler are deployed (rather than using combinatorial methods or solvers)
Critical weaknesses
  • The innovations - LSB/VPU/RAA - are standard engineering practices
  • The technical novelty is minimal
  • Some of the ablations in experiments could be done better (eg, would be good to know how useful LSB is by itself)
Questions for authors

1 In Appendix A, you say "The score definition and evaluation matching remain unconfirmed, as discussed in Section 5.5". What do you mean by this?

2 Why is Xu et al the right reference for dynamic job shop scheduling? Also line-147, why is Cao et al the right reference for minimizing terminal makespan? Scheduling problems are almost as old as computer science itself and the authors should exhibit better scholarship finding and citing the appropriate references.

The paper should improve writing:

  • There is classic AI-text in many places - makes the text really hard to read

  • Terms like RACE used before definition/introduction (eg, on line 91)

  • Seems some repetition of content in lines 432–447?

Comments on the paper

1 comment
Area_Chair_wuomOpenReview ↗

Authors response?

Dear authors,

Author-reviewer discussions end on November 18th. Please submit your responses to the reviewers reviews as soon as possible, so the reviewers would be able to respond to you.

Thank you.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.