Bicester3D · Research Note
Material Changeovers as Cache Replacement
Treating a printer’s automated material feeder as a four-slot cache: measured changeover behaviour, an implementable optimal eviction rule, and batched operator guidance
Each machine in our three-printer FDM facility carries a four-slot automated material feeder, and each queued job requires one material–colour combination (SKU). The feeder therefore behaves as a four-entry cache over the SKU catalogue, and a changeover — the operator physically exchanging a spool — is a cache miss whose service cost is roughly thirty minutes of interrupted attention. Replaying sixty days of executed job sequences through cache simulation, unguided operation approximates least-recently-used (LRU) replacement at 13.4 changeovers per week fleet-wide.
Production scheduling offers an advantage general-purpose caches lack: the reference string is visible in advance, because each machine’s queue is known. Bélády’s optimal replacement rule — evict the entry whose next use is furthest in the future — is therefore directly implementable rather than merely a lower bound. Simulation shows it removes approximately 27% of changeovers at identical job order; deadline-respecting re-grouping of jobs adds only a few further points, because the queue sequencer already clusters same-material work. We describe the deployed system: a read-only planner that emits, per machine, the batched set of spool changes its visible queue requires, with optimal evictions, demand- frequency tie-breaks, and single-visit consolidation.
1. The changeover burden
A changeover in this facility means an operator walking to a machine, unloading a spool from the feeder, loading another, and confirming the change — approximately cs ≈ 30 minutes of attention including the context switch, and subjectively one of the most frequent interruptions in the working day. The demand side is diverse: 32 distinct SKUs appeared in the 60-day window studied, against 12 feeder slots fleet-wide.
Demand is strongly concentrated: the eight most frequent SKUs account for 75% of executed jobs (the leading SKU, a black PETG variant, alone accounts for 21%), with a long tail of 24 SKUs covering the remainder. Tail SKUs force compulsory changeovers — no replacement policy avoids the first load of a material that is genuinely required — so the design target is the avoidable component: evictions of SKUs that are needed again soon.
2. Measurement by cache simulation
Changeovers are not directly logged, so we measure them by simulation over ground truth we do hold: the exact sequence of executed jobs per machine, with each job’s SKU. Replaying each machine’s sequence through a k-entry cache model (k = 4) yields the changeover count a given replacement policy would have produced. Unguided operator behaviour is well approximated by LRU — the spool touched longest ago is the natural candidate when a slot must be freed.
| Policy (k = 4) | Changeovers / week | vs. LRU baseline |
|---|---|---|
| LRU (proxy for unguided operation) | 13.4 | — |
| Bélády-optimal eviction, identical job order | 9.8 | −27% |
| + job re-grouping within 24–72 h windows | 9.3–9.7 | −28 to −30% |
| + unbounded re-grouping (no deadlines — bound only) | 5.8 | −57% |
Two structural conclusions. First, eviction choice is the dominant recoverable term: most of the realistically achievable reduction arrives with no change to job order at all. Second, re-grouping adds little within deadline-respecting windows — the queue sequencer’s existing changeover-adjacency scoring has already captured most grouping value, and the unbounded −57% figure would require batching across weeks, which dispatch commitments preclude.
3. An implementable optimal policy
Bélády’s rule is normally unusable online because it requires future knowledge [1]; competitive analysis exists precisely to characterise how badly online policies like LRU must trail it [2]. A production scheduler escapes this frame: the “future” is each machine’s queue, which the scheduling system itself maintains. Within the horizon the queue is reliable (we use eight jobs, roughly one to two staffed days; the order beyond that is subject to periodic re-optimisation), the optimal rule is simply computable.
The deployed policy, per machine and per required load:
- Evict the slot SKU whose next use in the visible queue is furthest away, or absent entirely.
- Among slots absent from the visible queue, evict the SKU with the lowest 30-day demand frequency — keeping the head of the demand distribution resident against jobs not yet visible. This reproduces the effect of a standing assortment for the top SKUs without maintaining one explicitly.
Setups here are effectively sequence-independent in duration (any spool exchange costs roughly cs), which places the problem in the simplest cell of the setup-time scheduling taxonomy [3]; the structure worth exploiting is the cache identity, not setup asymmetry.
4. Batched execution
The second lever is not the changeover count but the interruption count. Discovering required changes one job start at a time converts every miss into a separate walk-up. The planner instead consolidates: for each machine it emits the full ordered list of changes its visible queue requires (“load X evicting Y before job n”), and distinguishes the subset needed imminently — so an operator visiting a machine for any reason performs every pending exchange in one visit. Guidance is advisory and read-only: the planner mutates nothing, and an ignored plan simply regenerates against the next snapshot.
5. Evaluation design
The planner deployed 2026-07-26. Because changeovers are not directly instrumented, evaluation reuses the measurement method: weekly LRU-baseline and actual-sequence simulations over the executed log, with the gap between realised and Bélády counts as the primary metric, alongside a count of multi-exchange visits (batching adoption). Expected effect at unchanged demand mix: from ≈13.4 to ≈9.5–10 changeovers per week, with fewer interruptions than exchanges.
Threats to validity
- LRU is an assumption about unguided operator behaviour, not a measurement of it; if real behaviour already anticipates the queue, the baseline overstates the recoverable margin.
- The simulation treats all exchanges as equal-cost; drying requirements for hygroscopic engineering materials make some exchanges costlier, which frequency tie-breaking only partially reflects.
- Queue visibility beyond a few jobs is subject to re-optimisation; the eight-job horizon bounds but does not eliminate plan churn.
6. Related and companion work
Replacement optimality is Bélády [1]; the online/offline gap is the classical subject of competitive analysis [2]; scheduling with setup considerations is surveyed in [3]. The routing and queueing context for this facility — including why assignment decisions are restricted to a least-capable-first class before any of the loadout logic discussed here applies — is described in the companion note, Scheduling a Small Heterogeneous Print Farm.
References
- L. A. Bélády, “A study of replacement algorithms for a virtual-storage computer,” IBM Systems Journal, 5(2), 1966, pp. 78–101.
- D. D. Sleator and R. E. Tarjan, “Amortized efficiency of list update and paging rules,” Communications of the ACM, 28(2), 1985, pp. 202–208.
- A. Allahverdi, C. T. Ng, T. C. E. Cheng and M. Y. Kovalyov, “A survey of scheduling problems with setup times or costs,” European Journal of Operational Research, 187(3), 2008, pp. 985–1032.