| Abstract: |
Proofs from complexity theory as well as computational experiments indicate
that most lot sizing problems are hard to solve. Because these problems are so
difficult, various solution techniques have been proposed to solve them. In
the past decade, meta-heuristics such as tabu search, genetic algorithms and
simulated annealing, have become popular and efficient tools for solving hard
combinational optimization problems. We review the various meta-heuristics
that have been specifically developed to solve lot sizing problems, discussing
their main components such as representation, evaluation neighborhood
definition and genetic operators. Further, we briefly review other solution
approaches, such as dynamic programming, cutting planes, Dantzig-Wolfe
decomposition, Lagrange relaxation and dedicated heuristics. This allows us to
compare these techniques. Understanding their respective advantages and
disadvantages gives insight into how we can integrate elements from several
solution approaches into more powerful hybrid algorithms. Finally, we discuss
general guidelines for computational experiments and illustrate these with
several examples. |