This Article Full Text (PDF) e-companion Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Van den Heuvel, W. Articles by Wagelmans, A. P. M.

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

Econometric Institute and Erasmus Research Institute of Management, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands
Econometric Institute and Erasmus Research Institute of Management, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands
wvandenheuvel{at}ese.eur.nl
wagelmans{at}ese.eur.nl

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.

Subject classifications: analysis of algorithms; inventory/production; approximations/heuristics; production/scheduling; planning.
History: Received August 2007; revision received May 2008; accepted July 2008.