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 cons...

Full description

Saved in:
Bibliographic Details
Published in:Operations research 2010-01, Vol.58 (1), p.59-67
Main Authors: Van den Heuvel, Wilco, Wagelmans, Albert P. M.
Format: Article
Language:English
Subjects:
Analysis
analysis of algorithms
Applied sciences
approximations/heuristics
Capital costs
Carrying costs
Closing costs
Cost analysis
Cost efficiency
Economic costs
Economic lot size
Exact sciences and technology
Heuristic
Heuristic programming
Heuristics
Inventory control
Inventory control, production control. Distribution
inventory/production
Operational research and scientific management
Operational research. Management science
Operations research
Optimal solutions
planning
Production costs
Production scheduling
Ratios
Scheduling algorithms
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0030-364X
1526-5463
DOI:10.1287/opre.1080.0662