Progress with single-item lot-sizing (Q1390225)

The goal in this talk 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. The outline of the talk 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 analyzed up to the early 70's. 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-maximizing variant of the ULS model.