Worst-case analysis for a general class of online lot-sizing heuristics
January 2010
Article
volume 58, issue 1 pp 59-67.
| Related Files |
|---|
|
Redirect to publisher's version
(publisher's version.url.txt, 40 bytes) |
Repository contains one additional file which is not publicly available
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.
Keywords
- Planning
- Analysis of algorithms
- Approximations/heuristics
- Classical economics
- Cost parameters
- General class
- Heuristic methods
- Infinite time horizon
- Inventory/production
- Lot sizing problems
- Lot sizing
- Problem instances
- Production/scheduling
- Time invariants
- Fixed time
- Worst-case analysis
- Worst-case instances
- Worst-case performance
