441. Wagner–Whitin

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

441.1.1. Setup

• Periods (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.

441.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 ). The decision space collapses from “how much in each period” to “which blocks to use” — a much smaller problem solvable by DP.

441.1.3. Cost of a single order block

If we order in period to cover demands :

• Order cost: (one order).
• Holding cost: each unit consumed in period () sat in inventory for periods. Total holding for the block:

Block cost:

441.1.4. DP recursion

Let = minimum cost to cover demand for periods . Boundary: .

For each , the last order block ends at and starts at some :

Solve forward: . Track the argmin at each step to reconstruct the schedule.

441.1.5. Algorithm

1. Compute “Cost” for all pairs .
2. Forward pass: for each , compute and store .
3. Backtrack from : order in covering , then recurse on .

Complexity: in the number of periods.