ABSTRACT

In this article, we propose novel reformulations for capacitated lot sizing problem. These reformulations are the result of reducing the number of variables (by eliminating the backorder variable) or increasing the number of constraints (time capacity constraints) in the standard problem formulation. These reformulations are expected to reduce the computational time complexity of the problem. Their computational efficiency is evaluated later in this article through numerical analysis on randomly generated problems.

Keywords:

Capacitated Lot Sizing Problem, Efficient Problem Formulation, Branch and Bound

1. Introduction

Lot sizing problem aims to optimally utilize the available production resources while meeting the demand targets. It is classified as medium-term planning in production planning taxonomy. Lot sizing problem formulation depends upon the layout and the operating constraints in the production system. In the manufacturing industry, we come across many types of production systems. These production systems further give rise to different types of lot sizing problems (with different constraints and operating conditions) and their solution methodologies. Hence there is a rich literature on lot sizing problem and their solution methods. In this article, we restrict our discussion to general dynamic multi-level capacitated lot sizing problem.

This problem was first proposed by Billington et al. [1] . It addresses the following scenario: a finite planning horizon is given and is divided into discrete time periods. There is a dynamic demand for items which needs to be satisfied for each time period while honoring the production capacity constraints. Problem aims to develop a production plan over all time periods while minimizing the total cost comprising of setup cost, inventory cost, and backordering cost.

A capacitated lot sizing problem is a well-known NP-hard problem. If the capacity constraints of the problem are relaxed, then the problem can be solved in polynomial time [2] . Many model formulations have been proposed to develop an efficient numerical solution. These formulations differ with each other due to variables and constraints used. Formulations given in this article belongs to inventory and lot-size (I & L) formulations category, which are among the most popular in the literature due to their computational efficiency. These formulations use production quantity and inventory levels as the variables. Relaxation of each constraint in the standard I&L model affects the problem structure and hence its numerical complexity. Relaxation of capacity constraints decomposes CLSP into single-level lot sizing problem popularly known as Wagner-Whitin problem [2] . Further, some popular extensions to the standard problem have been suggested in the literature, to address certain practical issues. For example, Dillenberger et al. [3] have extended the problem to incorporate setup carryover. A setup cost and setup time are not incurred if the same item is being produced in the next time period, carried forward by the previous period. Our formulation incorporates binary variable for setup to address these issues. Binary setup variable to address the carryover of setup to the next period was earlier used by Hasse [4] , and Surie and Stadtler [5] .

We next discuss certain problem reformulations from the literature which are computationally efficient. CLSP can be formulated to assign each production quantity to a demand in a specific time period while minimizing the production cost. Shortest route formulation was proposed by Eppen and Martin [6] for a single level case. It was later extended by Tempelemier and Helber [7] for multi-level CLSP. Stadtler proposed an improvement in this formulation ( [8] [9] ), which decreases the number of non-negative coefficients. Rosling [10] introduced a formulation based on Plant location problem analogy. This formulation was further extended by Maes et al. [11] for the capacitated case of a lot-sizing problem. Capacity constraints were included in the original formulation for this purpose. Equivalence of Shortest route and SPL formulation in terms of objective function was shown by Denizel et al. [12] .

Apart from reformulation, additional inequalities can be added to the problem formulation to tighten the bound while reducing the search space. Important researches in this category are discussed next. Barany et al. [13] included lot sizing and inventory variables for the single level uncapacitated lot-sizing problem. Additional valid constraints are included in the formulation to tighten the convex bound of the uncapacitated lot-sizing problem. Pochet and Wolsey [14] ; and Clark and Armentano [15] extended the work of Barany [13] for the multi-level case. Miller et al. [16] have proposed additional valid inequalities for the capacitated case of a lot-sizing problem. Further Surie and Stadtler [5] have proposed valid inequalities for multi-level capacitated lot sizing problem with set up carry over. Setup carryover constraints are redefined to achieve a computational advantage in this formulation.

Research in this article is based on the appropriate reformulation of the standard capacitated lot sizing problem. We state the standard problem formulation and then derive three reformulations of the problem by eliminating the backordering variable or/and adding two capacity constraints. Efficacies of these formulations in terms of reduced computational complexity are demonstrated through numerical analysis of random problems on GAMS.

