Page 52 - IJOCTA-15-2

Multiple item economic lot sizing problem with inventory dependent demand
can be implemented in polynomial time. 39 and 40 on the Lagrangian relaxation method. Briefly,
work on capacitated single item lot sizing prob- in the Lagrangian relaxation method, the con-
lems where demand is a function of price. They straints that make the problem complicated are
assume production capacities are time-invariant removed from the constraint set and added to the
and develop polynomial time algorithms. 41 con- objective function with a vector of penalty mul-
siders a multi-product lot sizing and pricing prob- tipliers, which are also called Langrangian mul-
lem under a finite production capacity constraint, tipliers. This process of replacing a constraint is
where the demands for each product is a linear sometimes called the dualization of the constraint.
function of the price and is also affected by the The problem obtained this way is called the La-
complementarity or substitution characteristics of grangian relaxation of the original problem.
other products. Some problems consist of polynomially solv-
42
proposes a polynomial time dynamic pro- able sub-problems that are combined (or tied)
gramming algorithm to solve a single item un- with some constraints, making them complicated
capacitated lot sizing problem in a two-echelon to solve. When these tying constraints are du-
structure, under the assumption that demand is alized, the resulting problem is decomposed into
a function of price. In addition to these studies, 43 several easy-to-solve independent sub-problems.
develops a branch-and-price algorithm for a mul- For instance, in the capacitated multiple item
tiple item capacitated ELS problem with setup ELS problems, capacity constraints are usually
times where demand is affected by the pricing the only tying constraints. If these capacity con-
decisions. 44 and 45 can be mentioned for more re- straints are dualized, the resulting problem is just
cent work on ELS models where demand can be a group of independent single item ELS prob-
controlled by pricing decisions. lems. This special structure of multiple item ELS
The first paper that incorporates stock depen- problems inspired many researchers to apply the
4
dent demand in an ELS framework is, which as- Lagrangian relaxation method to such problems
sumes that the demand in each period is a concave (see, 47–50 and 51 ).
function of the amount of inventory available in Most of the time, combinatorial optimization
that period (after production). To the best of our problems can not be solved efficiently by exact al-
knowledge, their study is the only published work gorithms. As a result, people often utilize meta-
in the ELS literature where available inventory heuristic methods, which can be tailored to search
stimulates demand. They propose a polynomial the solution set of those problems with the hope
time dynamic programming algorithm for the un- of finding a good enough solution in a reason-
capacitated version of the problem. They also able amount of time. Metaheuristics like Tabu
prove that the problem is NP-hard even under Search Algorithm (TSA), Simulated Annealing
time-invariant production capacities. As we men- (SA), and Genetic Algorithms (GA) have gained
tioned earlier, the work we present in this paper popularity in recent years for handling complex
4
is an extension of the work in, which we will fre- combinatorial problems in various fields. 52–68 Ar-
quently refer to as single item ELSIDD. Needless tificial Bee Colony Optimization is another meta-
to say, since the single item capacitated ELSIDD heuristic that is gaining popularity. 69 Multiple
problem is NP-hard, the multiple item capaci- item capacitated ELS problems are also among
tated ELSIDD problem is also NP-hard. Indeed, those problems where the application of meta-
30
it is well known that (see ) even with two items, heuristic methods has proven useful. Numerous
ELS with production capacities is NP-hard un- examples of applications of all these metaheuris-
der conditions similar to those where the single tic methods to the capacitated ELS problem can
item problem can be solved in polynomial time. be found in the literature. 70 works on multiple
This justifies the use of heuristic solution methods item capacitated ELS problems considering back
to capacitated multiple item ELS problems. This orders and develop two hybrid heuristics: the
paper proposes a Lagrangian relaxation method GA/SA algorithm and Lagrangian relaxation/SA
to find an initial solution to the multiple item EL- algorithm. They conclude that Lagrangian relax-
SIDD. Then, starting with this solution, we im- ation provides tight upper bounds and promis-
plement a Tabu Search algorithm to find better ing initial solutions, and note that a hybrid La-
solutions. grangian relaxation/SA algorithm provides bet-
The Lagrangian relaxation method has been ter results. Also, 71 has a comprehensive review
utilized for decomposing problems since the of applications of Genetic algorithms for various
1970s. It is a well-known technique for finding economic lot-sizing problems. 72 utilizes the TSA
good lower or upper bounds in some problem in capacitated economic lot sizing problems. 73 de-
classes. 46 comprehensively reviews the work done velop TSA for economic lot sizing problem with
247