Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 38 ยท Applications

Multi-Period Production Planning

Build production plans over several periods with inventory balance, overtime and backlog in an LP, then add setup costs for lot sizing with MILP and check it against Wagner-Whitin.

A factory does not decide what to make one day at a time in isolation. Demand changes from month to month, capacity is limited, and goods can be stored (at a cost) to be sold later. A multi-period production plan decides how much to produce in each period so that demand is met at the least total cost. It is a textbook linear program because of one structure: the inventory balance equation.

This lesson builds the standard model step by step, shows what the solution tells you, and then adds setup costs, which turn the LP into the integer lot-sizing problem.

The inventory balance

For each period t let d_t be demand, x_t units produced and I_t the inventory at the end of the period. Stock carries over:

TEXT
I_{t-1} + x_t - I_t = d_t           (starting stock + production - ending stock = demand)

With a known starting stock I_0 and non-negative inventory, this single equation ties periods together. Adding more features is a matter of adding variables:

Feature How to model it
Regular and overtime production x_t and o_t, each with a capacity and a cost (overtime costs more)
Holding cost h * I_t in the objective
Backorders (late delivery) B_t >= 0; balance becomes I_{t-1} - B_{t-1} + x_t + o_t - I_t + B_t = d_t; penalty b * B_t
Maximum storage I_t <= S
Safety stock I_t >= s_t
Several products Add an index p; coupled by shared capacity sum_p a_p x_{pt} <= cap_t
Workforce changes Variables for hiring and firing with costs, workforce level determines capacity
flowchart LR
    I0["Stock<br/>start of t"] --> P["+ Production<br/>(regular + overtime)"] --> D["- Demand"] --> I1["Stock<br/>end of t"]
    I1 -->|"carried to t+1<br/>(holding cost)"| I0

A six-period plan

Demand is seasonal: it peaks in the middle of the horizon. Regular capacity is 120 units a period, overtime adds up to 40 more at a higher cost. The solver should build inventory early with cheap regular production to avoid overtime later, but not too early because stock costs money.

Python LP production plan with overtime, inventory and backlog

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The plan runs regular production at full capacity from the start, building up inventory of 60 units, and then uses overtime in periods 3, 4 and 5 when demand exceeds regular capacity. No backlog is needed because overtime plus stock is enough. Try lowering ot_cap to 10 in the code: the model will start using backlog, which carries a penalty, or it becomes infeasible if you forbid backlog entirely.

Reading the answer

  • Level versus chase strategies. A chase plan makes exactly demand in every period (many capacity changes, little stock); a level plan produces a constant amount (stable workforce, lots of stock). The LP finds the cost-optimal blend automatically.
  • Shadow prices of the balance equations are the marginal cost of one more unit demanded in that period. They show where capacity is tight: periods with overtime have marginal cost near the overtime rate.
  • Rolling horizon. Plans are re-solved each period with updated forecasts; only the first period's decisions are implemented. The model's end-of-horizon effects (here: zero final stock) can distort decisions near the end, so planners use a longer horizon than they intend to execute.

Setup costs and lot sizing

In many plants every production run requires a setup (cleaning, changing tools), a fixed cost K regardless of the quantity. Now producing in every period is expensive, so the optimizer must decide when to produce and how much per run. With y_t = 1 if production happens in t:

TEXT
minimize    sum_t ( K y_t + h I_t )
subject to  I_{t-1} + x_t - I_t = d_t
            x_t <= M_t y_t,   y_t in {0, 1}

This is the uncapacitated lot-sizing problem. It is a fixed-charge model of the kind introduced in Binary Variables and Logic, and a showcase for formulation strength: the smallest valid M_t is the remaining demand d_t + d_{t+1} + ... + d_T, since you never need to produce more than that.

Python Lot sizing: weak versus tight big-M, and a Wagner-Whitin check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both versions have the same integer optimum, 760, which also matches the Wagner-Whitin dynamic program (it relies on the fact that an optimal plan produces only when stock is zero). The relaxations tell a different story: the weak big-M proves only 51, and the tight one 360, much closer. A tighter formulation means a smaller search tree.

The optimal plan makes four production runs, in periods 1, 3, 6 and 8, each covering the demand up to the next run. Setups and holding balance: the setup cost of 150 equals 75 unit-periods of holding at cost 2, so the plan avoids runs for tiny quantities.

Real lot-sizing models add capacity limits (x_t <= cap_t), multiple items sharing a capacity, setup times (not only costs) and sequence-dependent changeovers. These capacitated, multi-item versions are NP-hard, and good solutions use strong formulations (facility-location or shortest-path reformulations) and cutting planes.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the inventory balance I_{t-1} + x_t - I_t = d_t express?

    Stock carried in plus what is produced equals what is sold plus what is carried out.
  2. 2. Why does the optimal plan produce more than demand in early periods?

    Holding cost is cheaper than the overtime premium, so the plan pre-builds stock for the peak.
  3. 3. Which is the tightest valid big-M for x_t in uncapacitated lot sizing?

    You never produce more than will ever be needed, so remaining demand is both valid and tight.
  4. 4. How does adding setup costs change the model type?

    A fixed charge for each run needs a yes/no variable per period, which makes the model mixed-integer.

Summary

  • Multi-period models connect periods through inventory balance equations; extra features are extra variables.
  • With overtime, holding and backlog costs the LP chooses between chase and level production automatically.
  • Setup costs add binary variables and produce the lot-sizing MILP; tight big-M values give much better LP bounds.
  • Wagner-Whitin dynamic programming solves uncapacitated lot sizing exactly and checks the MILP.
  • Plans are rolled forward, re-solved each period with updated forecasts.

Next: Finance and Data Fitting with LP