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 decisi on 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 decisi on in a given period depends on information related to a limited futur e time horizon, a so-called forecast horizon, only. In this paper we i dentify a general class of dynamic programs in which an efficient forw ard algorithm can be designed to solve the problem and to identify min imal forecast horizons. Such a procedure specifies necessary and suffi cient conditions for a stage to arise as a forecast horizon. This clas s of dynamic programs includes the single-item dynamic lot-sizing mode l with general concave costs, both with and without backlogging, to wh ich special attention is given.