Lot Sizing

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.

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">{{hint}}</p>
<div class="controls">
  <label>{{lbl_order_cost}}
    <input id="K" type="number" min="0" step="1" value="100">
  </label>
  <label>{{lbl_holding_cost}}
    <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">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{status_initial}}</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; }

// Code not found

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.

How hard is lot sizing, really?

• Brute force would consider every subset of periods to order in — $2^{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(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(n \log n)$ (and $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.

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

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.