Publication:
An Integrated Lagrangean Relaxation-Simulated Annealing Approach to the Multi-level Multi-item capacitated lot sizing problem

No Thumbnail Available

Date

2000-12-20

Authors

Özdamar, Linet
Barbarasoğlu, G

Journal Title

Journal ISSN

Volume Title

Publisher

ELSEVIER SCIENCE BV, PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS

Research Projects

Organizational Units

Journal Issue

Abstract

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.

Description

Keywords

lot sizing with setup times, Lagrangean relaxation, global search, simulated annealing, heuristics, lot kurulum süreleri ile boyutlandırma, Lagrangean gevşeme, global arama, ısıl işlem, sezgiseller

Citation