Production Lot Sizing Algorithm: Working, Explanation, and Inventory Optimization

I want to frame this topic around a very concrete manufacturing question I’d face as a production planner: over a series of time periods with known (and possibly fluctuating) demand, how much should I produce in each period to minimize my total cost, balancing the fixed cost of setting up a production run against the cost of holding inventory? This is the production lot-sizing problem, and the algorithm I focus on is the Wagner–Whitin algorithm, a dynamic programming method that finds the mathematically optimal production schedule.

History and Background

The problem was formally solved by Harvey M. Wagner and Thomson M. Whitin in their 1958 paper “Dynamic Version of the Economic Lot Size Model,” published in Management Science. Before their work, practitioners largely relied on the simpler Economic Order Quantity (EOQ) model developed by Ford W. Harris in 1913, which assumes constant, continuous demand — a poor fit for real production environments with period-by-period fluctuating demand. Wagner and Whitin showed that dynamic programming could find the truly optimal multi-period production plan, and their algorithm became foundational to materials requirements planning (MRP) systems still used in manufacturing today.

Problem Statement

I state it as: given demand $d_t$ for each period $t = 1, \dots, T$, a fixed setup cost $K$ incurred whenever I produce in a period, a per-unit holding cost $h$ for carrying inventory from one period to the next, and (optionally) a per-unit production cost, determine the production quantity $x_t$ for each period that satisfies all demand exactly (no backlog) while minimizing total setup plus holding cost over the planning horizon.

Core Concepts

• Setup cost ($K$): the fixed cost incurred each time I run a production batch, regardless of quantity.
• Holding cost ($h$): the cost per unit of inventory carried over from one period to the next.
• Zero-inventory-ordering property: a key structural property proven by Wagner and Whitin — in an optimal solution, I never produce in a period unless the inventory entering that period is exactly zero. This drastically reduces the number of production plans I need to consider.
• Planning horizon: the total number of periods $T$ over which I am planning production.
• Regeneration point: a period where inventory hits zero and a new production decision begins, breaking the problem into independent sub-problems.

How It Works

1. I use the zero-inventory-ordering property: production only ever happens in a period where incoming inventory is zero, and each production run covers demand for a contiguous block of periods until the next production run.
2. I define $C(t)$ as the minimum total cost to satisfy demand for periods $1$ through $t$.
3. For each period $t$, I consider every possible “last production period” $j \leq t$ such that a single production run at $j$ covers demand from $j$ through $t$, and compute the cost of that option as $C(j-1) + K + h \times (\text{holding cost of carrying demand from } j+1 \dots t \text{ produced at } j)$.
4. I take the minimum over all such $j$ to get $C(t)$.
5. I repeat for $t = 1, \dots, T$, building up the cost table, and use backtracking through my recorded choices to recover the actual optimal production plan.

Working Principle

The mechanism is a textbook dynamic programming approach: I break the full multi-period problem into overlapping sub-problems (“what’s the best plan for periods 1 through t”) and solve them in increasing order of $t$, reusing previously computed optimal sub-solutions. The zero-inventory property is what makes this tractable — without it, I would have to consider a combinatorially explosive set of possible production quantities per period, but with it, I only need to consider “which earlier period’s production run covers demand at time $t$,” which is a linear-in-$t$ set of choices at each step.

Mathematical Foundation

I define the recurrence:

$$ C(t) = \min_{1 \leq j \leq t} \left[ C(j-1) + K + h \sum_{i=j+1}^{t} (i-j) , d_i \right] $$

with base case $C(0) = 0$. Here, producing at period $j$ to cover demand through period $t$ means I hold $d_i$ units for $(i-j)$ periods for each $i$ between $j+1$ and $t$, incurring holding cost $h(i-j)d_i$ for that portion.

The final answer is $C(T)$, and the optimal production periods are recovered by tracing back through the arguments $j^*$ that achieved each minimum.

Diagrams

flowchart TD
    Start([Start: demand d1...dT known]) --> Init["C(0) = 0"]
    Init --> Loop["For t = 1 to T"]
    Loop --> Eval["For each j <= t: evaluate C(j-1) + K + holding cost(j,t)"]
    Eval --> Min["C(t) = minimum over all j"]
    Min --> Record[Record best j as production start for this segment]
    Record --> Next{t < T?}
    Next -- Yes --> Loop
    Next -- No --> Backtrack[Backtrack from T to recover production periods]
    Backtrack --> End([Return optimal lot-sizing plan])

Pseudocode

