Template-Type: ReDIF-Paper 1.0
Author-Name: van den Heuvel, W.
Author-Name-Last: van den Heuvel
Author-Name-First: Wilco
Author-Person: pva62
Author-Name: Wagelmans, A.P.M.
Author-Name-Last: Wagelmans
Author-Name-First: Albert
Title: Worst case analysis for a general class of on-line lot-sizing heuristics.
Abstract: 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.
Creation-Date: 2007-10-31
File-URL: https://repub.eur.nl/pub/10859/Van%20den%20Heuvel%20EI%202007-46.pdf
File-Format: application/pdf
Series: RePEc:ems:eureir
Number: EI 2007-46
Handle: RePEc:ems:eureir:10859