Introduction

Picture a warehouse that knows, week by week, exactly how much it will sell. It still has to make a decision every week: place a new order, or live off the shelf? Every order carries a fixed setup cost — paperwork, shipping, a machine changeover — no matter the size. But anything you order early and keep on the shelf racks up a holding cost for each week it waits.

Order in one giant batch and you pay almost no setup costs, but you drown in holding charges. Order a little every week and holding is cheap, but the setup costs pile up. Somewhere between those extremes lies the cheapest plan — and with a dozen periods there are thousands of ways to split the orders.

This is the lot-sizing problem. It looks like the kind of combinatorial puzzle that should blow up exponentially. It doesn't — and the reason is one of the prettiest results in operations research.

Plan the Reorders

Below is a six-period plan. Each period has a known demand. Set the fixed order cost (paid once whenever you place an order) and the holding cost (paid per unit, per period it sits in stock). Then press Solve and the planner computes the exact cheapest schedule.

<p class="hint">Each period has a known <b>demand</b>. You pay the fixed <b>order cost</b> once whenever you place an order, plus the <b>holding cost</b> for every unit that waits one period in stock. Press <b>Solve</b> to compute the exact cheapest schedule (Wagner–Whitin dynamic programming).</p>
<div class="controls">
  <label>Order cost K
    <input id="K" type="number" min="0" step="1" value="100">
  </label>
  <label>Holding cost h (per unit·period)
    <input id="h" type="number" min="0" step="0.5" value="1">
  </label>
</div>
<table class="grid" id="grid"></table>
<div class="btns">
  <button id="solve" type="button">Solve</button>
  <button id="reset" type="button" class="ghost">Reset demand</button>