function WagnerWhitin(demand[1..T], K, h):
    C[0] = 0
    choice[1..T] = undefined

    for t from 1 to T:
        C[t] = infinity
        for j from 1 to t:
            holdingCost = 0
            for i from j+1 to t:
                holdingCost += (i - j) * demand[i]
            cost = C[j-1] + K + h * holdingCost
            if cost < C[t]:
                C[t] = cost
                choice[t] = j   // production run starting at j covers up to t

    // Backtrack to find production periods
    productionPeriods = []
    t = T
    while t > 0:
        j = choice[t]
        add j to productionPeriods
        t = j - 1

    return C[T], reverse(productionPeriods)

Step-by-Step Example

I’ll use a 4-period example: demand = [10, 20, 5, 15], setup cost $K = 50$, holding cost $h = 1$ per unit per period.

• $C(0) = 0$
• $C(1)$: only option is produce at j=1 for t=1. Cost = $0 + 50 + 0 = 50$. So $C(1)=50$, choice(1)=1.
• $C(2)$:
  • j=1 (covers periods 1–2): holding = (2-1)*20=20. Cost = $C(0)+50+20=70$.
  • j=2 (covers only period 2): Cost = $C(1)+50+0=100$.
  • Minimum is 70 at j=1. $C(2)=70$, choice(2)=1.
• $C(3)$:
  • j=1 (covers 1–3): holding = (2-1)*20 + (3-1)*5 = 20+10=30. Cost = $0+50+30=80$.
  • j=2 (covers 2–3): holding = (3-2)*5=5. Cost = $C(1)+50+5=105$.
  • j=3 (covers only 3): Cost = $C(2)+50+0=120$.
  • Minimum is 80 at j=1. $C(3)=80$, choice(3)=1.
• $C(4)$:
  • j=1 (covers 1–4): holding = 20+10+(4-1)*15=20+10+45=75. Cost=$0+50+75=125$.
  • j=2 (covers 2–4): holding=(3-2)*5+(4-2)*15=5+30=35. Cost=$C(1)+50+35=135$.
  • j=3 (covers 3–4): holding=(4-3)*15=15. Cost=$C(2)+50+15=135$.
  • j=4 (covers only 4): Cost=$C(3)+50+0=130$.
  • Minimum is 125 at j=1. $C(4)=125$, choice(4)=1.

Backtracking from t=4: choice(4)=1, so production at period 1 covers all four periods. Total optimal cost = 125, with a single production run at period 1 producing all 50 units (10+20+5+15).

Time Complexity

The naive implementation, computing holding costs from scratch inside the nested loop, runs in $O(T^3)$ in the worst case (outer loop $T$, inner loop over $j$ up to $T$, and the holding-cost summation up to $T$). With incremental holding-cost computation (updating the running sum as $j$ decreases rather than recomputing), this reduces to $O(T^2)$. Wagner and Whitin’s original paper, using additional structural properties (planning horizon theorem), showed the algorithm can be implemented in $O(T \log T)$ or even $O(T)$ with further refinement, though the basic $O(T^2)$ DP is what’s most commonly taught and implemented.

Space Complexity

I need $O(T)$ space for the cost array $C$ and the choice/backtracking array, plus $O(T)$ for the demand array itself — overall space is $O(T)$, linear in the planning horizon.

Correctness Analysis

Correctness follows from the zero-inventory-ordering theorem, which Wagner and Whitin proved rigorously: in any optimal solution, if inventory at the start of period $t$ is positive, then no production occurs in period $t$. This means every optimal solution can be decomposed into contiguous “production blocks,” each starting at a period with zero incoming inventory. Because of this, my dynamic programming recurrence — which only considers “which earlier zero-inventory period’s production run supplies period $t$” — is guaranteed to consider every possible optimal-solution structure, and by the principle of optimality (any sub-plan of an optimal plan must itself be optimal for its own sub-problem), the recurrence correctly computes the true minimum cost.

Advantages

• Produces a provably optimal production plan, not just a heuristic approximation.
• Efficiently handles time-varying (lumpy) demand, unlike the classical EOQ model which assumes constant demand.
• The zero-inventory property gives useful structural insight for manufacturers even beyond the raw algorithm output.
• Forms a natural building block within larger MRP (Material Requirements Planning) systems.

Disadvantages

• The basic model assumes deterministic, known demand — real demand often has uncertainty that this model doesn’t directly address.
• Doesn’t natively handle capacity constraints (e.g., maximum production per period) without significant extension.
• $O(T^2)$ complexity can become a bottleneck for very long planning horizons unless the more advanced $O(T \log T)$ variant is implemented.
• Doesn’t account for quantity discounts or non-linear cost structures without modification.

