Performance of heuristics for the uncapacitated lot‐size problem

Although the uncapacitated lot‐size problem can be solved optimally very efficiently, heuristics are often used instead in practice. Recent research on the performance of these heuristics has focused on worst‐case analysis and empirical testing. This article extends earlier worst‐case results, for several of the commonly used heuristics, to more specific problem classes to obtain a better understanding of when a heuristic can be expected to perform well and when it is likely to perform poorly. In particular, we obtain bounds for the finite‐horizon problem (earlier results all assume an infinite horizon) and for problems in which demand is (i) constant, and (ii) bounded from above or below. We also show how the heuristics can be classified into three categories, with heuristics in each category using similar rules to construct feasible production schedules. Using this categorization, our analysis reveals that a small change in the definition of a heuristic can often have a significant impact on its performance. © 1992 John Wiley & Sons, Inc.