Offensive Security Researcher & Quantum Cryptography Analyst

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

Abdul Wahab Junaid
Production Lot Sizing algorithm and working of this algorithm

Production Lot Sizing algorithm and working of this algorithm

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

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.

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

Disadvantages

Applications

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;
}

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

Common Mistakes

Further Reading

Exit mobile version