Applications

• Manufacturing production scheduling and materials requirements planning (MRP).
• Inventory management for retailers with fluctuating seasonal demand.
• Supply chain procurement planning, deciding when and how much to order from suppliers.
• Capacity and workforce planning tied to production batches.

Implementation in C

#include <stdio.h>
#include <limits.h>

#define T 4  // number of periods

int main() {
    int demand[T + 1] = {0, 10, 20, 5, 15};  // 1-indexed
    int K = 50;  // setup cost
    int h = 1;   // holding cost per unit per period

    long C[T + 1];
    int choice[T + 1];
    C[0] = 0;

    for (int t = 1; t <= T; t++) {
        C[t] = LONG_MAX;
        for (int j = 1; j <= t; j++) {
            long holdingCost = 0;
            for (int i = j + 1; i <= t; i++) {
                holdingCost += (long)(i - j) * demand[i];
            }
            long cost = C[j - 1] + K + h * holdingCost;
            if (cost < C[t]) {
                C[t] = cost;
                choice[t] = j;
            }
        }
    }

    printf("Minimum total cost: %ld\n", C[T]);

    printf("Production plan (periods with production runs):\n");
    int t = T;
    int periods[T], count = 0;
    while (t > 0) {
        int j = choice[t];
        periods[count++] = j;
        t = j - 1;
    }
    for (int i = count - 1; i >= 0; i--)
        printf("Produce at period %d\n", periods[i]);

    return 0;
}

#include <stdio.h>
#include <limits.h>

#define T 4  // number of periods

int main() {
    int demand[T + 1] = {0, 10, 20, 5, 15};  // 1-indexed
    int K = 50;  // setup cost
    int h = 1;   // holding cost per unit per period

    long C[T + 1];
    int choice[T + 1];
    C[0] = 0;

    for (int t = 1; t <= T; t++) {
        C[t] = LONG_MAX;
        for (int j = 1; j <= t; j++) {
            long holdingCost = 0;
            for (int i = j + 1; i <= t; i++) {
                holdingCost += (long)(i - j) * demand[i];
            }
            long cost = C[j - 1] + K + h * holdingCost;
            if (cost < C[t]) {
                C[t] = cost;
                choice[t] = j;
            }
        }
    }

    printf("Minimum total cost: %ld\n", C[T]);

    printf("Production plan (periods with production runs):\n");
    int t = T;
    int periods[T], count = 0;
    while (t > 0) {
        int j = choice[t];
        periods[count++] = j;
        t = j - 1;
    }
    for (int i = count - 1; i >= 0; i--)
        printf("Produce at period %d\n", periods[i]);

    return 0;
}

Sample Input and Output

Input: demand = [10, 20, 5, 15], setup cost K = 50, holding cost h = 1.

Output:

Minimum total cost: 125
Production plan (periods with production runs):
Produce at period 1

This matches my manual walkthrough — a single production run at period 1 satisfying all four periods’ demand is optimal here.

Optimization Techniques

• Use incremental holding-cost accumulation (updating a running sum as I decrease $j$) to bring the complexity down from $O(T^3)$ to $O(T^2)$.
• Apply the Wagner–Whitin planning-horizon theorem, which lets me discard many candidate $j$ values early, achieving near-linear performance in practice.
• For very large horizons, consider approximate heuristics like the Silver–Meal heuristic or the Least Unit Cost method, which trade optimality for speed.
• Exploit problem-specific structure (e.g., capacity limits) by adding constraint-checking directly into the DP transition, when extending beyond the classic model.

Common Mistakes

• Forgetting the zero-inventory-ordering property and instead trying to enumerate arbitrary production quantities per period, which balloons the search space unnecessarily.
• Mixing up “holding cost per unit per period” with “holding cost per unit total,” which silently produces wrong totals.
• Not properly backtracking through the choice array, leading to a correct minimum cost but an incorrect or missing production schedule.
• Ignoring integer overflow when demand and cost values are large and the horizon is long — using appropriately sized integer types matters in a real implementation.

Further Reading

• Wagner, H. M., & Whitin, T. M. (1958). “Dynamic Version of the Economic Lot Size Model.” Management Science, 5(1), 89–96.
• Harris, F. W. (1913). “How Many Parts to Make at Once.” Factory, The Magazine of Management.
• Silver, E. A., Pyke, D. F., & Peterson, R. Inventory Management and Production Planning and Scheduling, Wiley.
• Nahmias, S. Production and Operations Analysis, McGraw-Hill.