MEIO Theory — Multi-Echelon Inventory Optimisation¶
Chapter summary
This chapter provides a rigorous technical treatment of the MEIO algorithm in Mirabelle. It covers multi-echelon network structure, the greedy marginal value allocation algorithm, BOM/kit dependency handling, reverse logistics, Erlang-B asset mode, the Rust optimizer architecture, and the scenario system. Developers and technically-inclined planners will find implementation details here that are not covered in the User Guide.
1. Why single-echelon is insufficient¶
A single-echelon model treats each (item, site) pair independently. It sets:
where \(L_i\) is the nominal lead time for that site. This ignores the fact that when a central warehouse is out of stock, the regional warehouse experiences a longer effective lead time — it must wait for the central warehouse to be replenished before receiving its order.
The Clark–Scarf insight¶
Figure: a central warehouse stockout lengthens the downstream node's effective lead time by the expected wait \(W_{\text{upstream}}\); holding safety stock upstream shortens that wait for every downstream node.
flowchart LR
CW["Central Warehouse<br/>(committed buffer b_cw)"] -->|"leg_lead_time L_leg"| RDC["Regional Warehouse"]
RDC -->|"leg_lead_time L_leg"| FIELD["Field / Retail Site"]
CW -.->|"out of stock → wait W"| RDC
RDC -.->|"out of stock → wait W"| FIELD
EFF["L_eff = L_leg + W_upstream<br/>(recomputed after each commit)"]
RDC -.-> EFF
Clark and Scarf (1960) showed that in a serial two-echelon system:
- The downstream node's effective lead time is: \(L_{\text{eff}} = L_{\text{leg}} + W_{\text{upstream}}\) where \(W_{\text{upstream}}\) is the expected wait for the upstream node to have stock.
- The safety stock at the upstream node reduces \(W\) for all downstream nodes.
- Optimizing independently ignores these dependencies and consistently over-stocks some nodes while under-stocking others.
For general networks (trees, divergent, with BOM dependencies), the serial Clark–Scarf decomposition does not apply. Mirabelle uses a greedy marginal value heuristic that handles arbitrary topologies.
2. Network topology¶
Echelon structure¶
A typical supply network in Mirabelle has three levels:
Central Warehouse (site type: DC)
│ [TRANSFER route, leg_lead_time = 2 weeks]
├─► Regional Warehouse A (site type: RDC)
│ │ [TRANSFER route, leg_lead_time = 1 week]
│ ├─► Field/Retail Site 1
│ └─► Field/Retail Site 2
└─► Regional Warehouse B
│
└─► Field/Retail Site 3
The route table encodes each arc with:
route_type:'BUY','TRANSFER','MAKE','RETURN', or'REPAIR'leg_lead_time:(lead_time + transit_time + pick_pack_time) / 7weekssource_site_id→dest_site_id
For each (item, site) SKU, the primary replenishment route is the lowest-priority
BUY/TRANSFER/MAKE route (DISTINCT ON (item_id, site_id) ORDER BY priority ASC).
Transfer sources¶
The CTE transfer_sources in _load_sku_records aggregates the full list of
source sites for each (item, site) pair as a JSONB array. This array is
passed to the Rust optimizer so it can propagate wait-time changes through
the network after each commit.
Indirect demand at warehouse nodes¶
Regional and central warehouses typically have no direct customer demand —
their demand is derived from downstream sites' requirements. The indirect_demand
table stores this accumulated demand. The refresh_item_indirect_stats
function aggregates it into item.demand_rate, dmd_stddev, and mad for
warehouse-level nodes.
3. The greedy marginal value algorithm¶
Phase 1 — Absolute stock lower bounds (ASL)¶
Before the greedy loop begins, any SKU with sku_min_fill_rate > 0 or
sku_min_sl_qty > 0 receives a pre-committed buffer sufficient to meet
that floor. This prevents the greedy loop from inadvertently leaving a
critical SKU below its contractual minimum.
for each SKU with sku_min_fill_rate > 0:
b_min = solve: FR(b_min) >= sku_min_fill_rate
committed_buffer[SKU] = b_min
for each SKU with sku_min_sl_qty > 0:
committed_buffer[SKU] = max(committed_buffer[SKU], sku_min_sl_qty)
Phase 2 — Marginal value initialisation¶
Before the main loop, compute_marginal_value() is called for every SKU.
The marginal value (MV) is the fill-rate gain per unit of currency
invested in the next buffer increment:
where: - \(G_i\) is the set of target groups (segments) that item \(i\) belongs to, - \(w_{ig}\) is the weight of item \(i\) in group \(g\) (currently uniform within a segment), - \(FR(b)\) is the fill-rate at buffer level \(b\) for item \(i\)'s demand distribution over its effective lead time, - \(\Delta b_i\) is the jump size for item \(i\) (see below), - \(c_i\) is the unit cost of item \(i\).
Jump size heuristics¶
Two jump sizes are used:
- Initial jump — a larger step to quickly move away from zero buffer.
- Further jump (precision jump) — smaller refinement steps.
When precision_jump > 0, a long-jump heuristic is enabled:
if the current fill rate is below big_jump_threshold (default 0.95), the
optimizer estimates in one step the buffer level needed to reach
big_jump_threshold, commits it, and then switches to small steps. This
cuts optimizer iterations by 30–50 % on scenarios with uniform fill-rate
targets.
Phase 3 — The greedy loop¶
Figure: the three-phase MEIO optimisation loop — ASL floors, marginal-value ranking, parallel Rayon evaluation, serial commit, and wait-time propagation back into the network.
flowchart TD
ASL["Phase 1 — ASL lower bounds<br/>(sku_min_fill_rate / sku_min_sl_qty)"] --> INIT["Phase 2 — compute_marginal_value<br/>for every SKU"]
INIT --> RANK["Step 1 — rank SKUs by<br/>marginal value (desc)"]
RANK --> TOP["Take top N = greedy_candidates"]
TOP --> PAR["Step 2 — parallel eval (Rayon)<br/>new_FR, new_MV on &SkuStore"]
PAR --> COMMIT["Step 3 — serial commit<br/>committed_buffer += jump"]
COMMIT --> PROP["Step 4 — propagate wait_time<br/>to downstream SKUs, recompute MV"]
PROP --> CHECK{"all groups meet<br/>fill_rate_target AND<br/>max_budget?"}
CHECK -->|"no"| RANK
CHECK -->|"yes"| DONE["Write meio_results /<br/>meio_group_results"]
repeat until all groups satisfy fill_rate_target AND max_budget:
Step 1 — Select candidates
Sort all eligible SKUs by marginal_value (descending)
Take top N = greedy_candidates
Step 2 — Parallel evaluation (Rayon)
For each candidate i in parallel (immutable &SkuStore refs):
new_FR_i = FR(committed_buffer_i + jump_i)
new_MV_i = compute_marginal_value(i, new state)
Step 3 — Serial commit
For each evaluated candidate:
committed_buffer_i += jump_i
current_fill_rate_i = new_FR_i
targets.commit(group, delta_fill_rate, delta_cost)
Step 4 — Propagate wait-time changes
For each committed SKU:
recompute wait_time for all downstream SKUs that depend on it
recompute MV for those downstream SKUs
Why greedy is near-optimal¶
Figure: the fill-rate function FR(b) is non-decreasing and concave — each extra buffer unit yields a smaller fill-rate gain, so the marginal-value ranking always picks the highest-return next unit.
quadrantChart
title Fill rate vs safety-stock investment (concave FR curve)
x-axis "Low buffer" --> "High buffer"
y-axis "FR = 0.50" --> "FR = 1.00"
quadrant-1 "Diminishing returns"
quadrant-2 "Under-stocked"
quadrant-3 "Starved"
quadrant-4 "Over-invested"
"small b, low FR": [0.15, 0.55]
"mid b, steep gain": [0.40, 0.90]
"near target 0.95": [0.62, 0.97]
"knee (max curvature)": [0.50, 0.94]
"large b, flat": [0.85, 0.995]
The fill-rate function \(FR(b)\) is:
- Non-decreasing: more buffer always helps or is neutral.
- Concave: the marginal gain from each additional unit of buffer decreases as \(b\) increases.
These properties mean the greedy marginal value algorithm is optimal for a single group (Federgruen and Zipkin, 1984). For multiple groups the greedy approach is a heuristic, but it is very close to optimal in practice because group membership is often disjoint and budget constraints are non-binding for most groups.
4. Fill-rate formulas per distribution family¶
The Rust module distributions.rs implements the fill-rate integral for each
family. Key implementations:
Normal¶
Computed using Horner's method polynomial approximations for \(\phi\) and \(\Phi\).
Poisson¶
For integer buffers, the complementary CDF sum:
where \(F_{\text{Poi}}\) is the Poisson CDF evaluated using the regularized incomplete gamma function.
Gamma¶
Log-Normal, Weibull¶
Numeric integration of \(\int_b^{\infty}[1-F(x)]\,dx\) using 64-point Gauss–Laguerre quadrature shifted to the appropriate domain.
Negative Binomial¶
Recurrence-based CDF evaluation using the Pascal triangle identity.
5. BOM and kit dependency¶
The service-level multiplication rule¶
If an assembly kit requires components \(B_1, B_2, \ldots, B_n\), the kit fill rate (probability that all components are available) is:
This assumes component availabilities are independent. For assemblies sharing a supply chain, this is a conservative approximation (common-cause supply disruptions create positive correlation, making the true kit FR lower).
Wait-time propagation through BOM¶
Each component SKU contributes to the wait time of its parent assemblies. If component \(j\) has wait time \(W_j\) (expected delay to fulfil an order when out of stock), the parent assembly's wait time includes a term:
where \(q_j\) is the quantity per assembly. The Rust optimizer.rs propagates
wait-time changes upward through the BOM graph after each commit. The
components_cte, kits_cte, and parents_cte in the _load_sku_records
SQL query serialize this graph as JSONB arrays.
Cycle detection in circular BOMs¶
In some MRO configurations, Item A can be repaired using a part from Item A itself (cannibalization). The BOM graph can have cycles. The Rust optimizer includes cycle-breaking logic: during wait-time propagation, any node already in the current propagation stack is skipped. This prevents infinite recursion while still propagating most of the dependency signal.
6. Reverse logistics¶
Net demand reduction¶
When a RETURN or REPAIR route exists for (item, site), the effective demand that must be sourced from new production or external suppliers is reduced:
- \(\rho\) = return rate (fraction of demand units that return to the network)
- \(\gamma\) = repair yield (fraction of returned units successfully restored)
The product \(\rho \gamma\) is the net recovery rate. If 60 % of parts return and 80 % of those are repairable, \(\rho\gamma = 0.48\) — only 52 % of gross demand must be sourced externally.
Repair turnaround variability¶
Repair turnaround time \(T_r\) adds to effective lead time. Modelled as a random variable with mean \(\bar{T}_r\) and coefficient of variation \(CV_r\):
The default parameters are stored in scenario.parameters:
- default_repair_tat_mean = 4.0 weeks
- default_repair_tat_cv = 0.3
Per-item values come from REPAIR/RETURN route attributes via
_load_repair_params_from_routes; there are no per-segment repair overrides
(return_rate, repair_yield, repair_tat_mean, repair_tat_cv, wip_qty
were removed from segment parameter sets — they are sourced exclusively from
master.route RETURN/REPAIR rows, with the default_* globals as fallback).
Circuit-breaking for repair loops¶
A repair route from Site B to Site A that involves the same item creates a
supply loop (Item A → repair at Site B → return to Site A). The runner
detects loops in _load_repair_params_from_routes() using a depth-limited
BFS and breaks them before passing the graph to Rust.
7. Asset mode — Erlang-B pool sizing¶
When to use asset mode¶
Asset mode applies to high-value, low-volume repairable assets where demand is driven by failure events, not customer pull. Examples: - Aircraft engines - Industrial machine tools - High-value test equipment
For these items, "demand" means a failure requiring a spare unit while the failed unit is under repair. The operating pool size \(C\) (number of spare units) determines the probability that all assets are simultaneously in repair (blocking probability).
The Erlang-B formula¶
The Erlang-B (M/G/c/c) loss formula gives the blocking probability:
where \(A = \lambda \cdot \bar{R}\) is the offered load (Erlangs): - \(\lambda\) = failure rate (assets failing per week) - \(\bar{R}\) = mean repair turnaround time (weeks)
Availability is the complement:
Erlang-B computation¶
The Rust module math.rs evaluates Erlang-B using a numerically stable
iterative formula that avoids factorial overflow:
Starting from \(B(A,0) = 1\) and iterating up to \(C\), this recurrence is stable for any \(A\) and \(C\).
Python path for asset scenarios¶
Asset-mode scenarios (service_level_type = 'availability') bypass the Rust
optimizer and are handled in _run_causal_asset_scenario() within
meio_runner.py. This function:
- Loads deployment data from
causal_asset_deployment(assets by site). - Loads failure rates and repair turnaround times from
causal_failure_rate. - For each (item, site) pair, computes \(A = \lambda\bar{R}\).
- Increments \(C\) from 0 until \(\text{Avail}(C) \geq \text{target}\).
- Records
committed_buffer = C,fill_rate = Avail(C).
8. The Rust optimizer¶
Empirical-distribution cycle-stock baseline (V3)¶
When use_empirical_distributions = true, DistributionType::empirical_mean()
(files/MEIO_v3/src/distributions.rs) returns the empirical demand-over-lead-time
sample mean, and compute_mv_recursive (files/MEIO_v3/src/marginal.rs) uses it
as the cycle-stock baseline:
The empirical demand-over-LT distribution is built from master.demand_actuals
summed over the actual replenishment lead time (not the planned one). Using
the planned-LT baseline alongside an empirical distribution built over actual LT
creates a consistency break: the distribution says "need 72 for 95 %" while the
planned-LT baseline says "cycle stock = 4", so the marginal value of additional
safety stock is ≈ 0, the SKU is marked dead, and rop stays at 0. The empirical
mean fixes this by making the baseline consistent with the distribution's horizon.
The tgt_max ceiling (Max Safety Qty / Max Cover) also uses this baseline:
tgt_max = min(sku_max_sl_qty, sku_max_sl_slices_qty) + effective_total_lt_fcst
(= sku_max_sl_qty + empirical_mean when empirical is active), enforced as a
continuous ceiling across ASL, initial jump, greedy loop, and endgame.
Architecture rationale¶
The greedy marginal value loop over thousands of SKUs with full fill-rate integral evaluation per iteration is CPU-intensive. For a realistic 5 000 SKU portfolio with \(\text{greedy\_candidates} = 8\):
- 1 000 outer iterations (typical)
- 8 candidates evaluated per iteration
- Each evaluation: lead-time scaling + CDF integral computation
This is approximately 8 million fill-rate evaluations, with each involving numerical integration. Python would take minutes; Rust with Rayon takes seconds.
PyO3 interface¶
The Rust extension is built with maturin and exposes three entry points:
# Single-scenario call
result_json = meio_optimizer.run_optimization(skus_json, config_json, targets_json)
# Batch call (used in production)
results_json = meio_optimizer.run_optimization_batch(batches_json)
The GIL is released via py.allow_threads() before any Rayon work begins.
pyo3-log reacquires the GIL only for log record emission, which occurs
outside the hot compute loop.
Source file responsibilities¶
| File | Responsibility |
|---|---|
lib.rs |
PyO3 exports, GIL management |
sku.rs |
SkuRecord struct, SkuStore (HashMap), JSON deserialisation |
optimizer.rs |
Three-phase optimization loop |
marginal.rs |
compute_marginal_value() — pure function, parallelised |
target.rs |
TargetDictionary — group fill-rate and budget tracking |
distributions.rs |
Fill-rate formulas for all 6 distribution families |
math.rs |
CDFs: Normal, Poisson, Gamma, LogNormal, Weibull, NegBinomial; Erlang-B |
config.rs |
MeioConfig, GroupTarget, OptimizationScope |
Two-level parallelism¶
Level 1 — Between scenarios:
batches.par_iter() — each scenario is an independent Rayon task. Scenarios
share no data (each has its own SkuStore clone). Scales linearly with
scenario count.
Level 2 — Within a scenario:
Each greedy iteration:
1. Select top-N candidates [serial]
2. compute_marginal_value × N [Rayon par_iter — immutable &SkuStore]
3. Commit results [serial — &mut SkuStore writes]
The Rust borrow checker statically enforces this: compute_marginal_value()
takes &SkuStore (shared immutable reference), making it impossible to write
during the parallel evaluation phase. All writes happen in the single-threaded
commit phase.
Lock-free design¶
There are no runtime synchronization primitives (Mutex, RwLock, Arc,
atomics, channels, DashMap) for user data. Thread safety is enforced at
compile time by Rust's ownership model. This eliminates all lock contention and
makes performance predictable under high parallelism.
Approximation — top-N pre-commit snapshot¶
The top-N candidates are all evaluated against the pre-commit snapshot of the SkuStore. Candidates 2 through N therefore see slightly stale marginal values (they do not know candidate 1 has already consumed some budget).
This approximation is intentional and negligible for large portfolios: the ranking at iteration \(k+1\) is almost identical regardless of whether the correct or stale snapshot is used. The parallelism benefit (N evaluations in parallel rather than sequential) far outweighs the tiny quality loss.
9. Scenario system¶
meio_scenarios table structure¶
scenario_id BIGSERIAL PRIMARY KEY
name TEXT -- e.g. "Base Case", "High Service"
is_base BOOLEAN -- exactly one base scenario per tenant
param_overrides JSONB -- {demand_multiplier, lead_time_multiplier,
-- fill_rate_target, config_overrides,
-- sku_overrides, group_target_overrides}
The param_overrides JSONB provides a flexible override hierarchy. The
override resolution order (most to least specific) is:
1. Per-segment overrides (config_meio_parameter_set linked to the SKU's segment)
fill_rate_target, max_budget, sku_min_fill_rate, sku_max_fill_rate,
sku_min_sl_qty, sku_max_sl_qty, sku_min_sl_slices, sku_max_sl_slices,
use_existing_inventory, demand_multiplier, lead_time_multiplier,
line_fill_rate, consider_eoq, lt_stddev_multiplier (API only)
NOTE: return_rate/repair_yield/repair_tat_*/wip_qty are NO LONGER
per-segment — sourced exclusively from master.route RETURN/REPAIR rows.
2. Global scenario overrides (param_overrides JSON)
sku_overrides: {demand_multiplier, ...} ← wins over per-segment
config_overrides: {line_fill_rate, ...}
group_target_overrides: {group_name: {fill_rate_target, ...}}
3. Item-level defaults (item table)
4. Route-level defaults (route table)
5. Global MEIO parameters (scenario.parameters, parameter_type='meio')
Pipeline linkage¶
Every pipeline is linked to at most one meio_scenario_id via
scenario_pipeline. When the MEIO step runs:
- If
meio_scenario_id IS NOT NULL: run that single scenario. - If
meio_scenario_id IS NULL: run all enabled scenarios (fallback for backward compatibility).
This design means: - Normal operation runs one scenario per pipeline run (fast, predictable). - Comparative analysis can run multiple scenarios in a single batch call (Rayon parallelises them).
What-if scenario analysis¶
A typical comparative analysis setup:
| Scenario | fill_rate_target | demand_multiplier | Description |
|---|---|---|---|
| Base Case | 0.95 | 1.0 | Current policy |
| High Service | 0.99 | 1.0 | Best-in-class service |
| Demand +20% | 0.95 | 1.2 | Demand growth scenario |
| Lean | 0.90 | 1.0 | Cost reduction scenario |
Running all four in one batch invocation takes only marginally longer than running one, because Rayon Level 1 parallelism covers the overhead.
10. Configuration reference¶
All MEIO configuration lives in scenario.parameters with
parameter_type = 'meio' and is_default = TRUE.
| Parameter | Default | Effect |
|---|---|---|
meio_parallel_workers |
0 (auto) |
Rayon thread-pool size. 0 = all CPUs. |
greedy_candidates |
3 |
SKUs evaluated per greedy iteration. Recommended 3–16. |
distribution_threshold |
25 |
Min observations for parametric fit; fewer → Normal fallback. |
precision_jump |
0.0 |
When > 0, enables long-jump heuristic. |
big_jump_threshold |
0.95 |
Fill-rate target for long-jump. |
consider_eoq |
true |
Snap buffer increments to EOQ multiples. |
line_fill_rate |
true |
True = line fill rate. False = unit fill rate. |
Figure: when consider_eoq = true, the committed safety-stock buffer is snapped up to the next EOQ multiple, so replenishment tops up to the order-up-to level S = Q (EOQ) on each cycle.*
flowchart LR
DLT["Demand over lead time<br/>d_weekly × L_weeks"] --> ROP["Reorder point<br/>ROP = d·L + SS"]
ROP --> TRIG["On-hand hits ROP"]
TRIG --> ORDER["Place order Q* = sqrt(2DS/H)<br/>(from item.eoq write-back)"]
ORDER --> SNAP["Snap SS to EOQ multiple<br/>b_snapped = ceil(b / Q*) × Q*"]
SNAP --> S["Order-up-to level S<br/>= Q* + SS_snapped"]
S --> ARRIVE["Order arrives after L<br/>on-hand → S"]
| default_return_rate | 0.0 | Return rate when no RETURN route defines one. |
| default_repair_yield | 1.0 | Repair yield when no REPAIR route defines one. |
| default_repair_tat_mean | 4.0 | Repair turnaround mean (weeks). |
| default_repair_tat_cv | 0.3 | Repair turnaround CV. |
| default_fill_rate_target | 0.95 | Group target when no segment override exists. |
| default_max_budget | 1e12 | Group budget cap when no override exists. |
11. Output tables¶
meio_results¶
One row per (scenario_id, item_id, site_id):
| Column | Description |
|---|---|
scenario_id |
MEIO scenario that produced this row |
item_id |
Item |
site_id |
Site (warehouse or field location) |
committed_buffer |
Safety stock quantity (units) |
fill_rate |
Achieved fill rate at committed_buffer |
marginal_value |
MV at final buffer — indicates remaining improvement potential |
inventory_value |
committed_buffer × unit_cost |
wait_time |
Expected wait (weeks) experienced by downstream nodes |
leg_lead_time |
Physical lead time of the primary replenishment route |
run_at |
Timestamp of the optimization run |
meio_group_results¶
One row per (scenario_id, segment):
| Column | Description |
|---|---|
scenario_id |
MEIO scenario |
segment_id |
Segment (target group) |
achieved_fill_rate |
Weighted average fill rate across all SKUs in this segment |
budget_consumed |
Total inventory_value allocated to this segment |
target_met |
Boolean: did the group reach its fill_rate_target? |
12. Performance characteristics¶
Timing profile (10 000 SKUs, 3 scenarios)¶
| Step | Typical time |
|---|---|
refresh_item_indirect_stats |
1–3 s (5 batch queries) |
_load_sku_records SQL |
3–8 s (one large CTE) |
| Build scenario batches | < 0.1 s |
| Rust optimizer | 5–60 s (depends on SKU count, candidates, workers) |
| Save results | 0.5–2 s |
Tuning for large datasets¶
- Increase
greedy_candidates(8–16) on servers with many CPU cores and SKU counts > 5 000. - Set
meio_parallel_workersexplicitly if the default Rayon thread count causes memory pressure (each thread holds partial SkuStore copies during evaluation). - Enable
precision_jump > 0(try 0.5–1.0) to cut iterations 30–50 % on scenarios with uniform fill-rate targets. VACUUM ANALYZEondemand_actualsandindirect_demandafter large ETL runs to keep query planner statistics current.
Cross-references: Distribution Fitting · Safety Stock · K-Curve · EOQ · MEIO User Guide