2. Research Methodology

As stated in the previous section, we intend to evaluate the improvement in computational efficiency of the model when the number of decision variables are decreased, or constraints are added to tighten the bound of the solution space. Model A1 is the reference standard model, which is tinkered to develop model A2, A3, and A4 accordingly. In model A2 (proposed later), we have eliminated the backordering variable; hence it is expected to be computationally efficient when compared with model A1. Similarly, we have added two extra constraints (Equation (27), Equation (28)) in our standard model (A1) which is referred to as model A3. Further, we eliminate backordering variable while adding two constraints in model A1 and refer it to model A4. Hence model A4 is expected to perform best among all. Efficacy of each model is evaluated by performing paired t-test of the computational time of random problem instances on A1, A2, A3, and A4. Branch and bound method is used in GAMS for solving random problem optimally by these models. Finally it is concluded in section 6 that most computationally efficient formulation should be used solving capacitated lot sizing problem.

3. Problem Formulation/Reformulation

3.1. Model A1

$\text{Minimize}Z=\sum _{i=1}^I\sum _{t=1}^T\left[C{P}_{it}*X{P}_{it}+C{S}_{it}*Y{S}_{it}+CIN{V}_{it}*XIN{V}_{it}+CB{O}_{it}*XB{O}_{it}\right]$ (1)

Subject to:

$X{P}_{it}+XIN{V}_{i,t-1}+XB{O}_{it}=D_{it}+XIN{V}_{it}+XB{O}_{i,t-1}\forall i\in I,t\in T$ (2)

$\sum _{i=1}^I\left(P{T}_{it}*X{P}_{it}+S{T}_i*Y{S}_{it}\right)\le CAP{T}_t\forall t\in T$ (3)

$\sum _{i=1}^I\left(P{T}_{it}*D_{it}+S{T}_i*Y{S}_{it}\right)\le CAP{T}_t\forall t\in T$ (4)

$X{P}_{it}\le CA{P}_{it}Y{S}_{it}\forall i\in I,t\in T$ (5)

$\sum _{t=1}^{T}X{P}_{it}\ge \sum _{t=1}^T{D}_{it}\forall i\in I$ (6)

$XIN{V}_{i0}=0\forall i\in I$ (7)

$XIN{V}_{iT}=0\forall i\in I$ (8)

$XB{O}_{i0}=0\forall i\in I$ (9)

$XB{O}_{iT}=0\forall i\in I$ (10)

$Y{S}_{it}\in \left\{0,1\right\}\forall i\in I,t\in T$ (11)

$XIN{V}_{it},X{P}_{it},XB{O}_{it}\ge 0\forall i\in I,t\in T$ (12)

3.2. Model A2

$\begin{array}{l}\text{Minimize}Z=\sum _{i=1}^I\sum _{t=1}^T\left[C{P}_{it}*X{P}_{it}+C{S}_{it}*Y{S}_{it}+CIN{V}_{it}*XIN{V}_{it}\right]\\ +\sum _{t_1=1}^T\sum _{i=1}^{I}CB{O}_{i{t}_1}*\left(\sum _{t=1}^{t_1}{D}_{it}+XIN{V}_{i{t}_1}-\sum _{t=1}^{t_1}X{P}_{it}\right)\end{array}$ (13)

Subject to:

$\sum _{t=1}^{t_1}{D}_{it}+XIN{V}_{i{t}_1}-\sum _{t=1}^{t_1}X{P}_{it}\ge 0\forall i\in I,t_1\in T$ (14)

$\sum _{i=1}^I\left(P{T}_{it}*X{P}_{it}+S{T}_i*Y{S}_{it}\right)\le CAP{T}_t\forall t\in T$ (15)

$X{P}_{it}\le CA{P}_{it}Y{S}_{it}\forall i\in I,t\in T$ (16)

$\sum _{t=1}^{T}X{P}_{it}\ge \sum _{t=1}^T{D}_{it}\forall i\in I$ (17)

