This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Van Vyve, M. Search for Related Content

Algorithms for Single-Item Lot-Sizing Problems with Constant Batch Size

n-side, Chemin du Cyclotron 6, 1348 Louvain-la-Neuve, Belgium
mathieu.vanvyve{at}gmail.com

The main result of this paper is an O(n³) algorithm for the single-item lot-sizing problem with constant batch size and backlogging. We consider a general number of installable batches, i.e., in each time period t we may produce up to m_t batches, where the m_t are given and time-dependent. This generalizes earlier results as we consider backlogging and a general number of maximum batches. We also give faster algorithms for three special cases of this general problem. When backlogging is not allowed and the costs satisfy the Wagner-Whitin property, the problem is solvable in O(n² log n) time. When the production in each period is required to be either zero or equal to the installed capacity, it is possible to solve the problem with and without backlogging in O(n²) and O(n log n) time, respectively.

Key Words: capacitated lot-sizing; complexity
History: Received: June 3, 2005; revision received: June 26, 2006;