A Lagrangian Heuristic for Capacitated Single Item Lot Sizing Problems

Abstract : This paper presents a new Lagrangian heuristic to solve the general capacitated single item lot sizing problem (CSILSP) where the total costs of production, setup, and inventory are to be minimized. We introduce a pre-smoothing procedure to transform the problem into a CSILSP with non-customer specific time windows and relax constraints that are specific to the CSILSP. The resulting uncapacitated single item problems with non-customer specific production time windows can be solved in polynomial time. We also analyze the performance of the Lagrangian heuristic for solving the CSILSP with non-customer specific time windows. Finally, the heuristic is adapted to the customer specific case. The introduction of pre-smoothing and the relaxation of CSILSP-specific constraints help to decrease the gap between lower bounds and upper bounds from 26.22 to 1.39 %, on average. The heuristic can be used to solve aggregate production planning problems, or can be integrated into a general procedure to solve more complex lot sizing problems.
Type de document :
Article dans une revue
4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2015, 13 (2), pp.173-198. 〈10.1007/s10288-014-0266-3〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-01278278
Contributeur : Stéphane Dauzère-Pérès <>
Soumis le : mercredi 24 février 2016 - 09:28:00
Dernière modification le : jeudi 11 janvier 2018 - 06:16:31

Identifiants

Citation

Nadjib Brahimi, Stéphane Dauzere-Peres. A Lagrangian Heuristic for Capacitated Single Item Lot Sizing Problems. 4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2015, 13 (2), pp.173-198. 〈10.1007/s10288-014-0266-3〉. 〈emse-01278278〉

Partager

Métriques

Consultations de la notice

110