$XIN{V}_{i0}=0\forall i\in I$ (18)

$XIN{V}_{iT}=0\forall i\in I$ (19)

$Y{S}_{it}\in \left\{0,1\right\}\forall i\in I,t\in T$ (20)

$XIN{V}_{it},X{P}_{it}\ge 0\forall i\in I,t\in T$ (21)

3.3. Model A3

$\text{Minimize}Z=\sum _{i=1}^I\sum _{t=1}^T\left[C{P}_{it}*X{P}_{it}+C{S}_{it}*Y{S}_{it}+CIN{V}_{it}*XIN{V}_{it}+CB{O}_{it}*XB{O}_{it}\right]$ (22)

Subject to:

$X{P}_{it}+XIN{V}_{i,t-1}+XB{O}_{it}=D_{it}+XIN{V}_{it}+XB{O}_{i,t-1}\forall i\in I,t\in T$ (23)

$\sum _{i=1}^I\left(P{T}_{it}*X{P}_{it}+S{T}_i*Y{S}_{it}\right)\le CAP{T}_t\forall t\in T$ (24)

$\sum _{i=1}^I\left(P{T}_{it}*D_{it}+S{T}_i*Y{S}_{it}\right)\le CAP{T}_t\forall t\in T$ (25)

$X{P}_{it}\le CA{P}_{it}Y{S}_{it}\forall i\in I,t\in T$ (26)

$\sum _{i=1}^I\sum _{t=1}^T\left(P{T}_{it}*D_{it}+S{T}_i*Y{S}_{it}\right)\le \sum _{t=1}^{T}CAP{T}_t$ (27)

$\sum _{i=1}^I\sum _{t=1}^T\left(P{T}_{it}*X{P}_{it}+S{T}_i*Y{S}_{it}\right)\le \sum _{t=1}^{T}CAP{T}_t$ (28)

$\sum _{t=1}^{T}X{P}_{it}\ge \sum _{t=1}^T{D}_{it}\forall i\in I$ (29)

$XIN{V}_{i0}=0\forall i\in I$ (30)

$XIN{V}_{iT}=0\forall i\in I$ (31)

$XB{O}_{i0}=0\forall i\in I$ (32)

$XB{O}_{iT}=0\forall i\in I$ (33)

$Y{S}_{it}\in \left\{0,1\right\}\forall i\in I,t\in T$ (34)

$XIN{V}_{it},X{P}_{it},XB{O}_{it}\ge 0\forall i\in I,t\in T$ (35)

3.4. Model A4

$\begin{array}{l}\text{Minimize}Z=\sum _{i=1}^I\sum _{t=1}^T\left[C{P}_{it}*X{P}_{it}+C{S}_{it}*Y{S}_{it}+CIN{V}_{it}*XIN{V}_{it}\right]\\ +\sum _{t_1=1}^T\sum _{i=1}^{I}CB{O}_{i{t}_1}*\left(\sum _{t=1}^{t_1}{D}_{it}+XIN{V}_{i{t}_1}-\sum _{t=1}^{t_1}X{P}_{it}\right)\end{array}$ (36)

Subject to:

$\sum _{t=1}^{t_1}{D}_{it}+XIN{V}_{i{t}_1}-\sum _{t=1}^{t_1}X{P}_{it}\ge 0\forall i\in I,t_1\in T$ (37)

$\sum _{i=1}^I\left(P{T}_{it}*X{P}_{it}+S{T}_i*Y{S}_{it}\right)\le CAP{T}_t\forall t\in T$ (38)

$X{P}_{it}\le CA{P}_{it}Y{S}_{it}\forall i\in I,t\in T$ (39)

$\sum _{i=1}^I\sum _{t=1}^T\left(P{T}_{it}*D_{it}+S{T}_i*Y{S}_{it}\right)\le \sum _{t=1}^{T}CAP{T}_t$ (40)

$\sum _{i=1}^I\sum _{t=1}^T\left(P{T}_{it}*X{P}_{it}+S{T}_i*Y{S}_{it}\right)\le \sum _{t=1}^{T}CAP{T}_t$ (41)

