IDEAS home Printed from https://ideas.repec.org/p/lms/mansci/mrg-0004.html
   My bibliography  Save this paper

Probabilistic Analysis of Multi-Item Capacitated Lot Sizing Problems

Author

Listed:
  • Awi Federgruen

    (Graduate School of Business, Columbia University)

  • Joern Meissner

    (Department of Management Science, Lancaster University Management School)

Abstract

This paper conducts a probabilistic analysis of an important class of heuristics for multiitem capacitated lot sizing problems. We characterize the asymptotic performance of so-called progressive interval heuristics as T, the length of the planning horizon, goes to infinity, assuming the data are realizations of a stochastic process of the following type: the vector of cost parameters follows an arbitrary process with bounded support, while the sequence of aggregate demand and capacity pairs is generated as an independent sequence with a common general bivariate distribution, which may be of unbounded support. We show that important subclasses of the class of progressive interval heuristics can be designed to be asymptotically optimal with probability one, while running with a complexity bound which grows linearly with the number of items N and slightly faster than quadratically with T. We generalize our results for the case where the items' shelf life is uniformly bounded, e.g. because of perishability considerations.

Suggested Citation

  • Awi Federgruen & Joern Meissner, 2004. "Probabilistic Analysis of Multi-Item Capacitated Lot Sizing Problems," Working Papers MRG/0004, Department of Management Science, Lancaster University, revised Apr 2005.
    • Handle: RePEc:lms:mansci:mrg-0004
    as

    Download full text from publisher

    File URL: http://www.meiss.com/en/publications/probabilistic-lot-sizing.html
    File Function: Webpage
    Download Restriction: no
    File URL: http://www.meiss.com/download/SC-02-Federgruen-Meissner.pdf
    File Function: Full Paper
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Rinnooy Kan, A. H. G., 1985. "Probabilistic Analysis Of Algorithms," Econometric Institute Archives 272328, Erasmus University Rotterdam.
    2. M. Haimovich & A. H. G. Rinnooy Kan, 1985. "Bounds and Heuristics for Capacitated Routing Problems," Mathematics of Operations Research, INFORMS, vol. 10(4), pages 527-542, November.
    3. Steven Nahmias, 1982. "Perishable Inventory Theory: A Review," Operations Research, INFORMS, vol. 30(4), pages 680-708, August.
    4. James B. Orlin, 1993. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm," Operations Research, INFORMS, vol. 41(2), pages 338-350, April.
    5. Stadtler, Hartmut, 2003. "Multilevel lot sizing with setup times and multiple constrained resources: Internally rolling schedules with lot-sizing windows," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 20204, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    6. Wansoo T. Rhee & Michel Talagrand, 1987. "Martingale Inequalities and NP-Complete Problems," Mathematics of Operations Research, INFORMS, vol. 12(1), pages 177-181, February.
    7. Lap Mui Ann Chan & David Simchi-Levi, 1998. "Probabilistic Analyses and Algorithms for Three-Level Distribution Systems," Management Science, INFORMS, vol. 44(11-Part-1), pages 1562-1576, November.
    8. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    9. Alok Aggarwal & James K. Park, 1993. "Improved Algorithms for Economic Lot Size Problems," Operations Research, INFORMS, vol. 41(3), pages 549-571, June.
    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. Retsef Levi & Andrea Lodi & Maxim Sviridenko, 2008. "Approximation Algorithms for the Capacitated Multi-Item Lot-Sizing Problem via Flow-Cover Inequalities," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 461-474, May.

    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. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    2. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.
    3. Awi Federgruen & Joern Meissner & Michal Tzur, 2007. "Progressive Interval Heuristics for Multi-Item Capacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 55(3), pages 490-502, June.
    4. Yongpei Guan, 2011. "Stochastic lot-sizing with backlogging: computational complexity analysis," Journal of Global Optimization, Springer, vol. 49(4), pages 651-678, April.
    5. Shoshana Anily, 1996. "The vehicle‐routing problem with delivery and back‐haul options," Naval Research Logistics (NRL), John Wiley & Sons, vol. 43(3), pages 415-434, April.
    6. Leon Yang Chu & Vernon Ning Hsu & Zuo‐Jun Max Shen, 2005. "An economic lot‐sizing problem with perishable inventory and economies of scale costs: Approximation solutions and worst case analysis," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(6), pages 536-548, September.
    7. 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.
    8. Chung-Lun Li & Vernon Ning Hsu & Wen-Qiang Xiao, 2004. "Dynamic Lot Sizing with Batch Ordering and Truckload Discounts," Operations Research, INFORMS, vol. 52(4), pages 639-654, August.
    9. AkartunalI, Kerem & Miller, Andrew J., 2009. "A heuristic approach for big bucket multi-level production planning problems," European Journal of Operational Research, Elsevier, vol. 193(2), pages 396-411, March.
    10. Liu, Hengyu & Zhang, Juliang & Zhou, Chen & Ru, Yihong, 2018. "Optimal purchase and inventory retrieval policies for perishable seasonal agricultural products," Omega, Elsevier, vol. 79(C), pages 133-145.
    11. Yongpei Guan & Andrew J. Miller, 2008. "Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems," Operations Research, INFORMS, vol. 56(5), pages 1172-1183, October.
    12. Minjiao Zhang & Simge Küçükyavuz & Hande Yaman, 2012. "A Polyhedral Study of Multiechelon Lot Sizing with Intermediate Demands," Operations Research, INFORMS, vol. 60(4), pages 918-935, August.
    13. Z Shen & M Dessouky & F Ordonez, 2011. "Perishable inventory management system with a minimum volume constraint," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(12), pages 2063-2082, December.
    14. Pahl, Julia & Voß, Stefan, 2014. "Integrating deterioration and lifetime constraints in production and supply chain planning: A survey," European Journal of Operational Research, Elsevier, vol. 238(3), pages 654-674.
    15. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    16. Jing, Fuying & Chao, Xiangrui, 2022. "Forecast horizons for a two-echelon dynamic lot-sizing problem," Omega, Elsevier, vol. 110(C).
    17. Sadia Samar Ali & Haripriya Barman & Rajbir Kaur & Hana Tomaskova & Sankar Kumar Roy, 2021. "Multi-Product Multi Echelon Measurements of Perishable Supply Chain: Fuzzy Non-Linear Programming Approach," Mathematics, MDPI, vol. 9(17), pages 1-27, August.
    18. Meet Patel & Uday Venkatadri & Claver Diallo & Ahsan Habib & Amirsalar Malekahmadi, 2023. "An Adaptive Sequential Decision-Making Approach for Perishable Food Procurement, Storage and Distribution Using Hyperconnected Logistics," Sustainability, MDPI, vol. 16(1), pages 1-29, December.
    19. Ravichandran, N., 1995. "Stochastic analysis of a continuous review perishable inventory system with positive lead time and Poisson demand," European Journal of Operational Research, Elsevier, vol. 84(2), pages 444-457, July.
    20. Siao-Leu Phouratsamay & Safia Kedad-Sidhoum & Fanny Pascual, 2021. "Coordination of a two-level supply chain with contracts," 4OR, Springer, vol. 19(2), pages 235-264, June.

    More about this item

    Keywords

    probabilistic analysis; supply chain management; inventory models; lot sizing; time partitioning;
    All these keywords.

    JEL classification:

    • C61 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Optimization Techniques; Programming Models; Dynamic Analysis

    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:lms:mansci:mrg-0004. 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: Joern Meissner (email available below). General contact details of provider: https://edirc.repec.org/data/degraus.html .

    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.