Performance of heuristics for the uncapacitated lot size problem

Although the uncapacitated lot-size problem can be solved optimally very efficiently, heuristics are oftne 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, bounds are obtained 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. The paper also shows 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, the present analysis reveals that a small change in the definition of a heuristic can often have a significant impact on its performance.