Worst-case analysis for a general class of online lot-sizing heuristics
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||Analysis of algorithms, Approximations/heuristics, Classical economics, Cost parameters, Fixed time, General class, Heuristic methods, Infinite time horizon, Inventory/production, Lot sizing, Lot sizing problems, Planning, Problem instances, Production/scheduling, Time invariants, Worst-case analysis, Worst-case instances, Worst-case performance|
|Persistent URL||dx.doi.org/10.1287/opre.1080.0662, hdl.handle.net/1765/19322|
|Series||ERIM Top-Core Articles , Econometric Institute Reprint Series|
van den Heuvel, W, & Wagelmans, A.P.M. (2010). Worst-case analysis for a general class of online lot-sizing heuristics. Operations Research, 58(1), 59–67. doi:10.1287/opre.1080.0662