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.
Document type :
Journal articles
Complete list of metadatas

https://hal-emse.ccsd.cnrs.fr/emse-01278278
Contributor : Stéphane Dauzère-Pérès <>
Submitted on : Wednesday, February 24, 2016 - 9:28:00 AM
Last modification on : Friday, March 15, 2019 - 1:14:36 AM

Identifiers

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⟩

Share

Metrics

Record views

162