IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v43y1996i2p169-189.html
   My bibliography  Save this article

Detection of minimal forecast horizons in dynamic programs with multiple indicators of the future

Author

Listed:
  • Awi Federgruen
  • Michal Tzur

Abstract

Many sequential planning problems can be represented as a shortest path problem in an acyclic network. This includes all deterministic dynamic programs as well as certain stochastic sequential decision problems. In this article, we identify a large class of shortest path problems for which a general efficient algorithm for the simultaneous solution and detection of minimal forecast horizons is developed. Detection of a such minimal forecast horizons is essential when accurate information regarding various relevant parameters is obtained progressively, i.e., when the initial information is restricted to a limited horizon of “future” stages only. We describe five classes of planning problems which can be efficiently addressed by the general algorithm. These classes deal with multi‐item joint replenishment systems, combined inventory and routing problems, machine scheduling issues, single item stochastic inventory settings and routing problems in the plane and in space. © 1996 John Wiley & Sons, Inc.

Suggested Citation

  • Awi Federgruen & Michal Tzur, 1996. "Detection of minimal forecast horizons in dynamic programs with multiple indicators of the future," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(2), pages 169-189, March.
    • Handle: RePEc:wly:navres:v:43:y:1996:i:2:p:169-189
    DOI: 10.1002/(SICI)1520-6750(199603)43:23.0.CO;2-8
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/(SICI)1520-6750(199603)43:23.0.CO;2-8
    Download Restriction: no
    File URL: https://libkey.io/10.1002/(SICI)1520-6750(199603)43:23.0.CO;2-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Dimitris J. Bertsimas & Garrett van Ryzin, 1991. "A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane," Operations Research, INFORMS, vol. 39(4), pages 601-615, August.
    2. Bertsimas, Dimitris & Van Ryzin, Garrett., 1991. "A stochastic and dynamic vehicle routing problem in the Euclidean plane," Working papers 3286-91., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    3. Dimitris J. Bertsimas & Garrett van Ryzin, 1993. "Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles," Operations Research, INFORMS, vol. 41(1), pages 60-76, February.
    4. Robert C. Carlson & James V. Jucker & Dean H. Kropp, 1979. "Less Nervous MRP Systems: A Dynamic Economic Lot-Sizing Approach," Management Science, INFORMS, vol. 25(8), pages 754-761, August.
    5. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    6. Suresh Chand & Suresh Sethi, 1982. "Planning horizon procedures for machine replacement models with several possible replacement alternatives," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 29(3), pages 483-493, September.
    7. Gary D. Eppen & F. J. Gould & B. Peter Pashigian, 1969. "Extensions of the Planning Horizon Theorem in the Dynamic Lot Size Model," Management Science, INFORMS, vol. 15(5), pages 268-277, January.
    8. Chand, Suresh, 1982. "Lot sizing for products with finite demand horizon and periodic review inventory policy," European Journal of Operational Research, Elsevier, vol. 11(2), pages 145-148, October.
    9. Suresh Sethi & Suresh Chand, 1979. "Planning Horizon Procedures for Machine Replacement Models," Management Science, INFORMS, vol. 25(2), pages 140-151, February.
    10. Suresh Chand & Suresh P. Sethi & Gerhard Sorger, 1992. "Forecast Horizons in the Discounted Dynamic Lot Size Model," Management Science, INFORMS, vol. 38(7), pages 1034-1048, July.
    11. Rolf A. Lundin & Thomas E. Morton, 1975. "Planning Horizons for the Dynamic Lot Size Model: Zabel vs. Protective Procedures and Computational Results," Operations Research, INFORMS, vol. 23(4), pages 711-734, August.
    12. Awi Federgruen & Michal Tzur, 1994. "Minimal Forecast Horizons and a New Planning Procedure for the General Dynamic Lot Sizing Model: Nervousness Revisited," Operations Research, INFORMS, vol. 42(3), pages 456-468, June.
    13. Suresh Chand & Thomas E. Morton, 1982. "A Perfect Planning Horizon Procedure for a Deterministic Cash Balance Problem," Management Science, INFORMS, vol. 28(6), pages 652-669, June.
    14. Dev Joneja, 1990. "The Joint Replenishment Problem: New Heuristics and Worst Case Performance Bounds," Operations Research, INFORMS, vol. 38(4), pages 711-723, August.
    15. T. Goldstein & S. P. Ladany & A. Mehrez, 1986. "Technical Note—A Dual Machine Replacement Model: A Note on Planning Horizon Procedures for Machine Replacements," Operations Research, INFORMS, vol. 34(6), pages 938-941, December.
    16. Edward Zabel, 1964. "Some Generalizations of an Inventory Planning Horizon Theorem," Management Science, INFORMS, vol. 10(3), pages 465-471, April.
    17. Awi Federgruen & Michal Tzur, 1995. "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, INFORMS, vol. 41(5), pages 874-893, May.
    18. James C. Bean & Robert L. Smith, 1984. "Conditions for the Existence of Planning Horizons," Mathematics of Operations Research, INFORMS, vol. 9(3), pages 391-401, August.
    19. Suresh Chand & Thomas E. Morton, 1986. "Minimal forecast horizon procedures for dynamic lot size models," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 33(1), pages 111-122, February.
    20. Suresh Chand & Suresh P. Sethi, 1990. "A Dynamic Lot Sizing Model with Learning in Setups," Operations Research, INFORMS, vol. 38(4), pages 644-655, August.
    21. Wallace J. Hopp & Suresh K. Nair, 1991. "Timing replacement decisions under discontinuous technological change," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(2), pages 203-220, April.
    22. S. Anily & A. Federgruen, 1993. "Two-Echelon Distribution Systems with Vehicle Routing Costs and Central Inventories," Operations Research, INFORMS, vol. 41(1), pages 37-47, February.
    23. S. Anily & A. Federgruen, 1990. "One Warehouse Multiple Retailer Systems with Vehicle Routing Costs," Management Science, INFORMS, vol. 36(1), pages 92-114, January.
    24. Chelsea C. White & Lyn C. Thomas & William T. Scherer, 1985. "Reward Revision for Discounted Markov Decision Problems," Operations Research, INFORMS, vol. 33(6), pages 1299-1315, December.
    25. Alain Bensoussan & Jean‐Marie Proth & Maurice Queyranne, 1991. "A planning horizon algorithm for deterministic inventory management with piecewise linear concave costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(5), pages 729-742, October.
    26. Awi Federgruen & Michal Tzur, 1993. "The dynamic lot‐sizing model with backlogging: A simple o(n log n) algorithm and minimal forecast horizon procedure," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(4), pages 459-478, June.
    27. Fleischmann, Bernhard, 1990. "The discrete lot-sizing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 44(3), pages 337-348, February.
    28. C. Bes & S. P. Sethi, 1988. "Concepts of Forecast and Decision Horizons: Applications to Dynamic Stochastic Optimization Problems," Mathematics of Operations Research, INFORMS, vol. 13(2), pages 295-310, May.
    29. Chung-Yee Lee & Eric V. Denardo, 1986. "Rolling Planning Horizons: Error Bounds for the Dynamic Lot Size Model," Mathematics of Operations Research, INFORMS, vol. 11(3), pages 423-432, August.
    30. Suresh Chand & Suresh P. Sethi & Jean-Marie Proth, 1990. "Existence of Forecast Horizons in Undiscounted Discrete-Time Lot Size Models," Operations Research, INFORMS, vol. 38(5), pages 884-892, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Torpong Cheevaprawatdomrong & Robert L. Smith, 2004. "Infinite Horizon Production Scheduling in Time-Varying Systems Under Stochastic Demand," Operations Research, INFORMS, vol. 52(1), pages 105-115, February.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Suresh Chand & Vernon Ning Hsu & Suresh Sethi, 2002. "Forecast, Solution, and Rolling Horizons in Operations Management Problems: A Classified Bibliography," Manufacturing & Service Operations Management, INFORMS, vol. 4(1), pages 25-43, September.
    2. Fuying Jing & Zirui Lan, 2017. "Forecast horizon of multi-item dynamic lot size model with perishable inventory," PLOS ONE, Public Library of Science, vol. 12(11), pages 1-15, November.
    3. Kimms, Alf, 1996. "Stability measures for rolling schedules with applications to capacity expansion planning, master production scheduling, and lot sizing," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 418, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    4. Archis Ghate & Robert L. Smith, 2009. "Optimal Backlogging Over an Infinite Horizon Under Time-Varying Convex Production and Inventory Costs," Manufacturing & Service Operations Management, INFORMS, vol. 11(2), pages 362-368, June.
    5. Robert L. Smith & Rachel Q. Zhang, 1998. "Infinite Horizon Production Planning in Time-Varying Systems with Convex Production and Inventory Costs," Management Science, INFORMS, vol. 44(9), pages 1313-1320, September.
    6. Kimms, A, 1998. "Stability Measures for Rolling Schedules with Applications to Capacity Expansion Planning, Master Production Scheduling, and Lot Sizing," Omega, Elsevier, vol. 26(3), pages 355-366, June.
    7. Milind Dawande & Srinagesh Gavirneni & Sanjeewa Naranpanawe & Suresh Sethi, 2007. "Forecast Horizons for a Class of Dynamic Lot-Size Problems Under Discrete Future Demand," Operations Research, INFORMS, vol. 55(4), pages 688-702, August.
    8. Alain Bensoussan & Jean‐Marie Proth & Maurice Queyranne, 1991. "A planning horizon algorithm for deterministic inventory management with piecewise linear concave costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(5), pages 729-742, October.
    9. Marshall Fisher & Kamalini Ramdas & Yu-Sheng Zheng, 2001. "Ending Inventory Valuation in Multiperiod Production Scheduling," Management Science, INFORMS, vol. 47(5), pages 679-692, May.
    10. Michael Bastian, 1992. "A perfect lot‐tree procedure for the discounted dynamic lot‐size problem with speculation," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(5), pages 651-668, August.
    11. S. Bylka & S. Sethi & G. Sorger, 1992. "Minimal forecast horizons in equipment replacement models with multiple technologies and general switching costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(4), pages 487-507, June.
    12. Jans, R.F. & Degraeve, Z., 2005. "Modeling Industrial Lot Sizing Problems: A Review," ERIM Report Series Research in Management ERS-2005-049-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    13. Stanislaw Bylka, 1997. "Strong turnpike policies in the single‐item capacitated lot‐sizing problem with periodical dynamic parameter," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(8), pages 775-790, December.
    14. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    15. Wallace J. Hopp & Suresh K. Nair, 1991. "Timing replacement decisions under discontinuous technological change," Naval Research Logistics (NRL), John Wiley & Sons, vol. 38(2), pages 203-220, April.
    16. Awi Federgruen & Michal Tzur, 1993. "The dynamic lot‐sizing model with backlogging: A simple o(n log n) algorithm and minimal forecast horizon procedure," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(4), pages 459-478, June.
    17. Awi Federgruen & Michal Tzur, 1999. "Time‐partitioning heuristics: Application to one warehouse, multiitem, multiretailer lot‐sizing problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(5), pages 463-486, August.
    18. Drexl, Andreas & Kimms, Alf, 1996. "Lot sizing and scheduling: Survey and extensions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 421, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    19. Richter, Knut & Sombrutzki, Mirko, 2000. "Remanufacturing planning for the reverse Wagner/Whitin models," European Journal of Operational Research, Elsevier, vol. 121(2), pages 304-315, March.
    20. Bhattacharjee, Sudip & Ramesh, R., 2000. "A multi-period profit maximizing model for retail supply chain management: An integration of demand and supply-side mechanisms," European Journal of Operational Research, Elsevier, vol. 122(3), pages 584-601, May.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wly:navres:v:43:y:1996:i:2:p:169-189. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.