Page 56 - IJOCTA-15-2

Multiple item economic lot sizing problem with inventory dependent demand
′
1. In the pseudocodes of Algorithm 1, z(.) re- Then, if we refer to (c it + λ t ) as c , we can
it
turns the objective function value of either the rewrite the objective function and obtain the fol-
LR or the original problem for some given input. lowing final form of the LR of the multiple item
It can be discriminated easily from the context: ELSIDD problem:
if the input is Λ, then it returns the objective
function value of LR for that choice of Lagrange
T N T
multipliers; whereas, if the input is y, then it re- X X X
z(Λ) = λ t C t + max p it D it
turns the objective function value of the multiple
t=1 i=1 t=1
item ELSIDD for the given y.
N T
X X
′
− (S it y it + c x it + h it I it ) (24)
it
i=1 t=1
4.1.1. Lagrangian Relaxation of the multiple subject to (LR)
item ELSIDD
(x i , y i , I i , D i , U i ) ∈ S i i = 1, . . . , N. (25)
Consider formulation (2) –(9) of the multiple item
ELSIDD problem. There, capacity constraint (5)
Note that the problem LR is decomposed into
ties N single item ELSIDD problems. As a mat- N independent single item ELSIDD problems.
ter of fact, for i = 1, . . . , N, if we let S i be the set These single item problems can be solved by using
of feasible solutions for the single item ELSIDD the O(T J ) algorithm of, where J = max J it .
4 2
max
4
problem of item i, then we can equivalently write i,t
4 2
That is, LR can be solved in O(NT J ) time.
formulation (2) –(9) as follows:
Furthermore, one can show that for any Λ ≥ 0,
N T z(Λ) ≥ z, which means that the objective func-
X X
z = max p it D it tion of the LR is greater than the objective func-
i=1 t=1 tion value of the original problem. In other words,
N T z(Λ) is an upper bound for z. Therefore, we try
X X
− (S it y it + c it x it + h it I it ) (19) to find the smallest upper bound by solving the
i=1 t=1 following LDP:
subject to
N min {z(Λ) : Λ ≥ 0} . (LDP)
X
x it ≤ C t t = 1, . . . , T (20)
i=1
(x i , y i , I i , D i , U i ) ∈ S i i = 1, . . . , N, (21) The objective function of the LDP, z(Λ), is a
convex function of Λ. The sub-gradient optimiza-
tion method can be used to determine the optimal
where x i , y i , I i , D i and U i are vectors that hold vector Λ. Below we describe how we implement
values of x it , y it , I it , D it , and U it for i = 1, . . . , N, the sub-gradient method.
t = 1, . . . , T. If we dualize the capacity con-
straints (20) with some vector Λ= (λ 1 , . . . , λ T )
4.1.2. Sub-gradient optimization method
≥ 0, we get the LR of the multiple item ELSIDD
problem:
Our sub-gradient method starts with vector Λ 1 =
0, i.e., the initial Lagrangian multiplier vector is a
N T 0 vector of dimension T. Then the method moves
X X
z(Λ) = max p it D it to vectors (points) Λ 1 , Λ 2 , and so on. When the
i=1 t=1 method is at Λ = Λ k , we solve the LR of the mul-
N T
X X tiple item ELSIDD problem for Λ k (i.e. determine
− (S it y it + c it x it + h it I it )
z(Λ k )) and find optimal values of vectors x i , y i ,
i=1 t=1 ∗ ∗
I i , D i U i , which we denote by x (Λ k ), y (Λ k ),
i
i
T N
∗
∗
∗
X X I (Λ k ), D (Λ k ) and U (Λ k ) for i = 1, . . . , N, re-
+ λ t (C t − x it ) (22) i i i
spectively. Substituting these optimal values, we
t=1 i=1
compute the gradient vector of the objective func-
subject to
tion z(Λ) at Λ = Λ k . This gradient vector is equal
(x i , y i , I i , D i , U i ) ∈ S i i = 1, . . . , N. (23) h i
∂z(Λ) ∂z(Λ) ∂z(Λ)
to ∇z(Λ) = , , . . . , ,
Λ=Λ k ∂λ 1 ∂λ 2 ∂λ T
Λ=Λ k
251