Worst-Case Analysis for a General Class of Online Lot-Sizing Heuristics

Wilco van den Heuvel and Albert P. M. Wagelmans ()
Additional contact information
Albert P. M. Wagelmans: Econometric Institute and Erasmus Research Institute of Management, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands

Operations Research, 2010, vol. 58, issue 1, 59-67

Abstract: In this paper, we analyze the worst-case performance of heuristics for the classical economic lot-sizing problem with time-invariant cost parameters. We consider a general class of online heuristics that is often applied in a rolling-horizon environment. We develop a procedure to systematically construct worst-case instances for a fixed time horizon and use it to derive worst-case problem instances for an infinite time horizon. Our analysis shows that any online heuristic has a worst-case ratio of at least 2.

Keywords: analysis of algorithms; inventory/production; approximations/heuristics; production/scheduling; planning (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0662 (application/pdf)

Related works:
Working Paper: Worst case analysis for a general class of on-line lot-sizing heuristics (2007)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:58:y:2010:i:1:p:59-67

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().