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 the authors 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.