Lesson · Dynamic Programming and Sequential Decisions · Ordering over time

Wagner-Whitin and the Order Intervals

Demand is known period by period, an order costs a fixed charge whatever its size, and stock costs something to hold. The decision looks like a quantity per period, which is a continuum, until one observation collapses it: an optimal plan never orders while stock remains. That makes a plan a partition of the periods into consecutive intervals, each covered by one order, and the recursion runs over the period the last order was placed in rather than over the stock on hand.

Open the interactive lesson Practice

an optimal plan never orders while stock remains, so it never holds and orders at once therefore a plan IS a partition of 1..T into consecutive order intervals F(t) = min over j from 1 to t of [ F(j-1) + K + h x (holding from j to t) ] demand 10 62 12 130 154 129, K = 54, h = 2 F: 0, 54, 108, 132, 186, 240, 294 and the cheapest plan costs 294 2^(T-1) = 32 order patterns, all of them priced, and none beats 294

One observation, and the recursion it makes possible

Core ideas

What this lesson establishes

The theorem first, because without it there is no recursion; then the state it licenses, then the check that keeps the reconstruction honest.

An optimal plan never orders while stock remains

Suppose it did: some period t has stock left over from an earlier order and places a new order as well. Move the quantity that period t orders for its own demand back into the earlier order, or move the leftover stock forward by cancelling part of the earlier order — one of the two saves holding cost without adding a setup, and neither can cost more. So an order always covers a whole run of consecutive periods, ending exactly where the next order begins.

So the state is when the last order was, not what is in stock

Stock on hand is the obvious state and it is a poor one: it takes many values and most of them are unreachable. The theorem says the only thing the future needs to know is where the current interval started, so F(t), the cheapest way to cover periods 1 through t exactly, is enough — one number per period, and the decision in each row is which period the last order went in.

Reconstructing the plan is a second computation

F(T) is the cost. The plan is recovered by following the argmins back: the last order went in period j, so the one before it covers 1 through j−1, and so on. That chain is separate arithmetic from the table, so the lab re-prices what it produces — setup by setup and unit-period by unit-period — and puts the total beside F(T).

The material

From a quantity per period to a partition into intervals

The theorem, the table it makes possible, and the plan read back out of the argmins.

Definition · The lot-sizing problem

Demands d₁, ..., d_T are known. An order placed in period t arrives in time for period t and costs a fixed setup charge K whatever its size. Stock carried from one period into the next costs h per unit per period. Shortages are not allowed and there is no stock at the start or required at the end.

A plan says how much to order in each period. Its cost is K times the number of orders, plus h times the total unit-periods of holding.

Theorem · An optimal plan orders only when stock has run out

There is an optimal plan in which every order arrives in a period that begins with nothing in stock. Consequently every order covers a consecutive run of periods, the runs partition 1 through T, and the quantity ordered at the start of a run is exactly the demand over that run.

So the search is over the 2^(T−1) ways of choosing where the runs break — one binary choice at each of the T−1 boundaries — rather than over quantities.

Take an optimal plan and suppose period t both begins with stock s > 0 and places an order of size q > 0. Let ε be the smaller of s and q.

Reduce the earlier order by ε and increase period t's order by ε: the number of orders is unchanged or falls by one, and ε units are held for fewer periods, so holding cost strictly falls. The plan is no more expensive.

Repeat while any period both holds and orders. Each step removes at least one such period and never creates one, so the process ends, and it ends at a plan that is optimal and orders only into an empty stock.

□

That is the whole of the modelling work. What is left is the recursion, and it is the one from “Filling the Table from the End” with the stages relabelled: let F(t) be the cheapest way to cover periods 1 through t exactly, with F(0) = 0. The last order in such a plan went in some period j, covering j through t, so F(t) is the smallest over j of F(j−1) plus K plus the holding on the run j to t. Holding on that run is h times Σ (i − j) dᵢ, because period i's demand sits in stock for i − j periods.

