Developing a New Reformulation of Single Level Capacitated Lot Sizing Problem (SLCLSP) with Set up, Shortage and Inventory Costs

R. R. K. Sharma, Vimal Kumar, Nilanjan Das Khan

Department of Industrial & Management Engineering, Indian Institute of Technology, Kanpur, India.

DOI: 10.4236/ajor.2017.75019                

Abstract

Formulation of SLCLSP given by Pochet and Wolsey [1] had set up, variables, inventory and shortage cost. We give a new reformulation where SLCLSP is reduced to set up and inventory variables. We find that this reformulation has less number of real variables than the reformulation of Pochet and Wolsey [1]. It is argued that this leads to computations advantages, and this is supported by the empirical investigation that we carried out.

Keywords

Reformulation of SLCLSP

1. Introduction and Literature Review

Capacitated lot sizing problem (CLSP) is well studied in literature, see Verma [2] , and Verma and Sharma [3] [4] [5] for a summary of recent works on CLSP. For literature on reformulation of CLSP, see Pochet and Wolsey [1] and Miller and Nemhauser et al. [6] for a detailed exposition on reformulations of CLSP. In this paper we give a new approach which leads to a better reformulation of CLSP.

2. Formulation by Pochet and Wolsey [1]

Indices Used

t: Set of the Time period from 1, ・・・, n, for which we are taking decisions;

Definition of Constant

$f_t$ : Fixed setup cost in time period “t”;

$p_t$ : Per unit production cost in time period “t”;

$d_t$ : Demand in time period “t”, here demand is independent;

$h_t$ : Per unit inventory carrying cost in time period “t”;

$s{h}_t$ : Per unit shortage cost in time period “t”;

$c_t$ : Production capacity in the time period “t”;

Definition of Variables

$x_t$ : Number of product produced in time period “t”;

$y_t$ : Binary variable takes value “1” if machine setup to produce in time period “t”, “0”, otherwise;

$I_t$ : In stock inventory at the end of time period “t”;

$s_t$ : Backlog in the end of period “t”;

Mathematical Model

$\text{Minimize}Z={\displaystyle \underset{t=1}{\overset{n}{\sum }}{f}_t}\ast y_t+{\displaystyle \underset{t=1}{\overset{n}{\sum }}{p}_t\ast x_t}+{\displaystyle \underset{t=0}{\overset{n-1}{\sum }}{h}_t}\ast I_t+{\displaystyle \underset{t=1}{\overset{n}{\sum }}s{h}_t}\ast s_t$ (1)

Production balance constraints

$x_t+\left(s_t-s_{t-1}\right)=d_t+\left(I_t-I_{t-1}\right),1\le t\le n$ (2)

Capacity constraints

$x_t\le c_t\ast y_t,1\le t\le n$ (3)

$I_o=s_n=0$ (4)

Pochet and Wolsey [1] gave the following constraint that lead to reformulation:

$x_t=y_t\ast c_t$ (5)

Non-negativity constraints

$x_t,r_t,s_t\ge 0$ (6)

