An integrated Lagrangean relaxation-simulated annealing approach to the multi-level multi-item capacitated lot sizing problem

This study proposes a heuristic approach for the solution of the dynamic multi-level multi-item capacitated lot sizing problem (MLCLSP) with general product structures. The difficulty in solving MLCLSP is to provide capacity-feasible lot-sizes while maintaining the non-negativity of the inventories belonging to the items in the lower levels of the product structures. The proposed technique aims to resolve this issue by combining the capability of the Lagrangean relaxation to decompose the hard-to-solve problems into smaller subproblems and the intensive search capability of the simulated annealing. As the first attempt, two Lagrangean relaxation schemes are designed and different versions of simulated annealing are incorporated into relaxation designs as the Lagrangean heuristic. Then in order to improve the performance of the heuristic, a Phase-1 procedure is developed as a recursive algorithm to restore capacity feasibility. It is observed that the best results are obtained by executing first Phase-1 procedure and then simulated annealing approach with only improving moves in each Lagrangean cycle. The performance of these approaches is compared by using the benchmark problems available in literature. (C) 2000 Elsevier Science B.V. All rights reserved.