Graves-Willems

426. Graves-Willems

The guaranteed-service multi-echelon inventory model (Graves & Willems 2000). Each stage promises a service time (max lead time it’ll deliver in) to its downstream customer. Safety stocks are placed to make those service times achievable given bounded demand.

Used by Procter & Gamble, Hewlett-Packard, Intel, and most modern supply-chain network design software.

426.1. Setup

A network of stages (general topology — serial, assembly, distribution, or mixed). For each stage $𝑖$ :

$𝑇_{𝑖}$ : internal processing / production time at the stage
$𝑠_{𝑖}$ : outbound service time to downstream — what stage $𝑖$ commits to deliver in
$𝑆_{𝑖}$ : inbound service time from upstream — what stage $𝑖$ ’s suppliers commit to deliver in

Customer-facing stages have $𝑠 = 0$ (instant fulfillment) typically.

426.2. Net replenishment time

Stage $𝑖$ ’s net replenishment time — how long it must cover with safety stock:

𝜏_{𝑖} = 𝑆_{𝑖} + 𝑇_{𝑖} - 𝑠_{𝑖}

— inbound time + processing time − outbound promise time. If you can absorb supplier and processing delays without breaking your downstream promise, $𝜏_{𝑖}$ is small (less safety stock needed).

Constraint: $𝜏_{𝑖} \geq 0$ (can’t promise faster than the work takes).

426.3. Safety stock at each stage

Assume demand at the customer-facing stage is bounded by some upper-tail quantile (typical: $𝜇 + 𝑧 𝜎$ over the relevant interval). Then safety stock at stage $𝑖$ :

{SS}_{𝑖} = 𝑧 𝜎_{𝑖} \sqrt{𝜏_{𝑖}}

— the standard square-root-of-lead-time form, but with $𝜏_{𝑖}$ (net replenishment time) instead of pure lead time. The sqrt comes from the variance of demand over a time interval scaling linearly.

Total safety-stock cost across the network:

𝐶 = \sum_{𝑖} ℎ_{𝑖} 𝑧 𝜎_{𝑖} \sqrt{𝜏_{𝑖}}

426.4. Optimization

Decision variables: the inbound / outbound service times $𝑠_{𝑖}, 𝑆_{𝑖}$ at every stage.

Constraints:

$𝑠_{𝑖}, 𝑆_{𝑖} \geq 0$
$𝜏_{𝑖} = 𝑆_{𝑖} + 𝑇_{𝑖} - 𝑠_{𝑖} \geq 0$
$𝑆_{𝑖} = {max}_{𝑗 \in upstream (𝑖)} 𝑠_{𝑗}$ (the inbound time at $𝑖$ is the slowest outbound from any upstream feeder)
Customer-facing $𝑠$ fixed (often $𝑠 = 0$ )

Objective: minimize $\sum ℎ_{𝑖} \sqrt{𝜏_{𝑖}}$ .

Algorithm:

For trees / serial systems — dynamic programming, $𝑂 (| 𝑉 |^{2})$ time
For general networks — Magnanti et al. extension; MILP

426.5. Geometric intuition

Two extreme strategies for each stage:

$𝜏_{𝑖} = 0$ — hold no safety stock here, just pass the delay through (you must trust upstream / promise slower downstream)
$𝜏_{𝑖} = 𝑆_{𝑖} + 𝑇_{𝑖}$ — hold enough safety stock to fully decouple from upstream (you can promise $𝑠_{𝑖} = 0$ )

Optimal placement: tradeoff $\sqrt{𝜏_{𝑖}}$ costs across all stages — concentrate inventory where holding is cheap (upstream, low $ℎ_{𝑖}$ ) and decoupling pays off most.

426.6. Risk pooling appears naturally

If two downstream stages share an upstream stage, the upstream stage’s safety stock covers their combined variability — naturally captures risk pooling.

426.7. When to use

Generally — anywhere you have a multi-stage supply network and need safety-stock placement
Works for assembly (multiple upstream feed one downstream)
Works for distribution (one upstream feeds multiple downstream)
Works for general DAG networks

426.8. Limitations vs Clark-Scarf

Bounded (not stochastic) demand: the cost of $𝑧$ -quantile coverage rather than full distributional optimality
Service-time commitment assumed: real supply chains have stochastic delays even within commitments
See Stochastic-service for the relaxation

426.9. See also

Multi-Echelon — overview
Clark-Scarf — stochastic-demand alternative
Stochastic-service
Safety Stock
Risk Pooling