Capacitated lot sizing (CLS)¶
Definition 1: Capacitated lot sizing
Given:
-
a set \(T = \{1,2,\dots,m\}\) of \(m\) time periods,
-
for each period \(t \in T\), a demand \(d_t \in \Z_{\ge 1}\) and a capacity \(cap_t \in \Z_{\ge 1}\), both counted in units of one product,
-
for each period \(t \in T\), three non-negative integer costs: the setup cost \(sc_t\), the variable production cost \(vc_t\) per unit produced and the holding cost \(hc_t\) per unit kept in stock at the end of the period,
the capacitated lot sizing problem (CLS) asks to decide how much to produce in every period, so that every demand is satisfied with what is produced and what is in stock, the capacities are respected, and the total cost of setups, production and holding is minimized.
Assumptions
-
We make the following assumptions:
-
The stock is empty at the beginning and at the end of the horizon. Leaving stock at the end only adds cost, so no optimal plan needs it; an initial stock is a variant of the problem (Section.
-
The capacities allow to satisfy the demands, period after period (otherwise there is no feasible plan). Formally:
\[ \sum_{u=1}^{t} cap_u \ge \sum_{u=1}^{t} d_u, ~~~~ \forall t \in T \] -
The quantities are integer. With integer data, once the periods with a setup are fixed, what remains is a minimum cost flow problem, which has an integer optimal solution: restricting the quantities to integers does not change the optimal cost.
-
What the course does on this problem¶
| Technique | Where |
|---|---|
| Definition | Ch. 8 «Lot sizing problems» |
| Formulations | Ch. 15 «Formulations of lot sizing problems» |
| Dynamic programming | Ch. 16 «Principles of dynamic programming»; Ch. 26 «DP for the capacitated lot sizing problem» |
| MIP heuristics | Ch. 33 «MIP heuristics for the classical problems» |
| Exercises | Ch. 8 (5 exercises); Ch. 15 (5 exercises); Ch. 26 (2 exercises) |
Properties¶
-
NP-hard with general capacities; without capacities (ULS) it is polynomial (Ch. 1).
-
Lower bound: the sum of the \(k\) smallest setup costs, with \(k\) the fewest periods whose capacities cover the total demand (Ch. 8).
-
Lot-for-lot and merging by hand: \(250\to210\to180\) on the instance of Ch. 8, where \(180\) is optimal (Ch. 8).
Formulations¶
-
Big-M formulation: the strong value \(M_t=\min\{cap_t,D_{t,m}\}\) raises the LP bound on the instance of Ch. 8 from \(99.65\) to \(157.5\) (Ch. 15).
-
The shortest-path formulation gives the bound \(170\), the strongest of the chapter (Ch. 15).
Dynamic programming¶
-
Without capacities an optimal plan produces only with empty stock (Wagner and Whitin): a DP over the last production run solves the ULS in \(\Theta(m^2)\) steps (Ch. 25).
-
With capacities the state is (period, inventory): \(O(m\,D\,C)\) steps, pseudo-polynomial (Ch. 26).