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.

Awi Federgruen and Michal Tzur
Journal Article
Publication Date
Management Science

Full Citation

Federgruen, Awi and Michal Tzur
. “Fast solution and detection of minimal forecast horizons in dynamic programs with a single indicator of the future: Applications to dynamic lot-sizing models.”
Management Science
, (May 01, 1995):