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.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Erasmus University Rotterdam, Econometric Institute in its series Econometric Institute Report with number
EI 2007-46 Revision_Date: 2009-11-06.