Wagner–Whitin

445. Wagner–Whitin

445.1. Wagner-Whitin (finite horizon, time-varying demand)

Relax two dimensions from basic EOQ at once: planning horizon is now finite, and demand is no longer constant — it varies period by period (still known and deterministic). No closed-form $𝑄^{*}$ ; the answer is a schedule of when to order, found by dynamic programming.

445.1.1. Setup

Periods $𝑡 = 1, 2, \dots, 𝑇$ (e.g., months in a finite production plan).
Known demand $𝑑_{𝑡}$ in each period.
Order cost $𝑆$ per order placed (independent of size).
Holding cost $ℎ$ per unit carried one period forward.
Decision: in which periods to place orders, and how much each order covers.

445.1.2. Zero-inventory ordering (ZIO) property

Claim: In an optimal Wagner-Whitin schedule, an order is placed only when starting inventory is zero.

Proof sketch: If you start a period with leftover stock and then order more, you could have ordered less the previous time and placed the same total order one period later — saving holding cost without changing the order count. So orders always coincide with the inventory hitting zero.

Consequence: each order covers a consecutive block of periods $[𝑗, 𝑘]$ (for some $𝑗 \leq 𝑘$ ). The decision space collapses from “how much in each period” to “which blocks to use” — a much smaller problem solvable by DP.

445.1.3. Cost of a single order block $[𝑗, 𝑘]$

If we order in period $𝑗$ to cover demands $𝑑_{𝑗}, 𝑑_{𝑗 + 1}, \dots, 𝑑_{𝑘}$ :

Order cost: $𝑆$ (one order).
Holding cost: each unit consumed in period $𝑡$ ( $𝑗 \leq 𝑡 \leq 𝑘$ ) sat in inventory for $𝑡 - 𝑗$ periods. Total holding for the block:

Hold (𝑗, 𝑘) = ℎ \sum_{𝑡 = 𝑗}^{𝑘} (𝑡 - 𝑗) 𝑑_{𝑡}

Block cost:

Cost (𝑗, 𝑘) = 𝑆 + ℎ \sum_{𝑡 = 𝑗}^{𝑘} (𝑡 - 𝑗) 𝑑_{𝑡}

445.1.4. DP recursion

Let $𝐹 (𝑡)$ = minimum cost to cover demand for periods $1, \dots, 𝑡$ . Boundary: $𝐹 (0) = 0$ .

For each $𝑡$ , the last order block ends at $𝑡$ and starts at some $𝑗 \in {1, \dots, 𝑡}$ :

𝐹 (𝑡) = {min}_{𝑗 = 1}^{𝑡} [𝐹 (𝑗 - 1) + Cost (𝑗, 𝑡)]

Solve forward: $𝐹 (1), 𝐹 (2), \dots, 𝐹 (𝑇)$ . Track the argmin $𝑗^{*} (𝑡)$ at each step to reconstruct the schedule.

445.1.5. Algorithm

Compute “Cost $(𝑗, 𝑡)$ ” for all pairs $𝑗 \leq 𝑡$ .
Forward pass: for each $𝑡$ , compute $𝐹 (𝑡)$ and store $𝑗^{*} (𝑡)$ .
Backtrack from $𝑇$ : order in $𝑗^{*} (𝑇)$ covering $[𝑗^{*} (𝑇), 𝑇]$ , then recurse on $𝐹 (𝑗^{*} (𝑇) - 1)$ .

Complexity: $𝑂 (𝑇^{2})$ in the number of periods.

Example

Given (small 4-period example):

4 periods with demands $𝑑 = (10, 20, 5, 15)$
Order cost: $𝑆$ = $50 / order
Holding cost: $ℎ$ = $1 / unit / period

Step 1 — block costs

$Cost (𝑗, 𝑡) = 𝑆 + ℎ \sum_{𝑠 = 𝑗}^{𝑡} (𝑠 - 𝑗) 𝑑_{𝑠}$ :

$𝑗 ↓$ \ $𝑡 \to$	1	2	3	4
1	50	50 + 20 = 70	70 + 10 = 80	80 + 45 = 125
2	—	50	50 + 5 = 55	55 + 30 = 85
3	—	—	50	50 + 15 = 65
4	—	—	—	50

Each cell is the cost of one order placed in period $𝑗$ that covers demand through period $𝑡$ .

Step 2 — DP forward pass

$𝐹 (0) = 0$ .

$𝐹 (1) = 𝐹 (0) + Cost (1, 1) = 0 + 50 = 𝟓𝟎$ . ( $𝑗^{*} (1) = 1$ )

$𝐹 (2) = min {\begin{cases} 𝐹 (0) + Cost (1, 2) = 0 + 70 = 70 \\ 𝐹 (1) + Cost (2, 2) = 50 + 50 = 100 \end{cases} = 𝟕𝟎$ . ( $𝑗^{*} (2) = 1$ )

$𝐹 (3) = min {\begin{cases} 𝐹 (0) + Cost (1, 3) = 80 \\ 𝐹 (1) + Cost (2, 3) = 50 + 55 = 105 \\ 𝐹 (2) + Cost (3, 3) = 70 + 50 = 120 \end{cases} = 𝟖𝟎$ . ( $𝑗^{*} (3) = 1$ )

$𝐹 (4) = min {\begin{cases} 𝐹 (0) + Cost (1, 4) = 125 \\ 𝐹 (1) + Cost (2, 4) = 50 + 85 = 135 \\ 𝐹 (2) + Cost (3, 4) = 70 + 65 = 135 \\ 𝐹 (3) + Cost (4, 4) = 80 + 50 = 130 \end{cases} = 𝟏𝟐𝟓$ . ( $𝑗^{*} (4) = 1$ )

Step 3 — reconstruct schedule

$𝑗^{*} (4) = 1$ → order in period 1, covers periods 1–4. Total cost = $125$ .

Step 4 — compare to basic EOQ on the average demand

Total demand $= 10 + 20 + 5 + 15 = 50$ over 4 periods → average $𝐷 = 12.5$ per period (or 50/year if $𝑇 = 4$ months $= 1 / 3$ year, $𝐷 = 150$ /year). EOQ would give a single $𝑄^{*}$ and a stationary cycle — but this problem’s demand is not stationary (period 4 is 3× period 3), so a stationary order cycle wastes either order cost or holding cost.

Wagner-Whitin’s answer (one big order in period 1) is cheaper than any stationary EOQ schedule because it adapts to the lumpy demand profile.

This is the value of dropping the “infinite horizon, stationary demand” assumption: when demand has structure, the optimal policy reflects that structure, not a one-size-fits-all $𝑄^{*}$ .