HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Heuristics for the multi-item capacitated lot-sizing problem with lost sales

Abstract : This paper deals with the Multi-item Capacitated Lot-Sizing problem with setup times and lost sales. Because of lost sales, demands can be partially or totally lost. To find a good lower bound, we use a Lagrangian relaxation of the capacity constraints, when single-item uncapacitated lot-sizing problems with lost sales have to be solved. Each subproblem is solved using an adaptation of the O(T^2) dynamic programming algorithm of Aksen et al. [5]. To find feasible solutions, we propose a non-myopic heuristic based on a probing strategy and a refining procedure. We also propose a metaheuristic based on the adaptive large neighborhood search principle to improve solutions. Some computational experiments showing the effectiveness and limitation of each approach are presented.
Complete list of metadata

https://hal-emse.ccsd.cnrs.fr/emse-00733895
Contributor : Stéphane Dauzère-Pérès Connect in order to contact the contributor
Submitted on : Thursday, September 20, 2012 - 8:56:27 AM
Last modification on : Monday, November 16, 2020 - 11:58:02 AM

Identifiers

Citation

Nabil Absi, Boris Detienne, Stéphane Dauzère-Pérès. Heuristics for the multi-item capacitated lot-sizing problem with lost sales. Computers and Operations Research, Elsevier, 2013, 40 (1), pp.264-272. ⟨10.1016/j.cor.2012.06.010⟩. ⟨emse-00733895⟩

Share

Metrics

Record views

173