Capacitated Lotsizing Problem (CLSP)

The capacitated dynamic lotsizing problem (CLSP) results, in the single-item dynmaic lot sizing problem (SLULSP, Wagner-Whitin problem) is extended to multiple products that compete for a resource with limited capacity.


multiple products
dynamic demands
a single resource types with a limited capacity per period
setup times (sometimes negleted)
any number of products can be produced per period ("big bucket" model)
no setup carry-over

There are several model formulations available for the CLSP. The standard formulation reads as follows:

$Minimize\; Z= \displaystyle{\sum_{k=1}^K \sum_{t=1}^T} \big( { { s_k\cdot \gamma _{kt}}}+{ h_k\cdot y_{kt}} \big)$

subject to

$ y_{k,t-1}+q_{k,t-z_{k}}-y_{kt}=d_{kt} \qquad {k=1,2,\ldots,K;\;t=1,2,\ldots,T} $

$ \displaystyle{\sum_{k=1}^K} \big(tb_k\cdot q_{kt}+ tr_k\cdot \gamma _{kt}\big) \leq b_{t} \qquad {\;t=1,2,\ldots,T} $

$ q_{kt}-M\cdot \gamma _{kt} \leq 0 \qquad {k=1,2,\ldots,K;\;t=1,2,\ldots,T} $

$ q_{kt}, y_{kt} \geq 0 \qquad {k=1,2,\ldots,K;\;t=1,2,\ldots,T} $

$ \gamma_{kt} \in \{0,1\} \qquad {k=1,2,\ldots,K;\;t=1,2,\ldots,T} $


$t$ period
$k$ product
$d_{kt}$ external demand of product $k$ in period $t$
$tb_{k}$ production time per unit of product $k$
$tr_{k}$ setup time for product $k$
$b_{t}$ capacity of the resource in period $t$
$q_{kt}$ lot size of product $k$ in period $t$
$y_{kt}$ inventory of product $k$ at the end of period $t$
$\gamma_{kt}$ binary setup variable of product $k$ in period $t$

Model CLSP results if we define model SLULSP for multiple products and add capacity constraints and input-output considerations.

There are other formulations of the CLSP which provide sharper lower bounds of the optimum value of objective function, if an LP-relaxation is used. Although there are a lot of heuristic algorithms available to solve the CLSP, in many practical situations a standard solver can be applied for the exact or at least good solution of a problem instance.

Note that the above formulation is a big-bucket model formulation. This means, that any production quantity greater than zeor induces a setup with associated setup costs and/or time, even if the setup state of a resource for a given product is carried over to the next period to continue production of the last product in a period.

» See also: SLULSP - Single-level uncapacitated dynamic lotsizing problem