Multi-Level Capacitated Lotsizing Problem

Deterministic Planning
Lotsizing

Multi-Level Capacitated Lotsizing Problem (MLCLSP)

The dynamic multi-level capacitated lotsizing problem is one of the hardest optimization problems known in the area of operations and production mangement. It arises in any company that uses the MRP successive planning approach. In a typical MRP system, based on the master production schedule the time-phased dependent demand quantities for components are computed. This is done with respect to the bill-of-material structure, the development of the inventory position and under the assumption of a (known) fixed lead time per item. Simple single-item single-level lot sizing algorithms are used to calculate "optimal" lot sizes. All lot size computations are performed under the assumption of infinite capacity, i.e. resources are completely neglected.

This successive planning concept is more than fourty years old, and it has been criticized by many authors which pointed out several severe flaws that make it hard to believe that any of these commercially available systems used in industry would perform well. The main problem is that in no planning phase the limited capacities of the resources are taken into account appropriately. From a theoretical point of view, this must result in infeasible production schedules. From a practical point of view, the results are unpredictable flow times due to queueing up of orders in front of overloaded resources. The consequence is large work-in-process combined with bad customer service.

In the MRP approach, lotsizing is embedded in the demand explosion procedure, where based on an ordering of the items with respect to their low level codes on an item by item basis first the net requirements are calculated and then "optimal" lot sizes are computed. The user is offered several lot sizing algorithms, among others the classical Harris-Wilson square-root formula, the Silver-Meal heuristic or the Groff heuristic.

An overview over the MRP approach and a critique is here.

The problem outlined above can be avoided, if in the material requirements planning phase a feasible production schedule is generated. However, this is only possible through the explicit consideration of the capacities of the resources during lot sizing. Therefore, in a resource-oriented MRP system the item-oriented successive planning phase must be substituted by a simultaneous lot sizing approach. The lot sizing model used in this approach is known as the multi-level capacitated lot sizing problem (MLCLSP). It is based on the following assumptions.

Assumptions:

-	multiple products
-	dynamic demands
-	multi-level BOM structure
-	several resource types
-	setup times
-	any number of products can be produced per period ("big bucket" model)
-	no setup carry-over

There are several model formulations available for the MLCLSP. 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}}-\displaystyle{\sum_{i\in \mathcal{N}_k}} a_{ki}\cdot q_{it}-y_{kt}=d_{kt} \qquad {k=1,2,\ldots,K;\;t=1,2,\ldots,T} $

$ \displaystyle{\sum_{k\in \mathcal{K}_j}} \big(tb_k\cdot q_{kt}+ tr_k\cdot \gamma _{kt}\big) \leq b_{jt} \qquad {j=1,2,\ldots,J;\;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
$j$	resource
$\mathcal{K}_j$	set of products that are produced by resource $j$
$\mathcal{N}_k$	set of direct successors (parents) of product $k$
$z_k$	lead time of product $k$
$d_{kt}$	external demand of product $k$ in period $t$
$a_{ij}$	gozinto factor between product $i$ and $i$
$tb_{k}$	production time per unit of product $k$
$tr_{k}$	setup time for product $k$
$b_{jt}$	capacity of resource $j$ 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 MLCLSP results if we define model SLULSP for multiple products and add capacity constraints and input-output relations.

There are other formulations of the MLCLSP which provide sharper lower bounds of the optimum value of objective function, if an LP-relaxation is used. Nevertheless, no matter which formulation is used, the MLCLSP is a very hard problem, and we do not expect to find exact solution algorithms that could routinely be applied in industry for the solution of problem instances with practical dimensions. However, an increasing number of heuristic solution algorithms is available.

Note that the above formulation is a big-bucket model formulation. This means, that any production quantity greater 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.

As far a we know, there is no Advanced Planning System that is capable to solve the above problem. By contrats, lotsizing is usually not supported at all or only with historic algorithms like the economic production quantity.

Deterministic Planning Lotsizing

Multi-Level Capacitated Lotsizing Problem (MLCLSP)

Deterministic Planning
Lotsizing