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.
Assumptions:
- |
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} $
Symbols:
| $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