IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v214y2011i2p428-441.html
   My bibliography  Save this article

An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging

Author

Listed:
  • Wu, Tao
  • Shi, Leyuan
  • Geunes, Joseph
  • AkartunalI, Kerem

Abstract

This paper proposes two new mixed integer programming models for capacitated multi-level lot-sizing problems with backlogging, whose linear programming relaxations provide good lower bounds on the optimal solution value. We show that both of these strong formulations yield the same lower bounds. In addition to these theoretical results, we propose a new, effective optimization framework that achieves high quality solutions in reasonable computational time. Computational results show that the proposed optimization framework is superior to other well-known approaches on several important performance dimensions.

Suggested Citation

  • Wu, Tao & Shi, Leyuan & Geunes, Joseph & AkartunalI, Kerem, 2011. "An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging," European Journal of Operational Research, Elsevier, vol. 214(2), pages 428-441, October.
    • Handle: RePEc:eee:ejores:v:214:y:2011:i:2:p:428-441
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221711003730
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Kuik, R. & Salomon, M., 1990. "Multi-level lot-sizing problem: Evaluation of a simulated-annealing heuristic," European Journal of Operational Research, Elsevier, vol. 45(1), pages 25-37, March.
    2. 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.
    3. 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).
    4. Peter J. Billington & John O. McClain & L. Joseph Thomas, 1983. "Mathematical Programming Approaches to Capacity-Constrained MRP Systems: Review, Formulation and Problem Reduction," Management Science, INFORMS, vol. 29(10), pages 1126-1141, October.
    5. Millar, Harvey H. & Yang, Minzhu, 1994. "Lagrangian heuristics for the capacitated multi-item lot-sizing problem with backordering," International Journal of Production Economics, Elsevier, vol. 34(1), pages 1-15, February.
    6. 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.
    7. Tang, Ou, 2004. "Simulated annealing in lot sizing problems," International Journal of Production Economics, Elsevier, vol. 88(2), pages 173-181, March.
    8. 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.
    9. 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.
    10. B Karimi & S M T Fatemi Ghomi & J M Wilson, 2006. "A tabu search heuristic for solving the CLSP with backlogging and set-up carry-over," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(2), pages 140-147, February.
    11. 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).
    12. Leyuan Shi & Sigurdur Ólafsson & Qun Chen, 2001. "An Optimization Framework for Product Design," Management Science, INFORMS, vol. 47(12), pages 1681-1692, December.
    13. C H Cheng & M S Madan & Y Gupta & S So, 2001. "Solving the capacitated lot-sizing problem with backorder consideration," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 52(8), pages 952-959, August.
    14. 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.
    15. Ioannis Ganas & Sotirios Papachristos, 2005. "The Single-Product Lot-Sizing Problem with Constant Parameters and Backlogging: Exact Results, a New Solution, and All Parameter Stability Regions," Operations Research, INFORMS, vol. 53(1), pages 170-176, February.
    16. Song, Yuyue & Chan, Gin Hor, 2005. "Single item lot-sizing problems with backlogging on a single machine at a finite production rate," European Journal of Operational Research, Elsevier, vol. 161(1), pages 191-202, February.
    17. 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.
    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. Carlos Mencía & María Sierra & Ramiro Varela, 2013. "Depth-first heuristic search for the job shop scheduling problem," Annals of Operations Research, Springer, vol. 206(1), pages 265-296, July.
    2. He, Yan & Wu, Tao & Zhang, Canrong & Liang, Zhe, 2015. "An improved MIP heuristic for the intermodal hub location problem," Omega, Elsevier, vol. 57(PB), pages 203-211.
    3. Wu, Tao & Xiao, Fan & Zhang, Canrong & Zhang, Defu & Liang, Zhe, 2019. "Regression and extrapolation guided optimization for production–distribution with ship–buy–exchange options," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 129(C), pages 15-37.
    4. Almeder, Christian & Klabjan, Diego & Traxler, Renate & Almada-Lobo, Bernardo, 2015. "Lead time considerations for the multi-level capacitated lot-sizing problem," European Journal of Operational Research, Elsevier, vol. 241(3), pages 727-738.
    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 & 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.
    7. Tao Wu & Leyuan Shi & Jie Song, 2012. "An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times," Annals of Operations Research, Springer, vol. 196(1), pages 635-650, July.
    8. Liang, Zhe & He, Yan & Wu, Tao & Zhang, Canrong, 2015. "An informative column generation and decomposition method for a production planning and facility location problem," International Journal of Production Economics, Elsevier, vol. 170(PA), pages 88-96.
    9. Zhenyuan Liu & Lei Xiao & Jing Tian, 2016. "An activity-list-based nested partitions algorithm for resource-constrained project scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4744-4758, August.
    10. Shuai Wang & Jizhuang Hui & Bin Zhu & Ying Liu, 2022. "Adaptive Genetic Algorithm Based on Fuzzy Reasoning for the Multilevel Capacitated Lot-Sizing Problem with Energy Consumption in Synchronizer Production," Sustainability, MDPI, vol. 14(9), pages 1-24, April.
    11. Lau, Kwok Hung, 2013. "Measuring distribution efficiency of a retail network through data envelopment analysis," International Journal of Production Economics, Elsevier, vol. 146(2), pages 598-611.
    12. Gruson, Matthieu & Cordeau, Jean-François & Jans, Raf, 2018. "The impact of service level constraints in deterministic lot sizing with backlogging," Omega, Elsevier, vol. 79(C), pages 91-103.
    13. 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. Tao Wu, 2022. "Predictive Search for Capacitated Multi-Item Lot Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 385-406, January.
    2. 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.
    3. 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.
    4. 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.
    5. Tao Wu & Leyuan Shi & Jie Song, 2012. "An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times," Annals of Operations Research, Springer, vol. 196(1), pages 635-650, July.
    6. Nadjib Brahimi & Tarik Aouam, 2016. "Multi-item production routing problem with backordering: a MILP approach," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1076-1093, February.
    7. 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.
    8. 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.
    9. 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.
    10. Tao Wu & Leyuan Shi & Joseph Geunes & Kerem Akartunalı, 2012. "On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times," Journal of Global Optimization, Springer, vol. 53(4), pages 615-639, August.
    11. Hartmut Stadtler & Malte Meistering, 2019. "Model formulations for the capacitated lot-sizing problem with service-level constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(4), pages 1025-1056, December.
    12. 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.
    13. Marcos Mansano Furlan & Maristela Oliveira Santos, 2017. "BFO: a hybrid bees algorithm for the multi-level capacitated lot-sizing problem," Journal of Intelligent Manufacturing, Springer, vol. 28(4), pages 929-944, April.
    14. Kimms, Alf & Drexl, Andreas, 1996. "Multi-level lot sizing: A literature survey," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 405, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    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. Daniel Quadt & Heinrich Kuhn, 2009. "Capacitated lot‐sizing and scheduling with parallel machines, back‐orders, and setup carry‐over," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(4), pages 366-384, June.
    17. 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.
    18. Liang, Zhe & He, Yan & Wu, Tao & Zhang, Canrong, 2015. "An informative column generation and decomposition method for a production planning and facility location problem," International Journal of Production Economics, Elsevier, vol. 170(PA), pages 88-96.
    19. Dziuba, Daryna & Almeder, Christian, 2023. "New construction heuristic for capacitated lot sizing problems," European Journal of Operational Research, Elsevier, vol. 311(3), pages 906-920.
    20. Drexl, Andreas & Haase, Knut, 1992. "A new type of model for multi-item capacitated dynamic lotsizing and scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 286, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    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:eee:ejores:v:214:y:2011:i:2:p:428-441. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.