Learned Local Search for Job-Shop Scheduling When Processing Times Are Missing

Learned improvement heuristics are neural policies that repeatedly edit a complete, valid solution, for example by swapping two operations on a machine, instead of building a solution from scratch. They now beat strong solvers on large scheduling problems. All of them, however, assume that every number in the problem instance is known. Real shop floors rarely meet that assumption: some operation durations are never recorded, and the missing ones are often the long, unusual jobs.

This note proposes a specific approach to that setting. Keep the solution fully specified, and represent each missing duration as a set of plausible values drawn from an imputer, a model that predicts missing entries from observed ones. Then compute both the policy's reward and its view of "which operations are bottlenecks" over all of those values at once, in a single batched GPU pass. Training uses a critic, the value-estimating half of an actor-critic learner, that is allowed to see the hidden true durations. The central question is whether missing-data robustness in learned local search is mainly a reward-estimation problem, fixable at test time with sampling, or a representation problem, which requires a policy trained to read uncertainty. The experiments are designed so that either answer is informative.

Why job-shop scheduling is the right testbed

In the Job-Shop Scheduling Problem (JSSP), jobs are sequences of operations, and each operation must run on a given machine. The objective is the makespan, the time at which the last operation finishes. A solution is an ordering of operations on each machine, stored in a "disjunctive graph" whose edges encode job precedence and machine order.

That ordering stays valid no matter what the durations are. Missing durations therefore never threaten feasibility; they only blur the objective. This isolates the question cleanly, because missing data can affect only which moves look good, not which moves are legal.

The strongest learned improvement method here is L2S, Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling. It scores swaps of adjacent operations on the critical path, the longest chain of dependent operations, which sets the makespan. L2S rewrites the critical-path computation as GPU message passing and reports a speedup of over 11x for batch evaluation. The authors explicitly motivate improvement over construction by the value of seeing a complete graph, but they assume the instance itself is complete.

We reuse L2S's machinery, including its code at zcaicaros/L2S. The batched critical-path evaluation that L2S uses to score hundreds of schedules can be repurposed to score one schedule under hundreds of completions of the missing data.

Core Claim

Let $p$ be the vector of operation durations, $M$ the binary mask of which entries are observed, and $\sigma$ the current machine orderings. Let $q(p_{\text{miss}} \mid p_{\text{obs}})$ be a conditional imputer trained on the instance distribution. Draw $K$ completions $p^{(1)},\dots,p^{(K)}$ from $q$. One batched GPU pass then gives the sampled makespans $C(\sigma, p^{(k)})$. It also gives, for every operation $o$, a criticality probability

$$\pi_o = \frac{1}{K}\sum_{k=1}^{K} \mathbf{1}[\,o \text{ lies on the critical path of } (\sigma, p^{(k)})\,],$$

which is the fraction of plausible worlds in which $o$ is a bottleneck.

We claim three things. First, a policy whose input graph carries $\pi_o$, the mask $M$, and imputed means and variances will choose swaps that reduce realized makespan, meaning the makespan evaluated on the hidden true durations, more reliably than any policy fed a single point imputation. Second, training is stabilized by an asymmetric critic that sees the true $p$. Third, together these recover most of the gap between point-imputation L2S and an oracle L2S that sees all durations.

The neighborhood L2S uses, adjacent swaps on the critical path, is not defined when the critical path is uncertain. We therefore define the candidate move set as the union of critical-path swaps across the $K$ samples, weighted by $\pi$.

Each piece plays a distinct role, and each is borrowed from prior work:

  • Hindsight critic. It comes from UP-AAC. That method trains a constructive dispatching policy under branching job routes with a critic evaluated on the fully realized instance. UP-AAC never refines complete schedules and never imputes anything. We transplant its critic into an improvement MDP, where the obstacle is different: the dense per-step reward that improvement methods rely on is no longer computable from what the actor sees.
  • Mask as a separate input stream. This follows S4M, which feeds a binary missingness mask alongside latent features for forecasting rather than trusting imputed values.
  • Structured imputer. The imputer follows Classification with Low Rank and Missing Data and the mixture approach of Supervised learning from incomplete data via an EM approach. Both show that exploiting low-dimensional structure beats filling in means.

Research Program

Benchmark construction. Taillard durations are drawn independently and uniformly, so no imputer can recover a missing Taillard entry from the observed ones. We use this property deliberately and build two regimes.

In the unpredictable regime, we mask entries of the classic suites (Taillard, LA, ABZ, FT, SWV, ORB, YN, as used by L2S). Only distributional knowledge helps here, so any gain must come from uncertainty-aware search rather than recovery of the missing values.

In the structured regime, durations are generated as a low-rank job-by-machine product plus noise at Taillard sizes, so missing entries are partly predictable.

In both regimes we mask 10% to 50% of durations under two mechanisms. One is missing completely at random. The other is missing-not-at-random, where longer operations are more likely to be missing; this is the realistic and adversarial case.

Method. We extend the L2S encoder, which embeds the schedule's global structure and its job- and machine-order context, with per-operation inputs: $M$, the imputed mean and standard deviation, and $\pi_o$. The actor sees only these. The critic additionally sees the true $p$.

We compare two step rewards:

  • the realized change in makespan, computed on true durations and available only during training;
  • the sampled expected change, $\frac{1}{K}\sum_k \Delta C(\sigma,p^{(k)})$.

A conditional-value-at-risk variant scores the worst 20% of samples instead of their mean. All other training details follow L2S's $n$-step REINFORCE setup on instances up to 20×15.

