Progress with single-item lot-sizing

The goal in this paper is to look at the history of the single-item uncapacitated lot-sizing (ULS) problem that was apparently well-solved in 1958, and point out a variety of new results that have been obtained in the last few years. For young researchers there is perhaps a moral: the important questions may not have been asked or may change with time, so it is wrong to assume that previous generations have solved all the easy questions and only left them the hard ones! A secondary goal is to indicate the practical reasons for continuing interest in this model. The outline of the paper is as follows. First we present the simplest multi-item model of practical interest and indicate how various solution algorithms lead naturally to ULS subproblems. We then take a historical viewpoint starting in 1958. In Section 3 (1958–1975) we describe the basic results of Wagner–Whitin on the structure of optimal solutions leading to a dynamic programming algorithm. We then mention briefly some of the important extensions to the model analysed up to the early 70s. In Section 4 (1975–1990) we describe some important reformulations either involving additional variables or the addition of valid inequalities, and indicate also how they can be used in practice. In Section 5 (1990–present) we cite some surprising new results, in particular the improvements in the dynamic programming algorithm and the simplification of the formulations when a ‘Wagner–Whitin’ cost structure is present. We terminate with a brief indication of work in progress on some of the more important extensions to ULS, namely models with capacities and start-up costs and times, as well as a new profit-maximising variant of the ULS model.