demand d1..d6 = 10 62 12 130 154 129 K = 54 h = 2 F(0) = 0 F(1) = 54 order at 1 F(2) = min( 178 , 108 ) = 108 order at 2 F(3) = min( 226 , 132 , 162 ) = 132 order at 2 F(4) = min( 1006 , 652 , 422 , 186 ) = 186 order at 4 F(5) = min( 2238 , 1576 , 1038 , 494 , 240 ) = 240 order at 5 F(6) = min( 3528, 2608, 1812, 1010, 498, 294 ) = 294 order at 6 reading the argmins backwards from t = 6: last order at 6, covering 6 so F(5) is next last order at 5, covering 5 so F(4) is next last order at 4, covering 4 so F(3) is next last order at 2, covering 2 to 3 so F(1) is next last order at 1, covering 1 five orders: 10 in p1, 74 in p2, 130 in p4, 154 in p5, 129 in p6

Five orders at 54 each is 270, and the plan's holding is 24 — the whole of it is period 3's demand of 12 carried one period at 2 per unit — so 294. The lab prices the plan again that way, from the demand and the two charges rather than from F, and prints the result beside the recursion's. It also enumerates all 32 order patterns and prices each of them; the best is 294 and it breaks at the same places.

Why the argmin column is worth more than the value column

Look at the row for F(4). The candidates are 1006, 652, 422 and 186, and the last of them wins by a wide margin: covering period 4's demand of 130 from any earlier order means carrying 130 units for at least one period at 2 each, which is 260 on its own against a setup charge of 54. The value column tells you the answer; the argmin column tells you why, and it is where the structure of the instance is visible.

Example · Flat demand, and the block structure

Set every demand to 40, the setup to 90 and the holding rate to 1. The table comes out 0, 90, 130, 210, 260, 340, 390, the plan is three orders of 80 covering periods 1 to 2, 3 to 4 and 5 to 6, and the cost is 390.

Even blocks, because nothing distinguishes one period from another. Now move the setup charge up and down with the slider and watch where the breaks go: raise it and the intervals lengthen, raise the holding rate instead and they shorten. The plan is the balance of the two and neither alone decides it.

Example · One period that dwarfs the rest

Demands 8, 6, 200, 7, 9, 5 with a setup of 60 and a holding rate of 3. The cheapest plan costs 234 with three orders, and the middle one is placed in period 3 itself.

Carrying 200 units even one period would cost 600, which is ten setup charges, so no optimal plan holds that demand at all. The instance is worth meeting because it shows the theorem doing real work: the search is over partitions, and this one is forced to break just before period 3.

What the model left out

Demand is known exactly, and known in advance for the whole horizon. Orders arrive instantly. Shortages are impossible rather than expensive. There is no capacity on an order and no minimum size, no discount for ordering more, and the setup charge is the same in every period. Each of those is a real feature of real ordering and each of them is absent here; several of them would break the theorem rather than merely complicate the arithmetic, which is the sort of omission worth knowing about before quoting a plan.

Interactive

Wagner-Whitin: when to order

A plan is a partition into intervals, and every one of them is priced here

Move the two charges and watch the intervals move

The recursion is over the period the last order was placed in, not over the stock on hand. Every row shows each candidate priced, so the argmin is visible rather than asserted; the plan it returns is then priced again from the demand and the two charges; and all 2ᵀ⁻¹ order patterns are enumerated and priced as a third witness. Nothing is shown as an answer unless the three agree.

Worked example

Demand, period by period

The charge for placing an order54

Holding cost, per unit per period2

The cheapest plan costs—

By enumerating every pattern—

Do the two agree?—

Orders it places—

Patterns there are—

The plan, priced again from scratch—

F(t) is the cheapest way to cover periods 1 to t, and the recursion is over the period the LAST order was placed in. That works because an optimal plan never orders while stock remains — so every plan is a partition of the periods into consecutive intervals, and there are 2^T−1 of them, all of which are priced here as a check.

Method

Filling the F table

Four steps. The third is the one worth writing out in full the first few times, because it is where the holding arithmetic hides.

Set F(0) = 0 and take the periods in order

F(0) = 0 says that covering nothing costs nothing. Every later row depends only on earlier rows, so one pass left to right finishes it.

For each t, try every period j the last order could have gone in

That is j from 1 to t. Each choice splits the problem into “cover 1 to j−1 optimally”, which is F(j−1) and already known, and “one order covering j to t”.

Price the interval as K plus h times the unit-periods

Demand in period i covered by an order in period j waits i − j periods, so the holding is h times Σ (i − j) dᵢ over the interval. The demand in period j itself contributes nothing, which is the term people drop.

