Reducing a Lot Sizing Problem with Set up, Production, Shortage and Inventory Costs to Lot Sizing Problem with Set up, Production and Inventory Costs
ABSTRACT
We reduce lot sizing problem with (a) Set Up, Production, Shortage and Inventory Costs to lot sizing problem with (b) Set Up, Production, and Inventory Costs. For lot sizing problem (as in (b)), Pochet and Wolsey  have given already integral polyhedral with polynomial separation where a linear program yield “integer” solutions. Thus problem (b) which we have created can be more easily solved by methods available in literature. Also with the removal of shortage variables is an additional computational advantage.

1. Introduction

Capacitated single item lot sizing problem (CLSP) with setup, backorders and inventory is a well studied problem (see Wolsey  for a detailed literature review). Pochet and Wolsey  gave several valid inequalities of uncapacitated LSP which resulted in a reformulation (linear program) that can be solved much more easily (compared to effort required to solve the 0-1 mixed integer programming formulation of CLSP). We use formulation of Kumar  , and pose capacitated single item lot sizing problem (CLSP) with setup, backorders and inventory as a single item lot sizing problem with set up, production and inventory problem. We can then reformulate it by using valid inequality given in Pochet and Wolsey  .

2. Problem Formulation

Indices Used

t: Set of Time period from $1,\cdots ,T$ .

Constant:

ft: fixed cost in time period “t”;

pt: per unit variable (production) cost in time period “t”;

ct: production capacity in time period “t”;

Dt: demand in time period “t”;

ht: per unit inventory carrying cost in time period “t”;

sht: per unit shortage cost in time period “t”.

Definition of Variables

xt: amount produced in time period “t”;

yt: 1, if machine setup to produce in time period “t”,

0, otherwise;

st: shortage in time period “t”;

It: Inventory in time period “t”.

Model A1:

$\text{Minimize}\text{\hspace{0.17em}}Z=\underset{t=1}{\overset{T}{\sum }}{f}_{t}\ast {y}_{t}+\underset{t=1}{\overset{T}{\sum }}{p}_{t}\ast {x}_{t}+\underset{t=1}{\overset{T}{\sum }}{h}_{t}\ast {I}_{t}+\underset{t=1}{\overset{T}{\sum }}s{h}_{t}\ast {s}_{t}$ (1)

s.t.

${I}_{0}+\underset{t=1}{\overset{{t}_{1}}{\sum }}{x}_{t}+{s}_{{t}_{1}}=\underset{t=1}{\overset{{t}_{1}}{\sum }}{D}_{t}+{I}_{{t}_{1}}$ for all ${t}_{1}=1,\cdots ,T$ (2)

${x}_{t}\le {c}_{t}\cdot {y}_{t}$ , $\forall t=1,\cdots ,T$ (3)

${x}_{t},{I}_{t},{s}_{t}\ge 0$ ; and ${y}_{t}=\left(0,1\right)$ (4)

This formulation is based on the formulation given for the location-distributed problem with shortages and inventory by Kumar  . Traditionally the problem is formulated as (Wolsey  , p. 1593) given below:

Model A2:

Min (1)

${x}_{t}+{s}_{t}-{s}_{t-1}={D}_{t}+\left({I}_{t}-{I}_{t-1}\right),\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall t=1,\cdots ,T$ (5)

and (3) & (4).

In model (1), we substitute

${x}_{t}={c}_{t}\cdot {y}_{t}$ in (1) and (2), to get

${s}_{t1}=\underset{t=1}{\overset{{t}_{1}}{\sum }}{D}_{t}+{I}_{t1}-{I}_{0}-\underset{t=1}{\overset{{t}_{1}}{\sum }}{c}_{t}\ast {y}_{t}$ for all ${t}_{1}=1,\cdots ,T$ (6)

(6) is substituted in (1) along with xt, = ct * yt to get following:

Model A3:

$\begin{array}{l}{\sum }_{t=1,\cdots ,T}\left({f}_{t}+\left({p}_{t}\ast {c}_{t}\right)\right)\ast {y}_{t}+{\sum }_{t=1,\cdots ,T}\left({h}_{t}\ast {I}_{t}\right)\\ +{\sum }_{t=1,\cdots ,{t}_{1}}\left(s{h}_{t1}\ast \left({\sum }_{t=1,\cdots ,{t}_{1}}{D}_{t}+{I}_{t1}-{I}_{0}-{\sum }_{t=1,\cdots ,{t}_{1}}\left({c}_{t}\ast {y}_{t}\right)\right)\right)\end{array}$ (7)

${I}_{t}\ge 0$ ; and ${y}_{t}=\left(0,1\right)$ (8)

It can be easily seen that coefficient of It is positive; and coefficient of yt can be positive, negative or zero. It can be easily seen that Model A3 is a lot sizing problem without shortage variables as in (b). Now we can apply the methods of reformulation and valid inequalities developed as given in (1).

3. Conclusion

Thus we show that a lot sizing problem with set up, production, inventory and shortage costs is reduced to a lot sizing problem with set up, production and inventory costs. This is possible due to new formulation given in Kumar  . Also then reformulation-based methods given in  and  can be fruitfully applied. This is the useful contribution given in this paper.

Cite this paper
Sharma, R. and Ali, S. (2017) Reducing a Lot Sizing Problem with Set up, Production, Shortage and Inventory Costs to Lot Sizing Problem with Set up, Production and Inventory Costs. American Journal of Operations Research, 7, 282-284. doi: 10.4236/ajor.2017.75020.
References
   Pochet, Y. and Wolsey L.A. (1994) Polyhedra for Lot Sizing with Wagner-Whitin Costs. Math Programming, 67, 207-323.
https://doi.org/10.1007/BF01582225

   Wolsey, L.A. (2002) Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation. Management Science, 48, 1587-1602.
https://doi.org/10.1287/mnsc.48.12.1587.442

   Kumar, V. (2012) Equal Distribution of Shortages in Supply Chain of Food Corporation of India: Using Lagrangian Relaxation Methodology. Master’s Thesis, Indian Institute of Technology, Kanpur. (Unpublished)

Top