Analysis. Beyond final gaps, we will measure how often the chosen swap actually improves realized makespan, as a function of $\pi_o$ for the swapped operations. We will also measure how calibrated $\pi$ is against the true critical path. These two curves show whether the policy learned to avoid edits whose benefit depends on durations nobody observed.

Baselines

Oracle and naive references. The upper reference is oracle L2S: the released L2S policy run on the true, complete durations. Every method is reported as the fraction of the gap it closes between the naive reference and this oracle. The naive reference is L2S run on mean-imputed durations, alongside zero-filling. Evidence from classification on Iris suggests mean imputation degrades sharply beyond about 25% missingness: accuracy drops toward 35–40% while EM stays above 80% (Ghahramani and Jordan). Whether that holds for makespan is part of what we test.

Impute-then-optimize. This baseline runs our own structured imputer's posterior mean, then L2S. It is the standard decoupled pipeline. Using our own imputer means any advantage of the proposal cannot be attributed to a better imputer. We also report a Kernel Point Imputation variant, Iterative Missing Data Imputation with Model Form Adaptation and Non-Missing Feature Supervision, on the smaller instances where its kernel solves are affordable.

Scenario-averaged L2S (strongest competitor). The released L2S policy is left unchanged. It proposes moves on the mean-imputed graph, but move acceptance and the incumbent schedule are judged by sampled expected makespan over the same $K$ completions. This baseline uses exactly our reward estimator with no retraining. It is the strongest competitor because, if it matches us, the policy-side contributions are unnecessary.

Retrained L2S. L2S is retrained on mean-imputed instances with realized-makespan reward and a standard critic. This is domain randomization without uncertainty features.

Classical comparisons. We run tabu search with scenario-averaged evaluation, and on instances up to 20×20 we run a sample-average CP-SAT model over the $K$ scenarios.

Fairness. All methods share data, masks, imputer, and $K$, and all receive equal wall-clock budgets on the same GPU. Because scenario evaluation multiplies critical-path cost by $K$, baselines that skip it receive proportionally more search steps. Learned baselines get the same training steps and hyperparameter search budget.

Reported numbers. The file reports that L2S beats OR-Tools CP-SAT by about 16% on 1000×40 instances in 4.1 minutes versus 1 hour. It also reports that L2S beats advanced tabu search under a 90-second limit (L2S). No reported result was found on Lacuna for L2S's per-suite Taillard gaps or for any learned improvement method under missing durations. We therefore reproduce oracle L2S ourselves. UP-AAC reports a 1.94% gap on small-to-medium Taillard-derived branching instances, but its uncertainty model differs from ours, so that number is not directly comparable.

What counts as beating the strongest competitor. The proposal wins only if it closes significantly more of the naive-to-oracle gap than scenario-averaged L2S, at 30% or higher missingness under the missing-not-at-random mechanism, across seeds.

Ablations. These isolate each ingredient: removing $\pi_o$, removing the mask stream, replacing the asymmetric critic with one that sees only what the actor sees, and setting $K=1$.

Why not just…?

Why not just impute the durations and run L2S? Decoupled pipelines accumulate error in forecasting (S4M) and degrade relative to joint methods in clustering (Leachable Component Clustering). Neither paper, however, studies scheduling. The specific mechanism we expect is different. A point imputation produces one critical path, and L2S spends its swaps on that path, which may be the wrong one. The analysis of swap success versus $\pi_o$ tests this directly. If impute-then-L2S closes most of the gap in the structured regime but not in the unpredictable one, the lesson is that imputation quality, not search, was the bottleneck.

Why not just evaluate moves over sampled completions with the existing L2S policy? This is a genuine threat. It is cheap, needs no training, and exploits exactly the batched evaluation we rely on. This is why it is our strongest baseline rather than a straw man. Even with good acceptance, a policy blind to uncertainty still proposes moves only on the mean-graph critical path. Our method's added value must therefore show up as better proposals, measured by the fraction of proposed swaps that improve realized makespan. If scenario-averaged L2S matches us, we will report that robustness to missing data in learned local search reduces to test-time reward estimation. That is a useful negative result.

Why not just retrain L2S on imputed instances? Domain randomization teaches a policy to tolerate noisy inputs but gives it no signal about which inputs are noisy. Cold Brew shows that standard graph networks degrade badly when neighborhood information is absent rather than represented (Cold Brew). This is evidence by analogy, not proof for our setting. The retrained-L2S baseline and the mask-removal ablation settle the question empirically.

Why not just use a robust exact model? Sample-average CP-SAT is included on small instances. However, OR-Tools CP-SAT already failed to find any feasible solution on 50×30 flexible job-shop instances within an hour (MIStar). Multiplying the model by $K$ scenarios makes larger scales impractical.

Decisive Checks

Three outcomes decide the proposal.

The first is gap closure on missing-not-at-random masks at 30–50% missingness, against scenario-averaged L2S, in both regimes. In the unpredictable Taillard regime, any win can come only from uncertainty-aware proposals, since imputation cannot help.

The second is the asymmetric-critic ablation. If removing the critic's access to true durations does not raise gradient variance or hurt the final gap, the UP-AAC transplant is unnecessary, and we drop it.

The third is generalization from 20×15 training instances to the largest suites under a fixed time budget. Computing $\pi$ costs a factor of $K$ more critical-path evaluation, and the benefit must survive that cost in wall-clock terms. If it does not, the right recommendation is the cheaper scenario-averaged baseline.