SLCLSP as given by Pochet and Wolsey [1] is Model A1: Min (1); s.t. (2), (3), (4) and (6). By using (5) in place of (3) lead to reformulation (called Model A2: min (1); s.t. (2), (4), (5) and (6). Model A1 has less number of variables as variable “x” is eliminated.

We add a new constraint given below (see, [7] ) that can be used in place of (2):

$I_0+{\displaystyle \underset{t=1}{\overset{t_1}{\sum }}{x}_t}+s_{t_1}={\displaystyle \underset{t=1}{\overset{t_1}{\sum }}{D}_t}+I_{t_1},\forall t_1=1,\cdots ,T$ (7)

Using (5) we get the following (called Model A3): Min Z1 (or (8)); s.t. (4), (5), (6), (7).

$\text{Min}Z1={\displaystyle \underset{t=1}{\overset{T}{\sum }}{f}_t}\ast y_t+{\displaystyle \underset{t=1}{\overset{T}{\sum }}{p}_t\ast c_t\ast y_t}+{\displaystyle \underset{t=1}{\overset{T}{\sum }}{h}_t}\ast I_t+{\displaystyle \underset{t=1}{\overset{T}{\sum }}s{h}_t}\ast s_t$ (8)

We use (7) to eliminate s_t from the problem A2 to get: Min Z2 (or (9)); s.t. (4), (5), (6).

$\text{Min}Z2={\displaystyle \underset{t=1}{\overset{T}{\sum }}{f}_t}\ast y_t+{\displaystyle \underset{t=1}{\overset{T}{\sum }}{p}_t\ast c_t\ast y_t}+{\displaystyle \underset{t=1}{\overset{T}{\sum }}{h}_t}\ast I_t$ $+{\displaystyle \underset{t=1}{\overset{T}{\sum }}s{h}_t}\ast \left({\displaystyle \underset{t=1}{\overset{t_1}{\sum }}{D}_t}+I_{t_1}-I_0-{\displaystyle \underset{t=1}{\overset{t_1}{\sum }}{c}_t\ast y_t}\right)$ (9)

It can be seen that model A3 has least number of variables; it is followed by A2 that has less number of variables compared to model A1 which is well known reformulation (Pochet and Wolsey [1] . We solve model A1, model A2, and

Table 1. Problem for 50 time period (Z value and No. of node processed in brand and bound procedure).

Table 2. Problem for 50 time period (Iteration and execution time in GAMS).

Table 3. Problem for 60 time period (Z value and No. of nodes).

Table 4. Problem for 60 time period (Iteration and execution time).

Table 5. Problem for 100 time period (Z value and No. of nodes).

Table 6. Problem for 100 time period (Iteration and execution time).

model A3 by using student version of GAMS available at IIT Kanpur; and find that our reformulations (model A3 and A2) have superior computational advantages than model has A1.

3. Preparing Test Problems and Results

We created problem instances with set up, inventory carrying, shortage and production cost are normally distributed with mean and variance given below:

Fixed cost: mean 100000 and variance 10000

Shortage cost: mean 5000 and variance 500

Inventory carrying cost: mean 600 and variance 60

Variable Production cost: mean1500 and variance 100

Demand and capacity were chosen from uniform distribution in the range of 10,000 - 15,000. In the case of infeasible solution, the capacity values are increased or demand values are decreased keeping other costs same. We created 50 problem instances each for periods 50, 60 and 100. Models A1, A2 and A3 were coded in GAMS and were solved in GAMS; and they were run in branch and bound mode. The GAMS solver returns a satisfactory solution obtainable in reasonable time. It is to be noted that these problems are NP-HARD and will take few billion centuries to come to optimal solution. Detailed data are given in appendix see Tables 1-6; and consolidated results of “t” test are given in Tables 7-9 below. Models A1, A2 and A3 are compared on the criteria of execution time,

Table 7. 50 Time period: t values.

Table 8. 60 Time period: t values.

Table 9. 100 time period: t values.

*Significant at 0.05 level; **significant at 0.01 level; ***significant at 0.001 level; In Table 7: 2.742**means that model A3 takes less time than model A1 and is significant at 0.01 level.

number of iterations and number of nodes evaluated in the search tree). On an average, A3 is superior to A1 and A2 and A2 is superior to A1 on most criteria; and large positive “t” values in the Tables 7-9 give adequate support in favor of A3.

4. Discussion and Conclusion

Thus it can be seen that model A3 has superior results in general (except for the case of execution time in 60 period problems) (here A3 is better than A1, but not statistically significant). This shows that the new formulation given by us is superior to models available in literature. This is the useful contribution we make. The three reformulations presented in this paper use Equation (5) and this leads

to ${\displaystyle \underset{t=1}{\overset{T}{\sum }}{x}_t}\ge {\displaystyle \underset{t=1}{\overset{T}{\sum }}{D}_t}$ To get ${\displaystyle \underset{t=1}{\overset{T}{\sum }}{x}_t}={\displaystyle \underset{t=1}{\overset{T}{\sum }}{D}_t}$ , we need to develop good heuristics, and

show that the duality gap is as less as possible. We have already started work on this, and will come back with results as soon as possible.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Pochet, Y. and Wolsey, L.A. (1991) Solving Multi-Item Lot-Sizing Problems Using Strong Cutting Planes. Management Science, 37, 53-67. https://doi.org/10.1287/mnsc.37.1.53
[2]	Mayank, V. (2012) Capacitated Lot Sizing with Back Orders in Multilevel Situations. Ph.D. Thesis, Indian Institute of Technology, Kanpur.
[3]	Mayank, E. and Sharma, R.R.K. (2009) Relaxations and Equivalence of Two Formulations of the Capacitated Lot Sizing Problem with Back-Orders and Setup Times. Proceedings of the Global Conference on Business and Finance, 4, 42-53.
[4]	Mayank, V. and Sharma, R.R.K. (2010) A New Lagrangian Relaxation Based Approach to solve Capacitated Lot-Sizing Problem with Backlogging. Global Business and Management Research, Universal-Publishers, Boca Raton, Vol. 2, 285-295.
[5]	Mayank, V. and Sharma, R.R.K. (2015) Lagrangian Based Approach to Solve a Two Level Capacitated Lot Sizing Problem. Cogent Engineering, 2, 108861.
[6]	Miller, A.J., Nemhauser, G.L. and Savelsbergh, M.W.P (2000) On the Capacitated Lot Sizing and Continuous 0-1 Knapsack Polyhedral. European Journal of operational Research, 125, 298-315. https://doi.org/10.1016/S0377-2217(99)00461-0
[7]	Kumar, V. (2012) Equal Distribution of Shortages in Supply Chain of Food Corporation of India: Using Lagrangian Relaxation Methodology. M. Tech Dissertation, Indian Institute of Technology, Kanpur. (Unpublished)