$\sum _{t=1}^{T}X{P}_{it}\ge \sum _{t=1}^T{D}_{it}\forall i\in I$ (42)

$XIN{V}_{i0}=0\forall i\in I$ (43)

$XIN{V}_{iT}=0\forall i\in I$ (44)

$Y{S}_{it}\in \left\{0,1\right\}\forall i\in I,t\in T$ (45)

$XIN{V}_{it},X{P}_{it}\ge 0\forall i\in I,t\in T$ (46)

Problem notations are tabulated in Table 1. Equation (1), Equation (13), Equation (22), and Equation (36) minimize the total production cost of the system in model A1, A2, A3, and A4 respectively. Equation (2), Equation (14), Equation (23), and Equation (37) are the state equations as they ensure that the total quantities in a particular time period is a function of total quantities carried forward from the preceding time period while satisfying demand. It must be noted that in model A2 and A4, the backorder variable has been eliminated from the model by appropriate substitution (backorder variable $XB{O}_{it}$ , has been eliminated by substituting it in terms of other decision variables from Equation (2). Its value has been substituted in the objective function Equation (13) in model A2 and objective function Equation (36) in model A4). These changes are reflected in Equation (23) and Equation (37). Reduction in number of variables improves the time complexity of the model. Equation (3), Equation (4), Equation (15), Equation (24), Equation (25), Equation (38), Equation (40), and Equation (41) are the time capacity constraints. They ensure that production of the items, and demand satisfied (through production) in a particular time period does not violate the production time available in that time period. Similarly, Equation (5), Equation (16), Equation (26), and Equation (39) are the production capacity constraints. These constraints ensures that capacity constraints in terms of production resources are not violated in any time period. Equation (27), Equation (28), Equation (40), and Equation (41) are the additional capacity constraints added in model A3, and A4 for tightening the bound and subsequently achieving computational advantage as discussed earlier. These constraints are derived from constraint Equation (24) and Equation (25) by extending the time capacity constraints over the entire time horizon T. It must be noted that Equation (24) and Equation (25) ensures the time capacity constraints are honored only for individual time period. Equation (6), Equation (17), Equation (29), and Equation (42) ensures that demand is satisfied in each period. Equations (7)-(10), Equation (18), Equation (19), Equations (30)-(33), Equation (43), Equation (44) sets the initial and final conditions (boundary conditions) over the production horizon. Equation (11), Equation (12), Equation (20), Equation (21), Equation (34), Equation (35), Equation (45), Equation (46) are the binary and non-negativity constraints for decision variables.

4. Numerical Experiments

40 problems each of size 5 × 5 and 6 × 6 are randomly generated in GAMS. 5 × 5, 6 × 6 problems denotes the lot sizing problem to find an optimum production plan of 5 items over 5 time periods, and 6 items over 6 time periods respectively. Only feasible problems are retained for data analysis (6 × 6―29 problems, 5 × 5―31 problems). Value of constants in these problems is randomly generated according to normal distribution (Table 2) and uniform distribution (Table 3).

5. Data Analysis

All the problems are implemented in GAMS. Solution to these sample problems are tabulated in Appendix. According to t-test performed on data, problem A3 is computationally efficient to problem A1 with a statistical significance of 0.009317 (p-value). Similarly A4 is better than A2 with a statistical significance of 0.003071 (p-value). Model A2 is computationally more efficient than model A1 with a statistical significance of 0.000695 (p-value). Model A4 is computationally more efficient than model A3 with a statistical significance of 0.00473 (p-value).

6. Conclusion

In this article, we have demonstrated the effect of reducing the number of variables, increasing the number of constraints on the computational time of lot sizing problem through 4 models. We infer from our data analysis that model A4 is the most computationally efficient model, and hence is recommended to be used for solving capacitated lot sizing problem.

Cite this paper

Sharma, R.R.K., Sinha, P. and Verma, M.K. (2018) Computationally Efficient Problem Reformulations for Capacitated Lot Sizing Problem. American Journal of Operations Research, 8, 312-322. https://doi.org/10.4236/ajor.2018.84018

References

Appendix: Data Analysis Results