Worst-Case Analysis for a General Class of Online Lot-Sizing Heuristics

• 成果类型: Article
• 署名作者: Van den Heuvel, Wilco; Wagelmans, Albert P. M.
• 署名单位: Erasmus University Rotterdam; Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam; Erasmus University Rotterdam - Excl Erasmus MC
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1080.0662
• 发表日期: 2010
• 页码: 59-67
• 关键词: performance

摘要

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 online 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 online heuristic has a worst-case ratio of at least 2.