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 on-line 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 on-line heuristic has a worst case ratio of at least 2. Furthermore, we show how the results can be used to construct heuristics with optimal worst case performance for small model horizons.

Additional Metadata
Publisher Erasmus School of Economics (ESE)
Persistent URL hdl.handle.net/1765/10859
Citation
van den Heuvel, W, & Wagelmans, A.P.M. (2007). Worst case analysis for a general class of on-line lot-sizing heuristics. (No. EI 2007-46). Report / Econometric Institute, Erasmus University Rotterdam. Erasmus School of Economics (ESE). Retrieved from http://hdl.handle.net/1765/10859