Multi-Echelon

443. 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.

443.0.1. Setup (two-echelon: warehouse $\to$ 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).

443.0.2. Cost model

Annual cost = sum across stages:

TC (𝑇_{𝑟}, 𝑇_{𝑤}) = \underset{retailer}{\underset{⏟}{\frac{𝑆_{𝑟}}{𝑇_{𝑟}} + ℎ_{𝑟} 𝑑 \frac{𝑇_{𝑟}}{2}}} + \underset{warehouse}{\underset{⏟}{\frac{𝑆_{𝑤}}{𝑇_{𝑤}} + ℎ_{𝑤} 𝑑 \frac{𝑇_{𝑤}}{2}}}

Constraint: $𝑇_{𝑤} = 𝑘 𝑇_{𝑟}$ for some integer $𝑘 \geq 1$ .

443.0.3. Unconstrained optimum (relax integer $𝑘$ )

If we ignored nesting, each stage would independently optimize:

𝑇_{𝑟}^{basic} = \sqrt{\frac{2 𝑆_{𝑟}}{ℎ_{𝑟} 𝑑}} 𝑇_{𝑤}^{basic} = \sqrt{\frac{2 𝑆_{𝑤}}{ℎ_{𝑤} 𝑑}}

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.

443.0.4. Roundy’s power-of-two policies

Restrict cycle times to powers of two of a base period: $𝑇_{𝑖} = 2^{𝑘_{𝑖}} 𝑇_{0}$ for integer $𝑘_{𝑖} \geq 0$ , where $𝑇_{0}$ is fixed (e.g., 1 day).

Then any two cycles are nested: a stage with $𝑘_{𝑖} = 3$ orders 8 base periods; another with $𝑘_{𝑖} = 5$ 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 $\leq \sqrt{2 / ln (2)} / (1 + 1 / \sqrt{2}) \approx 1.06$ ). So a 6% penalty is the worst case for using powers of two.

443.0.5. Algorithm

Compute unconstrained $𝑇_{𝑖}^{basic}$ at each stage.
Round each to the nearest power of two: $𝑇_{𝑖}^{*} = 2^{𝑘_{𝑖}^{*}} 𝑇_{0}$ where $𝑘_{𝑖}^{*} = round ({log}_{2} (𝑇_{𝑖}^{basic} / 𝑇_{0}))$ .
Compute resulting cost ${TC}^{*}$ and verify it’s within 6% of $\sum_{𝑖} \sqrt{2 𝑆_{𝑖} ℎ_{𝑖} 𝑑}$ .

443.0.6. Final formulas (two-stage, nested with $𝑇_{𝑤} = 𝑘 𝑇_{𝑟}$ )

Substitute $𝑇_{𝑤} = 𝑘 𝑇_{𝑟}$ into TC:

TC (𝑇_{𝑟}, 𝑘) = \frac{𝑆_{𝑟} + 𝑆_{𝑤} / 𝑘}{𝑇_{𝑟}} + (ℎ_{𝑟} + 𝑘 ℎ_{𝑤}) 𝑑 \frac{𝑇_{𝑟}}{2}

Optimize over $𝑇_{𝑟}$ for fixed $𝑘$ :

𝑇_{𝑟}^{*} (𝑘) = \sqrt{\frac{2 (𝑆_{𝑟} + 𝑆_{𝑤} / 𝑘)}{(ℎ_{𝑟} + 𝑘 ℎ_{𝑤}) 𝑑}}

{TC}^{*} (𝑘) = \sqrt{2 (𝑆_{𝑟} + 𝑆_{𝑤} / 𝑘) (ℎ_{𝑟} + 𝑘 ℎ_{𝑤}) 𝑑}

Now optimize over integer $𝑘 \geq 1$ — small search (typically $𝑘 \in {1, 2, 4, 8}$ ).

Example

Given (two-echelon: warehouse $\to$ retailer):

