IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v53y2012i3p729-753.html
   My bibliography  Save this article

A computational analysis of lower bounds for big bucket production planning problems

Author

Listed:
  • Kerem Akartunalı
  • Andrew Miller

Abstract

In this paper, we analyze a variety of approaches to obtain lower bounds for multi-level production planning problems with big bucket capacities, i.e., problems in which multiple items compete for the same resources. We give an extensive survey of both known and new methods, and also establish relationships between some of these methods that, to our knowledge, have not been presented before. As will be highlighted, understanding the substructures of difficult problems provide crucial insights on why these problems are hard to solve, and this is addressed by a thorough analysis in the paper. We conclude with computational results on a variety of widely used test sets, and a discussion of future research. Copyright Springer Science+Business Media, LLC 2012

Suggested Citation

  • Kerem Akartunalı & Andrew Miller, 2012. "A computational analysis of lower bounds for big bucket production planning problems," Computational Optimization and Applications, Springer, vol. 53(3), pages 729-753, December.
    • Handle: RePEc:spr:coopap:v:53:y:2012:i:3:p:729-753
    DOI: 10.1007/s10589-012-9465-z
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-012-9465-z
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-012-9465-z?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Gary D. Eppen & R. Kipp Martin, 1987. "Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition," Operations Research, INFORMS, vol. 35(6), pages 832-848, December.
    2. 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).
    3. Alan S. Manne, 1958. "Programming of Economic Lot Sizes," Management Science, INFORMS, vol. 4(2), pages 115-135, January.
    4. GÜNLÜK, Oktay & POCHET, Yves, 2001. "Mixing mixed-integer inequalities," LIDAM Reprints CORE 1504, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. William W. Trigeiro & L. Joseph Thomas & John O. McClain, 1989. "Capacitated Lot Sizing with Setup Times," Management Science, INFORMS, vol. 35(3), pages 353-366, March.
    6. POCHET, Yves & WOLSEY, Laurence A., 1988. "Lot-size models with backlogging: strong reformulations and cutting planes," LIDAM Reprints CORE 791, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. Zeger Degraeve & Raf Jans, 2007. "A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times," Operations Research, INFORMS, vol. 55(5), pages 909-920, October.
    8. BELVAUX, Gaetan & WOLSEY, Laurence A., 2001. "Modelling practical lot-sizing problems as mixed-integer programs," LIDAM Reprints CORE 1516, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. WOLSEY, Laurence A., 2002. "Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation," LIDAM Reprints CORE 1605, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    10. BARANY, Imre & VAN ROY, Tony & WOLSEY, Laurence A., 1984. "Uncapacitated lot-sizing: the convex hull of solutions," LIDAM Reprints CORE 605, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    11. Michael Florian & Morton Klein, 1971. "Deterministic Production Planning with Concave Costs and Capacity Constraints," Management Science, INFORMS, vol. 18(1), pages 12-20, September.
    12. 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.
    13. 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.
    14. BELVAUX, Gaëtan & WOLSEY, Laurence A., 2000. "bc-prod: A specialized branch-and-cut system for lot-sizing problems," LIDAM Reprints CORE 1455, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. WOLSEY, Laurence, 2002. "Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation," LIDAM Discussion Papers CORE 2002012, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. MARCHAND, Hugues & WOLSEY, Laurence A., 1999. "The 0-1 Knapsack problem with a single continuous variable," LIDAM Reprints CORE 1390, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    17. MILLER, Andrew & NEMHAUSER, George & SAVELSBERGH, Martin, 2000. "Solving multi-item capacitated lot-sizing problems with setup times by branch-and-cut," LIDAM Discussion Papers CORE 2000039, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    18. MARCHAND, Hugues & WOLSEY, Laurence A., 2001. "Aggregation and mixed integer rounding to solve mips," LIDAM Reprints CORE 1513, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. ANILY, Shoshana & TZUR, Michal & WOLSEY, Laurence A., 2009. "Multi-item lot-sizing with joint set-up costs," LIDAM Reprints CORE 2081, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    20. Yves Pochet & Laurence A. Wolsey, 1991. "Solving Multi-Item Lot-Sizing Problems Using Strong Cutting Planes," Management Science, INFORMS, vol. 37(1), pages 53-67, January.
    21. Hartmut Stadtler, 2003. "Multilevel Lot Sizing with Setup Times and Multiple Constrained Resources: Internally Rolling Schedules with Lot-Sizing Windows," Operations Research, INFORMS, vol. 51(3), pages 487-502, June.
    22. LOPARIC, Marko & POCHET, Yves & WOLSEY, Laurence A., 2001. "The uncapacitated lot-sizing problem with sales and safety stocks," LIDAM Reprints CORE 1498, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    23. 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.
    24. Elena Katok & Holly S. Lewis & Terry P. Harrison, 1998. "Lot Sizing in General Assembly Systems with Setup Costs, Setup Times, and Multiple Constrained Resources," Management Science, INFORMS, vol. 44(6), pages 859-877, June.
    25. Hugues Marchand & Laurence A. Wolsey, 2001. "Aggregation and Mixed Integer Rounding to Solve MIPs," Operations Research, INFORMS, vol. 49(3), pages 363-371, June.
    26. Horst Tempelmeier & Matthias Derstroff, 1996. "A Lagrangean-Based Heuristic for Dynamic Multilevel Multiitem Constrained Lotsizing with Setup Times," Management Science, INFORMS, vol. 42(5), pages 738-757, May.
    27. Gabriel R. Bitran & Horacio H. Yanasse, 1982. "Computational Complexity of the Capacitated Lot Size Problem," Management Science, INFORMS, vol. 28(10), pages 1174-1186, October.
    28. Laurence A. Wolsey, 2002. "Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation," Management Science, INFORMS, vol. 48(12), pages 1587-1602, December.
    29. Pochet, Y. & Wolsey, L. A., 1994. "Polyhedra for lot-sizing with Wagner-Whitin costs," LIDAM Reprints CORE 1129, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    30. Rardin, Ronald L. & Wolsey, Laurence A., 1993. "Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems," European Journal of Operational Research, Elsevier, vol. 71(1), pages 95-109, November.
    31. Gaetan Belvaux & Laurence A. Wolsey, 2001. "Modelling Practical Lot-Sizing Problems as Mixed-Integer Programs," Management Science, INFORMS, vol. 47(7), pages 993-1007, July.
    32. Yves Pochet & Mathieu Van Vyve, 2004. "A General Heuristic for Production Planning Problems," INFORMS Journal on Computing, INFORMS, vol. 16(3), pages 316-327, August.
    33. Gaetan Belvaux & Laurence A. Wolsey, 2000. "bc --- prod: A Specialized Branch-and-Cut System for Lot-Sizing Problems," Management Science, INFORMS, vol. 46(5), pages 724-738, May.
    34. Willard I. Zangwill, 1969. "A Backlogging Model and a Multi-Echelon Model of a Dynamic Economic Lot Size Production System--A Network Approach," Management Science, INFORMS, vol. 15(9), pages 506-527, May.
    35. BARANY, Imre & VAN ROY, Tony J. & WOLSEY, Laurence A., 1984. "Strong formulations for multi-item capacitated lot sizing," LIDAM Reprints CORE 590, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    36. Awi Federgruen & Michal Tzur, 1991. "A Simple Forward Algorithm to Solve General Dynamic Lot Sizing Models with n Periods in 0(n log n) or 0(n) Time," Management Science, INFORMS, vol. 37(8), pages 909-925, August.
    37. Peter J. Billington & John O. McClain & L. Joseph Thomas, 1986. "Heuristics for Multilevel Lot-Sizing with a Bottleneck," Management Science, INFORMS, vol. 32(8), pages 989-1006, August.
    38. 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.
    39. Imre Barany & Tony J. Van Roy & Laurence A. Wolsey, 1984. "Strong Formulations for Multi-Item Capacitated Lot Sizing," Management Science, INFORMS, vol. 30(10), pages 1255-1261, October.
    40. Gabriel R. Bitran & Hirofumi Matsuo, 1986. "The Multi-Item Capacitated Lot Size Problem: Error Bounds of Manne's Formulations," Management Science, INFORMS, vol. 32(3), pages 350-359, March.
    41. M. Florian & J. K. Lenstra & A. H. G. Rinnooy Kan, 1980. "Deterministic Production Planning: Algorithms and Complexity," Management Science, INFORMS, vol. 26(7), pages 669-679, July.
    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. Doostmohammadi, Mahdi & Akartunalı, Kerem, 2018. "Valid inequalities for two-period relaxations of big-bucket lot-sizing problems: Zero setup case," European Journal of Operational Research, Elsevier, vol. 267(1), pages 86-95.
    2. Cunha, Jesus O. & Melo, Rafael A., 2021. "Valid inequalities, preprocessing, and an effective heuristic for the uncapacitated three-level lot-sizing and replenishment problem with a distribution structure," European Journal of Operational Research, Elsevier, vol. 295(3), pages 874-892.
    3. Chen, Haoxun, 2015. "Fix-and-optimize and variable neighborhood search approaches for multi-level capacitated lot sizing problems," Omega, Elsevier, vol. 56(C), pages 25-36.
    4. Wolfgang Albrecht & Martin Steinrücke, 2020. "Continuous-time scheduling of production, distribution and sales in photovoltaic supply chains with declining prices," Flexible Services and Manufacturing Journal, Springer, vol. 32(3), pages 629-667, September.
    5. Wei, Mingyuan & Qi, Mingyao & Wu, Tao & Zhang, Canrong, 2019. "Distance and matching-induced search algorithm for the multi-level lot-sizing problem with substitutable bill of materials," European Journal of Operational Research, Elsevier, vol. 277(2), pages 521-541.
    6. Kerem Akartunalı & Ioannis Fragkos & Andrew J. Miller & Tao Wu, 2016. "Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 766-780, November.
    7. Tao Wu & Zhe Liang & Canrong Zhang, 2018. "Analytics Branching and Selection for the Capacitated Multi-Item Lot Sizing Problem with Nonidentical Machines," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 236-258, May.
    8. Glomb, Lukas & Liers, Frauke & Rösel, Florian, 2022. "A rolling-horizon approach for multi-period optimization," European Journal of Operational Research, Elsevier, vol. 300(1), pages 189-206.
    9. Syed Ali, Sharifah Aishah & Doostmohammadi, Mahdi & Akartunalı, Kerem & van der Meer, Robert, 2018. "A theoretical and computational analysis of lot-sizing in remanufacturing with separate setups," International Journal of Production Economics, Elsevier, vol. 203(C), pages 276-285.
    10. Ioannis Fragkos & Zeger Degraeve & Bert De Reyck, 2016. "A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 465-482, August.
    11. Tao Wu & Kerem Akartunal? & Raf Jans & Zhe Liang, 2017. "Progressive Selection Method for the Coupled Lot-Sizing and Cutting-Stock Problem," INFORMS Journal on Computing, INFORMS, vol. 29(3), pages 523-543, August.

    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. Kerem Akartunalı & Ioannis Fragkos & Andrew J. Miller & Tao Wu, 2016. "Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 766-780, November.
    2. 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.
    3. 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.
    4. 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.
    5. Wei, Mingyuan & Qi, Mingyao & Wu, Tao & Zhang, Canrong, 2019. "Distance and matching-induced search algorithm for the multi-level lot-sizing problem with substitutable bill of materials," European Journal of Operational Research, Elsevier, vol. 277(2), pages 521-541.
    6. Tao Wu, 2022. "Predictive Search for Capacitated Multi-Item Lot Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 385-406, January.
    7. Francesco Gaglioppa & Lisa A. Miller & Saif Benjaafar, 2008. "Multitask and Multistage Production Planning and Scheduling for Process Industries," Operations Research, INFORMS, vol. 56(4), pages 1010-1025, August.
    8. Laurence A. Wolsey, 2002. "Solving Multi-Item Lot-Sizing Problems with an MIP Solver Using Classification and Reformulation," Management Science, INFORMS, vol. 48(12), pages 1587-1602, December.
    9. 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.
    10. 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.
    11. Alper Atamtürk & Simge Küçükyavuz, 2005. "Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation," Operations Research, INFORMS, vol. 53(4), pages 711-730, August.
    12. Absi, Nabil & Kedad-Sidhoum, Safia, 2008. "The multi-item capacitated lot-sizing problem with setup times and shortage costs," European Journal of Operational Research, Elsevier, vol. 185(3), pages 1351-1374, March.
    13. Silvio Alexandre de Araujo & Bert De Reyck & Zeger Degraeve & Ioannis Fragkos & Raf Jans, 2015. "Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 27(3), pages 431-448, August.
    14. 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.
    15. Helber, Stefan & Sahling, Florian, 2010. "A fix-and-optimize approach for the multi-level capacitated lot sizing problem," International Journal of Production Economics, Elsevier, vol. 123(2), pages 247-256, February.
    16. Andrea Raiconi & Julia Pahl & Monica Gentili & Stefan Voß & Raffaele Cerulli, 2017. "Tactical Production and Lot Size Planning with Lifetime Constraints: A Comparison of Model Formulations," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(05), pages 1-24, October.
    17. Degraeve, Z. & Jans, R.F., 2003. "A New Dantzig-Wolfe Reformulation And Branch-And-Price Algorithm For The Capacitated Lot Sizing Problem With Set Up Times," ERIM Report Series Research in Management ERS-2003-010-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.
    18. Zeger Degraeve & Raf Jans, 2007. "A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times," Operations Research, INFORMS, vol. 55(5), pages 909-920, October.
    19. Absi, Nabil & van den Heuvel, Wilco, 2019. "Worst case analysis of Relax and Fix heuristics for lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 279(2), pages 449-458.
    20. Atamturk, Alper & Munoz, Juan Carlos, 2002. "A Study of the Lot-Sizing Polytope," University of California Transportation Center, Working Papers qt6zz2g0z4, University of California Transportation Center.

    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:spr:coopap:v:53:y:2012:i:3:p:729-753. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.