2007-10-31
Worst case analysis for a general class of on-line lot-sizing heuristics.
Publication
Publication
Report / Econometric Institute, Erasmus University Rotterdam
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 | |
---|---|
Erasmus School of Economics | |
hdl.handle.net/1765/10859 | |
Econometric Institute Research Papers | |
Report / Econometric Institute, Erasmus University Rotterdam | |
Organisation | Erasmus School of Economics |
van den Heuvel, W., & Wagelmans, A. (2007). Worst case analysis for a general class of on-line lot-sizing heuristics. (No. EI 2007-46). Report / Econometric Institute, Erasmus University Rotterdam. Retrieved from http://hdl.handle.net/1765/10859 |