Skip to Main content Skip to Navigation
Journal articles

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
Contributor : Stéphane Dauzère-Pérès <>
Submitted on : Wednesday, February 24, 2016 - 9:28:00 AM
Last modification on : Wednesday, June 24, 2020 - 4:19:24 PM



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⟩



Record views