Reducing a Lot Sizing Problem with Set up, Production, Shortage and Inventory Costs to Lot Sizing Problem with Set up, Production and Inventory Costs ()
1. Introduction
Capacitated single item lot sizing problem (CLSP) with setup, backorders and inventory is a well studied problem (see Wolsey [2] for a detailed literature review). Pochet and Wolsey [1] 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 [3] , 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 [1] .
2. Problem Formulation
Indices Used
t: Set of Time period from
.
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:
(1)
s.t.
for all
(2)
,
(3)
; and
(4)
This formulation is based on the formulation given for the location-distributed problem with shortages and inventory by Kumar [3] . Traditionally the problem is formulated as (Wolsey [2] , p. 1593) given below:
Model A2:
Min (1)
(5)
and (3) & (4).
In model (1), we substitute
in (1) and (2), to get
for all
(6)
(6) is substituted in (1) along with xt, = ct * yt to get following:
Model A3:
(7)
; and
(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 [3] . Also then reformulation-based methods given in [1] and [2] can be fruitfully applied. This is the useful contribution given in this paper.