| Article ID: | iaor20101085 |
| Volume: | 58 |
| Issue: | 1 |
| Start Page Number: | 59 |
| End Page Number: | 67 |
| Publication Date: | Jan 2010 |
| Journal: | Operations Research |
| Authors: | Van den Heuvel Wilco, Wagelmans Albert P M |
| Keywords: | heuristics |
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.