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.

, , , , , , , , , , , , , , , , ,,
ERIM Top-Core Articles , Econometric Institute Reprint Series
Operations Research
Erasmus Research Institute of Management

van den Heuvel, W., & Wagelmans, A. (2010). Worst-case analysis for a general class of online lot-sizing heuristics. Operations Research, 58(1), 59–67. doi:10.1287/opre.1080.0662