[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Modeling and Hybridized Decomposition Approach for the Multi-level Capacitated Lot-Sizing Problem with Setup Carryover, Backlogging, and Emission Control

  • Research
  • Published:
Operations Research Forum Aims and scope Submit manuscript

Abstract

The goal of the production planning problem is to determine the optimum quantity to produce in order to satisfy demand over a predetermined planning horizon with the least amount of money spent. Making the appropriate choices in production planning will impact a manufacturing company’s performance and productivity, which is crucial to remain competitive in the market. Therefore, developing and enhancing techniques for solving production planning problems is very significant. This paper proposes a mixed-integer linear programming model for this extension of the dynamic multi-level capacitated lot-sizing under study, where setup carryover, backlogging, and emission control are considered. An item Dantzig-Wolfe decomposition-based heuristic procedure is developed, and a dynamic programming and column generation approach is used to solve the problem. We also propose a multi-step iterative capacity allocation heuristic procedure to handle any infeasibilities that arise when solving the problem. We evaluate the performance of the developed solution approach using a test data set available in the literature. Computational results show that the proposed optimization framework provides competitive solutions within a reasonable timeframe.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Data Availability

The authors confirm that the data supporting the findings of this study are available within the article.

References

  1. Billington PJ, McClain JO, Thomas LJ (1983) Mathematical programming approaches to capacity-constrained MRP systems: review, formulation and problem reduction. Manage Sci 29(10):1126–1141. https://doi.org/10.1287/mnsc.29.10.1126

    Article  Google Scholar 

  2. Buschkühl L, Sahling F, Helber S, Tempelmeier H (2010) Dynamic capacitated lot-sizing problems: a classification and review of solution approaches. OR Spectrum 32(2):231–261. https://doi.org/10.1007/s00291-008-0150-7

    Article  Google Scholar 

  3. Briskorn D (2006) A note on capacitated lot sizing with setup carry over. IIE Trans 38(11):1045–1047. https://doi.org/10.1080/07408170500245562

    Article  Google Scholar 

  4. Haase K (1998) Capacitated lot-sizing with linked production quantities of adjacent periods. Beyond Manufacturing Resource Planning (MRP II). Advanced Models and Methods for Production Planning. Springer Berlin Heidelberg., Berlin, Heidelberg, pp 127–146

    Google Scholar 

  5. Chen X, Benjaafar S, Elomri A (2013) The carbon-constrained EOQ. Oper Res Lett 41(2):172–179. https://doi.org/10.1016/j.orl.2012.12.003

    Article  Google Scholar 

  6. Wagner HM, Whitin TM (1958) Dynamic version of the economic lot size model. Manage Sci 5(1):89–96. https://doi.org/10.1287/mnsc.5.1.89

    Article  Google Scholar 

  7. Federgruen A, Tzur M (1991) A simple forward algorithm to solve general dynamic lot sizing models with n periods in 0(n log n) or 0(n) time. Manag Sci 37(8):909–925. https://doi.org/10.2307/2632555   

  8. Florian M, Lenstra JK, Kan AHGR (1980) Deterministic production planning: algorithms and complexity. Manag Sci 26(7):669–679.  https://doi.org/10.1287/mnsc.26.7.669

  9. Bitran GR, Yanasse H (1982) Computational complexity of the capacitated lot size problem. Manag Sci 28(10):1174–1186. https://doi.org/10.1287/mnsc.28.10.1174

  10. Tempelmeier H, Derstroff M (1996) A Lagrangean-based heuristic for dynamic multilevel multiitem constrained lotsizing with setup times. Manage Sci 42(5):738–757

    Article  Google Scholar 

  11. Sox CR, Gao Y (1999) The capacitated lot sizing problem with setup carry-over. IIE Trans 31(2):173–181. https://doi.org/10.1023/a:1007520703382

    Article  Google Scholar 

  12. Tempelmeier H, Buschkühl L (2009) A heuristic for the dynamic multi-level capacitated lotsizing problem with linked lotsizes for general product structures. OR Spectrum 31(2):385–404. https://doi.org/10.1007/s00291-008-0130-y

    Article  Google Scholar 

  13. Sahling F, Buschkühl L, Tempelmeier H, Helber S (2009) Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic. Comput Oper Res 36(9):2546–2553. https://doi.org/10.1016/j.cor.2008.10.009

    Article  Google Scholar 

  14. Wu T, Akartunalı K, Song J, Shi L (2013) Mixed integer programming in production planning with backlogging and setup carryover: modeling and algorithms. Discrete Event Dynamic Systems 23(2):211–239. https://doi.org/10.1007/s10626-012-0141-3

    Article  Google Scholar 

  15. Carvalho DM, Nascimento MCV (2018) A kernel search to the multi-plant capacitated lot sizing problem with setup carry-over. Comput Oper Res 100:43–53. https://doi.org/10.1016/j.cor.2018.07.008

    Article  Google Scholar 

  16. Ghirardi M, Amerio A (2019) Matheuristics for the lot sizing problem with back-ordering, setup carry-overs, and non-identical machines. Comput Ind Eng 127:822–831. https://doi.org/10.1016/j.cie.2018.11.023

    Article  Google Scholar 

  17. Fiorotto DJ, del Carmen J, Neyra H, de Araujo SA (2020) Impact analysis of setup carryover and crossover on lot sizing problems. Int J Prod Res 58(20):6350–6369. https://doi.org/10.1080/00207543.2019.1680892

    Article  Google Scholar 

  18. Benjaafar S, Li Y, Daskin M (2013) Carbon footprint and the management of supply chains: insights from simple models. IEEE Trans Autom Sci Eng 10(1):99–116. https://doi.org/10.1109/TASE.2012.2203304

    Article  Google Scholar 

  19. Retel Helmrich MJ, Jans R, van den Heuvel W, Wagelmans APM (2015) The economic lot-sizing problem with an emission capacity constraint. Eur J Oper Res 241(1):50–62. https://doi.org/10.1016/j.ejor.2014.06.030

    Article  Google Scholar 

  20. Mashud AHM, Roy D, Daryanto Y, Mishra U, Tseng M (2022) Sustainable production lot sizing problem: a sensitivity analysis on controlling carbon emissions through green investment. Comput Ind Eng 169(108143)

  21. Mashud AHM, Roy D, Daryanto Y, Chakrabortty RK, Tseng M (2021) A sustainable inventory model with controllable carbon emissions, deterioration and advance payments. J Clean Prod 296(126608)

  22. Sepehri A (2021) Controllable carbon emissions in an inventory model for perishable items under trade credit policy for credit-risk customers. Carbon Capture Sci Technol 1(100004)

  23. Konur D, Schaefer B (2014) Integrated inventory control and transportation decisions under carbon emissions regulations: LTL vs. TL carriers. Trans Res Part E-Log 68:14–38. https://doi.org/10.1016/j.tre.2014.04.012

  24. Ghosh A (2021) Optimisation of a production-inventory model under two different carbon policies and proposal of a hybrid carbon policy under random demand. Int J Sustain Eng 14(3):280–292

    Article  Google Scholar 

  25. Ahmadini AAH, Modibbo UM, Shaikh AA, Ali I (2021) Multi-objective optimization modelling of sustainable green supply chain in inventory and production management. Alex Eng J 60(6):5129–5146

    Article  Google Scholar 

  26. Manne AS (1958) Programming of economic lot sizes. Manage Sci 4(2):115–135. https://doi.org/10.1287/mnsc.4.2.115

    Article  Google Scholar 

  27. Degraeve Z, Jans R (2007) A new Dantzig-Wolfe reformulation and branch-and-price algorithm for the capacitated lot-sizing problem with setup times. Oper Res 55(5):909–920. https://doi.org/10.1287/opre.1070.0404

    Article  Google Scholar 

  28. Pimentel CMO, Alvelos FPE, de Carvalho Valério JM (2010) Comparing Dantzig-Wolfe decompositions and branch-and-price algorithms for the multi-item capacitated lot sizing problem. Optimization Methods and Software 25(2):299–319. https://doi.org/10.1080/10556780902992837

    Article  Google Scholar 

  29. Caserta M, Voß S (2012) A math-heuristic Dantzig-Wolfe algorithm for the capacitated lot sizing problem. Learning and Intelligent Optimization: 6th International Conference, LION 6, Paris, France, January 16–20, 2012, Revised Selected Papers, 31–41.

  30. Fiorotto DJ, de Araujo SA, Jans R (2015) Hybrid methods for lot sizing on parallel machines. Comput Oper Res 63(Supplement C):136–148. https://doi.org/10.1016/j.cor.2015.04.015

    Article  Google Scholar 

  31. Ioannis F, Degraeve Z, De Reyck B (2016) A horizon decomposition approach for the capacitated lot-sizing problem with setup times. INFORMS J Comput 28(3):465–482. https://doi.org/10.1287/ijoc.2016.0691

    Article  Google Scholar 

  32. Wu T, Shi Z, Liang Z, Zhang X, Zhang C (2020) Dantzig-Wolfe decomposition for the facility location and production planning problem. Comput Oper Res. https://doi.org/10.1016/j.cor.2020.105068

    Article  Google Scholar 

  33. Gören HG, Tunali S (2018) Fix-and-optimize heuristics for capacitated lot sizing with setup carryover and backordering. J Enterp Inf Manag 31(6):879–890. https://doi.org/10.1108/JEIM-01-2017-0017

  34. Vanderbeck F (2000) On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm. Oper Res 48(1):111–128. https://doi.org/10.1287/opre.48.1.111.12453

    Article  Google Scholar 

  35. Vanderbeck F, Savelsbergh MWP (2006) A generic view of Dantzig-Wolfe decomposition in mixed integer programming. Oper Res Lett 34(3):296–306. https://doi.org/10.1016/j.orl.2005.05.009

    Article  Google Scholar 

  36. Ramsay TEJ (1981) Integer programming approaches to capacitated concave cost production planning problem. (Ph.D Dissertation), Georgia Institute of Technology.

  37. Chowdhury NT, Baki F, Azab A (2023) The setup carryover assignment problem. Oper Res Forum 4(25):1–13. https://doi.org/10.1007/s43069-023-00207-6

Download references

Acknowledgements

I would like to express my sincere gratitude to my supervisors, Professor Dr. Fazle Baki and Professor Dr. Ahmed Azab for their valuable guidance and support throughout the research process.

Funding

This research is partially funded by the Natural Sciences and Engineering Research Council’s (NSERC) Discovery Grants (A/C # 811008). This research is also partially funded by the Research and Teaching Innovation Fund (RTIF) and the internal faculty funds.

Author information

Authors and Affiliations

  1. School of Technology, Art and Design, Bemidji State University, Bemidji, MN, 56601, USA

    Nusrat T. Chowdhury

  2. Odette School of Business, University of Windsor, Windsor, ON, N9B 3P4, Canada

    Mohammed F. Baki

  3. Production & Operations Management Research Laboratory, Faculty of Engineering, University of Windsor, Windsor, ON, N9B 3P4, Canada

    Nusrat T. Chowdhury & Ahmed Azab

Authors
  1. Nusrat T. Chowdhury
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohammed F. Baki
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ahmed Azab
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Nusrat T. Chowdhury is the major contributor in writing the manuscript. M.F. Baki and A. Azab did the overall supervision while writing the manuscript. All authors read and approved the final manuscript.

Corresponding author

Correspondence to Nusrat T. Chowdhury.

Ethics declarations

Ethical Approval

All authors certify that for this manuscript the following is fulfilled. This material is the author’s own original work, which has not been previously published elsewhere. The paper is not currently being considered for publication elsewhere. The paper reflects the authors' own research and analysis in a truthful and complete manner. The paper properly credits the meaningful contributions of co-authors and co-researchers.

Competing Interests

The authors declare no competing interests.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chowdhury, N.T., Baki, M.F. & Azab, A. A Modeling and Hybridized Decomposition Approach for the Multi-level Capacitated Lot-Sizing Problem with Setup Carryover, Backlogging, and Emission Control. Oper. Res. Forum 5, 68 (2024). https://doi.org/10.1007/s43069-024-00350-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s43069-024-00350-8

Keywords

Search

Navigation