Pricing the Window Boundary: Rolling-Horizon Scheduling When Decisions Carry Over

Large factory schedules are often too big to solve in one piece. A common workaround is to cut the timeline into overlapping windows: solve the first few hours, commit the earliest decisions, slide forward, and repeat. This works well when what happens in one window barely constrains the next. Real shops break that assumption. A machine left configured for one product family at the end of a window charges a setup penalty to whatever the next window wants to run first, and work left unfinished becomes a backlog the next window inherits. Each window solver is blind to these carry-over costs, so it makes cheap-looking choices near its end that are expensive just past it.

We propose to give each window solver a price on the state it leaves behind. The price is a small table of terminal penalties, one for each machine's final configuration and for leftover work. It is estimated from the neighboring window's own solve and refined over a few cheap forward-and-backward sweeps, in which each window gets only a bounded solver budget. In two sentences: the quality lost by rolling-horizon scheduling with setup costs is concentrated at window boundaries and is caused by a missing cost-to-go on the machine state. Pricing that state from neighbor windows should recover most of the loss at lower compute than the obvious fix of enlarging the windows.

Core Claim and Where It Sits

The closest work is Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling, which we call L-RHO. It runs rolling-horizon optimization over flexible job shops of 600 to 2,000 operations. A flexible job shop is a set of jobs whose operations can each run on any of several compatible machines. Inside each window, L-RHO calls CP-SAT, Google's constraint-programming solver. Its contribution is a learned classifier that freezes machine assignments in the overlap that are predicted to stay the same, which cuts redundant work. L-RHO reports solve-time reductions of "up to 54%" and quality gains of "up to 21%". It also shows that cutting the problem along time beats cutting it by machines or operations, as Large Neighborhood Search does. That finding motivates our choice of a temporal cut.

L-RHO's objectives are makespan and start delay, and it models no cost that crosses a window boundary. It speeds up the inside of each window; it does nothing about how windows interact. We leave the window interiors alone and change only what each window is told about its successor. The two contributions are complementary and can be stacked.

The mechanism borrows from two other lines of work.

The first is A Fast Temporal Decomposition Procedure for Long-Horizon Nonlinear Dynamic Programming, which we call FOTD. In continuous problems, FOTD shows that overlapping time windows need not be solved to optimality. One inexact step per window, repeated over sweeps, converges at a rate that improves exponentially with overlap. This works because the effect of a boundary perturbation decays with distance from the boundary. The authors explicitly leave discrete and inequality-constrained problems open. We borrow the structure of FOTD (bounded inexact window solves, repeated sweeps, information exchanged through the overlap) but none of its guarantees, which depend on smoothness that scheduling lacks.

The second line is online optimization with switching costs. Capacity Provisioning Motivated Online Non-Convex Optimization Problem with Memory and Switching Cost shows that when backlog carries over and switching is expensive, purely reactive policies degrade. Good policies must scale their changes, for example by a factor of $\alpha^{1/4}$ for switching weight $\alpha>1$. This motivates a testable prediction: the benefit of boundary pricing should grow with setup-cost magnitude. Fairness-Regularized Online Optimization with Switching Costs proves that no online method has a finite competitive ratio against an unconstrained offline comparator once switching couples decisions over time. Two consequences follow for us. Our method has lookahead within a window, so it is not purely online. And we should report quality against a strong offline reference rather than promise worst-case bounds.

Research Program

The problem we study is long-horizon flexible job-shop scheduling with sequence-dependent setups. Operations belong to families, and switching a machine from family $a$ to family $b$ costs a setup time $s_{ab}$, which is scaled by a severity factor $\alpha$. Unfinished work at the end of a window becomes the next window's initial backlog.

For window $k$ with end time $\tau_k$, the window solver minimizes its usual objective plus a terminal term:

$$\min \; J_k(x) + \sum_{m} \pi_k(m, c_m(x)) + \lambda_k \, B_k(x).$$

Here $x$ is the window's schedule. $J_k$ is the in-window objective, meaning makespan contribution plus the setups incurred inside the window. $c_m(x)$ is the family configuration that machine $m$ is left in at $\tau_k$, and $\pi_k(m,c)$ is its price. $B_k(x)$ is the remaining processing work at the boundary, and $\lambda_k$ is its price. The terms are linear in indicator variables, so CP-SAT handles them natively.

The prices come from the successor window. After window $k+1$ has a tentative solution, we measure how its objective would change if machine $m$ started in configuration $c$ instead of the configuration it actually inherited. A cheap estimate re-costs the first block of window $k+1$'s schedule on each machine under each alternative starting configuration. This is a small, separable computation per machine. The estimate is exact for the first setup and only an approximation of downstream ripple effects. The backlog price comes the same way, from the slack observed on window $k+1$'s critical path.

A sweep proceeds as follows. We solve all windows forward with a fixed per-window CP-SAT time budget, update the prices from successors, and re-solve. Within a sweep, windows can be solved in parallel using the previous sweep's boundary states, which mirrors FOTD's parallel inexact steps. We stop after a small, fixed number of sweeps, and the total compute is matched to the baselines.

