FAST SOLUTION AND DETECTION OF MINIMAL FORECAST HORIZONS IN DYNAMIC PROGRAMS WITH A SINGLE INDICATOR OF THE FUTURE - APPLICATIONS TO DYNAMIC LOT-SIZING MODELS

In most dynamic planning problems, one observes that an optimal decision at any given stage depends on limited information, i.e. information pertaining to a limited set of adjacent or nearby stages. This holds in particular for planning problems over time, where an optimal decision in a given period depends on information related to a limited future time horizon, a so-called forecast horizon, only. In this paper we identify a general class of dynamic programs in which an efficient forward algorithm can be designed to solve the problem and to identify minimal forecast horizons. Such a procedure specifies necessary and sufficient conditions for a stage to arise as a forecast horizon. This class of dynamic programs includes the single-item dynamic lot-sizing model with general concave costs, both with and without backlogging, to which special attention is given.