A Lagrangian Heuristic for Capacitated Single Item Lot Sizing Problems - Mines Saint-Étienne Access content directly
Journal Articles 4OR: A Quarterly Journal of Operations Research Year : 2015

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.
No file

Dates and versions

emse-01278278 , version 1 (24-02-2016)

Identifiers

Cite

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

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More