</div>
<div class="status" id="status">Set the costs, then press Solve.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: 1rem; flex-wrap: wrap; margin: .3rem 0 .6rem; }
.controls label { font-size: .85rem; color: #1d3557; font-weight: 600; display: flex; flex-direction: column; gap: .25rem; }
.controls input { width: 90px; padding: .3rem .4rem; border: 1px solid #adb1b8; border-radius: 6px; font: 600 14px system-ui; }
table.grid { border-collapse: collapse; margin: .4rem 0; }
.grid th, .grid td { border: 1px solid #cdd9e3; padding: .35rem .5rem; text-align: center; font-size: .85rem; min-width: 52px; }
.grid th { background: #e8eef3; color: #1d3557; font-weight: 700; }
.grid td.lbl { background: #f4f7fa; color: #1d3557; font-weight: 700; text-align: right; min-width: 96px; }
.grid input { width: 48px; padding: .2rem; border: 1px solid #adb1b8; border-radius: 5px; text-align: center; font: 600 14px system-ui; }
.order { background: #d6f0dd; font-weight: 700; color: #0a7d33; }
.order::after { content: " ✚"; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .4rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Wagner-Whitin lot sizing (1958): given per-period demand d[1..n], a fixed order
// cost K, and a holding cost h per unit per period, find the order schedule that
// minimizes total (order + holding) cost. Solved exactly in polynomial time by DP.
//
// Key fact (zero-inventory property): an optimal plan only orders when stock hits
// zero, and each order covers an exact run of future periods. So define
//   F[i] = min cost to satisfy demand for periods i..n,
//          ordering at period i to cover through some period j>=i.
// Cost of ordering at i to cover i..j = K + holding of units carried = K + h * sum_{t=i..j} (t-i)*d[t].
//   F[i] = min over j>=i of  cost(i,j) + F[j+1],   F[n+1] = 0.
let DEFAULT = [10, 20, 5, 15, 8, 12];
let demand = DEFAULT.slice();

function num(id){ return parseFloat(document.getElementById(id).value) || 0; }

function buildGrid(){
  const n = demand.length;
  let head = '<tr><th class="lbl">Period</th>';
  for(let t=0;t<n;t++) head += '<th>'+(t+1)+'</th>';
  head += '</tr>';
  let drow = '<tr><td class="lbl">Demand</td>';
  for(let t=0;t<n;t++) drow += '<td><input data-i="'+t+'" type="number" min="0" step="1" value="'+demand[t]+'"></td>';
  drow += '</tr>';
  let orow = '<tr id="orow"><td class="lbl">Order (qty)</td>';
  for(let t=0;t<n;t++) orow += '<td id="o'+t+'">—</td>';
  orow += '</tr>';
  document.getElementById('grid').innerHTML = head + drow + orow;
  document.querySelectorAll('#grid input[data-i]').forEach(inp=>{
    inp.addEventListener('input', ()=>{ demand[+inp.dataset.i] = Math.max(0, parseInt(inp.value)||0); });
  });
}

// Returns {orders: array of {period, qty}, cost}
function solve(d, K, h){
  const n = d.length;
  const F = new Array(n+1).fill(Infinity); F[n] = 0; // F[i] uses 0-based i (periods i..n-1)
  const nextOrder = new Array(n).fill(-1);
  for(let i=n-1;i>=0;i--){
    let carry = 0;            // holding-unit-periods accumulated covering i..j
    for(let j=i;j<n;j++){
      carry += (j - i) * d[j];          // units demanded at j wait (j-i) periods
      const cost = K + h*carry + F[j+1];
      if(cost < F[i]){ F[i] = cost; nextOrder[i] = j; }
    }
  }
  const orders = [];
  let i = 0;
  while(i < n){
    const j = nextOrder[i];
    let qty = 0; for(let t=i;t<=j;t++) qty += d[t];
    orders.push({ period: i, qty });
    i = j + 1;
  }
  return { orders, cost: F[0] };
}

function run(){
  const K = num('K'), h = num('h');
  const res = solve(demand, K, h);
  // clear order row
  for(let t=0;t<demand.length;t++){ const c=document.getElementById('o'+t); c.textContent='—'; c.className=''; }
  res.orders.forEach(o=>{ const c=document.getElementById('o'+o.period); c.textContent=o.qty; c.className='order'; });
  const s = document.getElementById('status');
  s.textContent = fmt('Optimal: %length% order(s), total cost %cost%.', { length: res.orders.length, cost: res.cost });
  s.className = 'status ok';
  console.log('orders', res.orders, 'cost', res.cost);
}

document.getElementById('solve').addEventListener('click', run);
document.getElementById('reset').addEventListener('click', ()=>{ demand = DEFAULT.slice(); buildGrid(); document.getElementById('status').textContent='Set the costs, then press Solve.'; document.getElementById('status').className='status'; });
buildGrid();
Result
Console

Notice what the algorithm exploits. Because holding stock is never free, an optimal plan only ever orders an amount that covers a whole run of upcoming periods exactly — it never carries a fraction. That single insight (the zero-inventory property) shrinks a sea of possibilities down to one clean question per period: which future period should this order last until? Dynamic programming answers that, in order, and stitches the answers into the global optimum.

The Real Complexity

How hard is lot sizing, really?

  • Brute force would consider every subset of periods to order in — 2n−12^{n-1} schedules. With 30 periods that's already half a billion, and it grows hopeless fast.
  • It's solved — exactly, in polynomial time. In 1958, Harvey Wagner and Thomson Whitin published a dynamic-programming algorithm that finds the guaranteed-optimal schedule in O(n2)O(n^{2}) time, where n is the number of periods. No guessing, no approximation: the true cheapest plan, every time.
  • The key is the zero-inventory property. An optimal policy never orders unless the shelf is empty, and each order covers an exact integer number of future periods. So the only choice at each ordering point is "cover demand through which period?" — and a DP over those choices is all you need.
  • It's even faster than that. In the early 1990s, Federgruen–Tsitsiklis and Wagelmans–Van Hoesel–Kolen sharpened the algorithm to O(nlog⁡n)O(n \log n) (and O(n)O(n) in special cases) using geometric and Monge-array tricks.

That is the punchline: a problem that looks exponential is genuinely in P, one of the cleanest success stories in optimization. It sits in the same easy world as the shortest path — in fact, lot sizing is exactly a shortest path through a graph of "order now, next at period k" decisions.

Where It Matters

"Pay a fixed cost to act now, or wait and pay to hold" is a shape that shows up far beyond warehouses:

  • Production planning: the Wagner-Whitin logic is the textbook core of MRP (material requirements planning) systems that schedule factory runs.
  • Retail replenishment: deciding how often to restock each SKU when delivery has a fixed cost and shelves cost money.
  • Cloud and energy: batching jobs or charging a battery has a fixed switch-on cost versus a per-period holding/idle cost — the same math.
  • Cash and maintenance: how often to withdraw cash, or service a machine, given a fixed transaction cost and a carrying cost in between.

Whenever a fixed "act" cost trades off against a smooth "wait" cost, the optimal rhythm comes from lot sizing. Its big-batch cousins — when capacity is tight or items compete for it — can turn hard, linking it to problems like the knapsack and scheduling.

Conclusion

Lot sizing carries a quietly encouraging message. Faced with a tangle of order-or-wait decisions across many periods, you might brace for an exponential search. Instead, one structural fact — that an optimal plan never holds stock it doesn't have to — collapses the whole thing into a short, exact computation.

So not every problem that looks like a combinatorial explosion actually is one. The frontier mapped out by P vs NP has surprises on both sides, and lot sizing is a happy one: a real, money-saving question with a guaranteed-optimal answer you can compute before lunch.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/inventory-lot-sizing/Content licensed under CC BY-NC 4.0.