Retail demand: $𝑑 = 12000$ units/year
Retailer: $𝑆_{𝑟}$ = $50 / order, $ℎ_{𝑟}$ = $2 / unit / year
Warehouse: $𝑆_{𝑤}$ = $200 / order, $ℎ_{𝑤}$ = $1 / unit / year (echelon — added cost over nothing)

Step 1 — unconstrained $𝑇_{𝑖}^{basic}$ at each stage

𝑇_{𝑟}^{basic} = \sqrt{\frac{2 \cdot 50}{2 \cdot 12000}} \approx 0.0645 yr \approx 24 days

𝑇_{𝑤}^{basic} = \sqrt{\frac{2 \cdot 200}{1 \cdot 12000}} \approx 0.1826 yr \approx 67 days

Ratio $\frac{𝑇_{𝑤}^{basic}}{𝑇_{𝑟}^{basic}} \approx 67 / 24 \approx 2.83$ — roughly 3, but not an integer.

Step 2 — search nested integer $𝑘$

Try $𝑘 = 1, 2, 3, 4$ :

${TC}^{*} (𝑘) = \sqrt{2 (𝑆_{𝑟} + 𝑆_{𝑤} / 𝑘) (ℎ_{𝑟} + 𝑘 ℎ_{𝑤}) 𝑑}$ :

$𝑘$	$𝑆_{𝑟} + 𝑆_{𝑤} / 𝑘$	$ℎ_{𝑟} + 𝑘 ℎ_{𝑤}$	*${TC}^{} (𝑘)$**
1	50 + 200 = 250	2 + 1 = 3	$\sqrt{2 \cdot 250 \cdot 3 \cdot 12000} \approx 4243$
2	50 + 100 = 150	2 + 2 = 4	$\sqrt{2 \cdot 150 \cdot 4 \cdot 12000} \approx 3795$
3	50 + 67 = 117	2 + 3 = 5	$\sqrt{2 \cdot 117 \cdot 5 \cdot 12000} \approx 3742$
4	50 + 50 = 100	2 + 4 = 6	$\sqrt{2 \cdot 100 \cdot 6 \cdot 12000} \approx 3795$

Optimal $𝑘^{*} = 3$ (warehouse cycle is 3× the retailer cycle).

Step 3 — cycle times at $𝑘^{*} = 3$

𝑇_{𝑟}^{*} = \sqrt{\frac{2 (50 + 200 / 3)}{(2 + 3 \cdot 1) \cdot 12000}} = \sqrt{\frac{2 \cdot 117}{5 \cdot 12000}} \approx 0.0625 yr \approx 23 days

𝑇_{𝑤}^{*} = 3 \cdot 𝑇_{𝑟}^{*} \approx 68 days

Order quantities: retailer $𝑄_{𝑟}^{*} = 𝑑 𝑇_{𝑟}^{*} \approx 750$ , warehouse $𝑄_{𝑤}^{*} = 𝑑 𝑇_{𝑤}^{*} \approx 2280$ .

Step 4 — compare to basic EOQ at each stage independently

Treating the two stages independently (no nesting):

Retailer: ${TC}_{𝑟} = \sqrt{2 \cdot 50 \cdot 2 \cdot 12000} \approx 1549$
Warehouse: ${TC}_{𝑤} = \sqrt{2 \cdot 200 \cdot 1 \cdot 12000} \approx 2191$
Sum (independent): $3740/year

Multi-echelon nested: ${TC}^{*} (3) \approx 3742$ .

They almost coincide! The 6% Roundy bound is achieved here at 0.05% — the integer- $𝑘$ constraint costs almost nothing because $𝑇_{𝑤}^{basic} / 𝑇_{𝑟}^{basic} \approx 2.83$ 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 $𝑇_{𝑖} = 2^{𝑘_{𝑖}} 𝑇_{0}$ and the worst-case penalty stays below 6%. Predictable, nestable, near-optimal.