The analysis component is empirical, not a proof. We will measure the decay profile directly: perturb a boundary machine configuration and record how far into the next window the optimal schedule changes. This tells us whether a discrete analogue of FOTD's forgetting property holds on these instances, and it tells us the overlap at which plain rolling horizon would already suffice. We will also define boundary regret: the gap between rolling-horizon cost and a strong offline reference, attributed by time position. Our claim predicts that this regret is concentrated within a short distance of the boundaries and shrinks under pricing.

Baselines

The naive reference is plain rolling-horizon optimization with CP-SAT in each window and the setup cost included only inside windows. It uses the same window length, overlap, and per-window budget as our method. Everything is measured relative to this reference, and it is the setting in which we expect boundary regret to be largest.

The strongest existing method is L-RHO from Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling. It reports up to 54% solve-time reduction and up to 21% objective improvement over plain rolling horizon and other solvers on setup-free long-horizon instances. We found no reported result on Lacuna for L-RHO, or for any method in the file, on setup-coupled flexible job shops. We will therefore reimplement L-RHO's freezing classifier and retrain its look-ahead-oracle labels on our setup-coupled instances, giving it the same training-data budget we use. We will run it both alone and combined with pricing. Beating it means lower total cost (makespan plus setups) at equal wall-clock time on the 1,000-to-2,000-operation instances, across at least three setup-severity levels. Showing that pricing adds on top of L-RHO would establish complementarity.

The monolithic reference is CP-SAT on the full instance with a one-hour limit. Learning Memory-Enhanced Improvement Heuristics for Flexible Job Shop Scheduling reports two relevant results for CP-SAT without setups: it found no feasible solution within an hour on $50\times30$ instances, and it reached a 62.22% gap in an hour on $100\times10$ instances. The same paper's improvement heuristic, MIStar, reached 66.03% in under 16 minutes. We include MIStar, adapted so that its evaluation function includes setup costs, as the strongest non-decomposition learned method. We will report whether its zero-shot transfer still holds once setups enter the objective.

The ablations isolate the key ingredient, which is neighbor-estimated prices. We will compare against uniform prices, where every configuration change is charged the mean setup; against random prices; against a single sweep with no refinement; and against price estimation without the backlog term. If uniform prices match estimated ones, the contribution reduces to "add a constant terminal setup penalty," and we will report that.

Why not just…?

Why not just enlarge the overlap? This is the real threat. If the decay profile is short, a modestly longer overlap gives each window enough visibility, and no prices are needed. The experiment that settles it plots total cost against total compute for plain rolling horizon over a range of overlaps, against pricing at a fixed short overlap. Pricing only matters if its curve lies below the overlap curve. We expect that to happen mainly when the effect of a setup propagates further than CP-SAT can afford to see within its budget. The direct decay measurements will say in advance on which instances that is true.

Why not just retrain L-RHO with setup costs in the objective? Freezing decides which overlap variables to keep. It never tells window $k$ what its final state costs window $k+1$, so a retrained L-RHO still ends windows myopically. The stacked L-RHO-plus-pricing run tests this directly. If retrained L-RHO alone closes the boundary regret, our claim fails.

Why not just add a fixed setup penalty at the window end? This is the uniform-price ablation. It is cheap and may capture much of the gain when setup matrices are near-uniform. We therefore vary the heterogeneity of the setup matrix, from roughly uniform to strongly asymmetric. Estimated prices should only help as heterogeneity grows.

Why not just solve monolithically or use spatial decomposition? The file's evidence is against both at this scale: CP-SAT finds nothing feasible on 1,500-operation instances in an hour, and L-RHO found temporal decomposition significantly more effective than Large Neighborhood Search. We still run both, because setups could change that ranking.

Proposed Experiments

We will build setup-coupled instances by augmenting the L-RHO synthetic suite (600 to 2,000 operations) and the long-horizon Dauzère-Pérès and Paulli instances used there. Each operation is assigned a product family, and we generate setup matrices at three severities $\alpha$ and two heterogeneity levels. Brandimarte MK01–MK10 and the Hurink sets serve as setup-free controls. On these, pricing should give essentially no gain, and any gain there would indicate an artifact. The offline reference is the best solution found by long CP-SAT runs warm-started from every method, with the remaining gap reported.

The metrics are total cost, setup count, makespan, wall-clock time, and boundary regret by position. Every method gets the same hardware and the same total time budget, and every learned component gets equal tuning and training budget.

Three checks are decisive. First, boundary regret under plain rolling horizon must actually concentrate near boundaries; if it does not, the premise is wrong. Second, pricing must dominate overlap enlargement on the cost-versus-compute curve for at least the high-$\alpha$, high-heterogeneity setting. Third, the gain must increase with $\alpha$, as the switching-cost literature predicts, and vanish on the setup-free controls. If the second check fails everywhere, we will report the measured decay lengths as the useful outcome: they would show that overlap sizing, not pricing, is what setup-coupled rolling horizon needs.