439. Multi-Echelon
Relax one dimension from basic EOQ: number of echelons is no longer one. Inventory is held at multiple stages of a supply chain (warehouse → retailer, supplier → factory → distributor, etc.). Orders cascade up the chain, and each stage has its own setup and holding costs.
Key concept: echelon inventory at each stage, count not just on-hand but also all downstream inventory you’ve already paid to put in motion.
439.0.1. Setup (two-echelon: warehouse retailer)
- = customer demand rate at the retailer
- Retailer: setup , holding per unit per year, cycle time
- Warehouse: setup , echelon holding per unit per year (the added cost of holding at the warehouse vs nowhere), cycle time
The retailer pulls from the warehouse every . The warehouse re-orders from the upstream supplier every . Nesting requirement: must be an integer multiple of (otherwise the warehouse stocks fractionally, which is wasteful).
439.0.2. Cost model
Annual cost = sum across stages:
Constraint: for some integer .
439.0.3. Unconstrained optimum (relax integer )
If we ignored nesting, each stage would independently optimize:
This is just basic EOQ at each stage. But a non-integer ratio wastes capacity — the warehouse would carry partial cycles. Nesting is required for clean operation.
439.0.4. Roundy’s power-of-two policies
Restrict cycle times to powers of two of a base period: for integer , where is fixed (e.g., 1 day).
Then any two cycles are nested: a stage with orders 8 base periods; another with orders every 32 base periods the second is always a multiple of the first.
Roundy’s 98% theorem: the best power-of-two policy achieves at least 98% of the unconstrained optimum (worst-case cost ratio ). So a 6% penalty is the worst case for using powers of two.
439.0.5. Algorithm
- Compute unconstrained at each stage.
- Round each to the nearest power of two: where .
- Compute resulting cost and verify it’s within 6% of .
439.0.6. Final formulas (two-stage, nested with )
Substitute into TC:
Optimize over for fixed :
Now optimize over integer — small search (typically ).
Example
Given (two-echelon: warehouse retailer):
- Retail demand: units/year
- Retailer: = $50 / order, = $2 / unit / year
- Warehouse: = $200 / order, = $1 / unit / year (echelon — added cost over nothing)
Step 1 — unconstrained at each stage
Ratio — roughly 3, but not an integer.
Step 2 — search nested integer
Try :
:
| 1 | 50 + 200 = 250 | 2 + 1 = 3 | |
| 2 | 50 + 100 = 150 | 2 + 2 = 4 | |
| 3 | 50 + 67 = 117 | 2 + 3 = 5 | |
| 4 | 50 + 50 = 100 | 2 + 4 = 6 |
Optimal (warehouse cycle is 3× the retailer cycle).
Step 3 — cycle times at
Order quantities: retailer , warehouse .
Step 4 — compare to basic EOQ at each stage independently
Treating the two stages independently (no nesting):
- Retailer:
- Warehouse:
- Sum (independent): $3740/year
Multi-echelon nested: .
They almost coincide! The 6% Roundy bound is achieved here at 0.05% — the integer- constraint costs almost nothing because was already close to a small integer (3). This is the Roundy theorem at work: with two stages, the worst-case nesting penalty is bounded by 6%, and in practice it’s usually much less.
The deeper takeaway: power-of-two policies generalize this beyond two stages — at any number of echelons, restrict each cycle to and the worst-case penalty stays below 6%. Predictable, nestable, near-optimal.