Record the minimum and the period that attained it

Both columns. The values give the cost; the argmins give the plan, read backwards from t = T.

Re-price the reconstructed plan from the demand

Setup charges plus holding, computed from scratch. If it does not equal F(T) the reconstruction is wrong even though the table is right, and that failure has a completely different cause from an arithmetic slip in the table.

Intervals, states and what the theorem buys

Score 0 / 0

Choose the answer you can justify.

One table, one plan, and thirty-two patterns

The candidates in each row of F, then the plan read back out of the argmins, then the same answer reached by pricing every way of breaking the six periods into intervals.

demand 10 62 12 130 154 129 K = 54 h = 2 t each candidate F(j-1) + K + holding(j..t) F(t) order at 1 j=1 0 + 54 + 0 = 54 54 1 2 j=1 0 + 54 + 2(62) = 178 j=2 54 + 54 + 0 = 108 108 2 3 j=1 0 + 54 + 2(62 + 24) = 226 j=2 54 + 54 + 2(12) = 132 132 2 j=3 108 + 54 + 0 = 162 4 j=3 108 + 54 + 2(130) = 422 j=4 132 + 54 + 0 = 186 186 4 5 j=5 186 + 54 + 0 = 240 240 5 6 j=6 240 + 54 + 0 = 294 294 6 the plan, read backwards from t = 6: ordered in quantity covering setup holding total period 1 10 period 1 54 0 54 period 2 74 periods 2 to 3 54 24 78 period 4 130 period 4 54 0 54 period 5 154 period 5 54 0 54 period 6 129 period 6 54 0 54 in all 270 24 294 all 32 order patterns priced: best 294, breaking at 1, 2, 4, 5, 6

The only holding in the whole plan is 12 units carried one period, and it buys the saving of one setup charge: 24 against 54. Every other pair of adjacent periods has too much demand in the later one for that trade to pay, which is why the plan is four singletons and one pair rather than something tidier.

For a rehearsal, drop the setup charge to 20 and predict the plan before running it. With setups cheap relative to holding, the intervals should shrink to singletons everywhere; check whether they actually do, and find the first charge at which periods 2 and 3 separate.

The harder rehearsal: the enumeration is 2ᵀ⁻¹, which at six periods is 32 and at thirteen is 4096. The recursion prices T(T+1)/2 candidates, which is 21 at six periods and 91 at thirteen. Work out roughly where on that curve an enumeration stops being something a page can do, and notice that the recursion has not changed at all in the meantime.

Common mistakes

Taking the stock on hand as the stateIt is the first thing everyone reaches for and it is a much worse state: it takes many values, most of them are never reached by any optimal plan, and it makes the table larger without making it more correct. The theorem is what licenses the smaller state, so if you cannot state the theorem you should not be using the small state — and the moment shortages or capacities enter, the theorem goes and the small state goes with it.

Charging holding on the demand the order arrives forAn order placed in period j covers period j immediately, so period j's own demand is never held. Writing (i − j + 1) instead of (i − j) adds h times the interval's whole demand to every candidate. Because it inflates all candidates in a row, the argmins often survive and the plan looks right while every number in the table is wrong.

Quoting the plan without saying demand was assumed knownThe entire construction depends on knowing d₁ through d_T in advance. A rolling horizon, where the table is refilled each period as forecasts arrive, is a different thing and its plans are not optimal for any single problem. The arithmetic here cannot tell you which situation you are in, and it will produce a confident answer either way.

Check your understanding

✓

Finish when you can state the exchange argument, fill the F table with its argmin column, read the plan back out and price it independently.

You should be able to say why an optimal plan never holds and orders in the same period, explain why that makes a plan a partition, write F(t) as a minimum over the period of the last order, compute the holding on an interval without the off-by-one, and reconstruct and re-price the plan from the argmins.

Note: The answer above is exact, and it is exact about a schedule that nobody in practice fills in this way: the table needs the whole horizon in advance, and it is more work than the situation usually justifies. So two rules of thumb are used instead, and the honest question is what they cost. The next lesson, “Silver-Meal and Least Unit Cost”, traces both of them against this same recursion — on an instance where one of them happens to find the optimum, and on another where both miss, by different amounts, with different numbers of orders.