Worst case analysis for a general class of on-line lot-sizing 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 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.
|Publisher||Erasmus School of Economics (ESE)|
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