Polyhedral and Lagrangian approaches for lot sizing with production time windows and setup times

In this paper, we solve the capacitated multi item lot-sizing problem with non-customer specific production time windows and setup times using two approaches: (i) using a Lagrangian relaxation-based heuristic and (ii) using reformulations and a commercial software. The results of the two approaches...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2010, Vol.37 (1), p.182-188
Main Authors: Brahimi, Nadjib, Dauzere-Peres, Stéphane, Wolsey, Laurence A.
Format: Article
Language:English
Subjects:
Applied sciences
Comparative analysis
Computer Science
Exact sciences and technology
Heuristic
Integer programming
Inventory control, production control. Distribution
Job shops
Lagrange multiplier
Lagrangian
Lot sizing
Mathematical programming
Operational research and scientific management
Operational research. Management science
Operations Research
Polyhedra
Problem solving
Studies
Time windows
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we solve the capacitated multi item lot-sizing problem with non-customer specific production time windows and setup times using two approaches: (i) using a Lagrangian relaxation-based heuristic and (ii) using reformulations and a commercial software. The results of the two approaches are analyzed and compared based on randomly generated data sets. The results show that the first approach finds feasible solution more rapidly but a steady state is reached very quickly. On the other hand the second approach quickly finds good lower bounds and finds good feasible solutions if more CPU time is allowed. It turns out that, for a wide variety of instances varying in size and other parameters, we can obtain feasible solutions within 1–5% of optimal within 10 s and also obtain solutions that are guaranteed within 1–2% of optimal within 60–120 s.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2009.04.005