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

Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost

Author

Listed:
  • Silva, Eduardo M.
  • Melega, Gislaine M.
  • Akartunalı, Kerem
  • de Araujo, Silvio A.

Abstract

In this paper, we study the one-dimensional multi-period cutting stock problem with setup costs on cutting patterns. We present pattern-based and pseudo-polynomial formulations for the problem. Reformulations are also proposed to improve the lower bounds. We then present a thorough theoretical analysis to establish the strength of the various proposed formulations in comparison to each other. Finally, a computational analysis is conducted to complement the theoretical analysis and provide further insights with respect to the complexity and strength of the formulations.

Suggested Citation

  • Silva, Eduardo M. & Melega, Gislaine M. & Akartunalı, Kerem & de Araujo, Silvio A., 2023. "Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost," European Journal of Operational Research, Elsevier, vol. 304(2), pages 443-460.
    • Handle: RePEc:eee:ejores:v:304:y:2023:i:2:p:443-460
    DOI: 10.1016/j.ejor.2022.04.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221722003344
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2022.04.023?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. VAN VYVE, Mathieu & WOLSEY, Laurence A & YAMAN, Hande, 2014. "Relaxations for two-level multi-item lot-sizing problems," LIDAM Reprints CORE 2611, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. WOLSEY, Laurence A., 1977. "Valid inequalities, covering problems and discrete dynamic programs," LIDAM Reprints CORE 302, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Martínez, Karim Pérez & Morabito, Reinaldo & Toso, Eli Angela Vitor, 2018. "A coupled process configuration, lot-sizing and scheduling model for production planning in the molded pulp industry," International Journal of Production Economics, Elsevier, vol. 204(C), pages 227-243.
    5. 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.
    6. Johnston, Robert E. & Sadinlija, Enes, 2004. "A new model for complete solutions to one-dimensional cutting stock problems," European Journal of Operational Research, Elsevier, vol. 153(1), pages 176-183, February.
    7. Arbib, Claudio & Marinelli, Fabrizio, 2007. "An optimization model for trim loss minimization in an automotive glass plant," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1421-1432, December.
    8. Cui, Yaodong & Yang, Liu & Zhao, Zhigang & Tang, Tianbing & Yin, Mengxiao, 2013. "Sequential grouping heuristic for the two-dimensional cutting stock problem with pattern reduction," International Journal of Production Economics, Elsevier, vol. 144(2), pages 432-439.
    9. Kelly Cristina Poldi & Silvio Alexandre Araujo, 2016. "Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem," Annals of Operations Research, Springer, vol. 238(1), pages 497-520, March.
    10. 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.
    11. Aktin, Tülin & Özdemir, RIfat Gürcan, 2009. "An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing," European Journal of Operational Research, Elsevier, vol. 196(2), pages 737-743, July.
    12. Wascher, Gerhard & Hau[ss]ner, Heike & Schumann, Holger, 2007. "An improved typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1109-1130, December.
    13. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    14. Nonas, Sigrid Lise & Thorstenson, Anders, 2000. "A combined cutting-stock and lot-sizing problem," European Journal of Operational Research, Elsevier, vol. 120(2), pages 327-342, January.
    15. Jean-François Côté & Manuel Iori, 2018. "The Meet-in-the-Middle Principle for Cutting and Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 646-661, November.
    16. Hatem Ben Amor & José Valério de Carvalho, 2005. "Cutting Stock Problems," Springer Books, in: Guy Desaulniers & Jacques Desrosiers & Marius M. Solomon (ed.), Column Generation, chapter 0, pages 131-161, Springer.
    17. José Roberto Dale Luche & Reinaldo Morabito & Vitória Pureza, 2009. "Combining Process Selection And Lot Sizing Models For Production Scheduling Of Electrofused Grains," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 26(03), pages 421-443.
    18. Angelo Aliano Filho & António Carlos Moretti & Margarida Vaz Pato, 2018. "A comparative study of exact methods for the bi-objective integer one-dimensional cutting stock problem," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 69(1), pages 91-107, January.
    19. Attila, Öykü Naz & Agra, Agostinho & Akartunalı, Kerem & Arulselvan, Ashwin, 2021. "Robust formulations for economic lot-sizing problem with remanufacturing," European Journal of Operational Research, Elsevier, vol. 288(2), pages 496-510.
    20. 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.
    21. Robert W. Haessler, 1988. "Selection and Design of Heuristic Procedures for Solving Roll Trim Problems," Management Science, INFORMS, vol. 34(12), pages 1460-1471, December.
    22. Ming Zhao & Minjiao Zhang, 2020. "Multiechelon Lot Sizing: New Complexities and Inequalities," Operations Research, INFORMS, vol. 68(2), pages 534-551, March.
    23. 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.
    24. 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.
    25. Douglas Alem & Fabricio Oliveira & Miguel Carrión Ruiz Peinado, 2020. "A practical assessment of risk-averse approaches in production lot-sizing problems," International Journal of Production Research, Taylor & Francis Journals, vol. 58(9), pages 2581-2603, May.
    26. Gau, T. & Wascher, G., 1995. "CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem," European Journal of Operational Research, Elsevier, vol. 84(3), pages 572-579, August.
    27. P. C. Gilmore & R. E. Gomory, 1961. "A Linear Programming Approach to the Cutting-Stock Problem," Operations Research, INFORMS, vol. 9(6), pages 849-859, December.
    28. X Song & J A Bennell, 2014. "Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(7), pages 1037-1052, July.
    29. Umetani, Shunji & Yagiura, Mutsunori & Ibaraki, Toshihide, 2003. "One-dimensional cutting stock problem to minimize the number of different patterns," European Journal of Operational Research, Elsevier, vol. 146(2), pages 388-402, April.
    30. Trkman, Peter & Gradisar, Miro, 2007. "One-dimensional cutting stock optimization in consecutive time periods," European Journal of Operational Research, Elsevier, vol. 179(2), pages 291-301, June.
    31. Wuttke, David A. & Heese, H. Sebastian, 2018. "Two-dimensional cutting stock problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 265(1), pages 303-315.
    32. Oliveira, Washington A. & Fiorotto, Diego J. & Song, Xiang & Jones, Dylan F., 2021. "An extended goal programming model for the multiobjective integrated lot-sizing and cutting stock problem," European Journal of Operational Research, Elsevier, vol. 295(3), pages 996-1007.
    33. Maurício Móz Christofoletti & Silvio Alexandre de Araujo & Adriana Cristina Cherri, 2021. "Integrated lot-sizing and cutting stock problem applied to the mattress industry," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 72(6), pages 1279-1293, June.
    34. Arbib, Claudio & Marinelli, Fabrizio, 2005. "Integrating process optimization and inventory planning in cutting-stock with skiving option: An optimization model and its application," European Journal of Operational Research, Elsevier, vol. 163(3), pages 617-630, June.
    35. L. V. Kantorovich, 1960. "Mathematical Methods of Organizing and Planning Production," Management Science, INFORMS, vol. 6(4), pages 366-422, July.
    36. Gothe-Lundgren, Maud & T. Lundgren, Jan & A. Persson, Jan, 2002. "An optimization model for refinery production scheduling," International Journal of Production Economics, Elsevier, vol. 78(3), pages 255-270, August.
    37. P. C. Gilmore & R. E. Gomory, 1963. "A Linear Programming Approach to the Cutting Stock Problem---Part II," Operations Research, INFORMS, vol. 11(6), pages 863-888, December.
    38. Cui, Yaodong & Zhong, Cheng & Yao, Yi, 2015. "Pattern-set generation algorithm for the one-dimensional cutting stock problem with setup cost," European Journal of Operational Research, Elsevier, vol. 243(2), pages 540-546.
    39. 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).
    40. VANDERBECK, François & WOLSEY, Laurence A., 2010. "Reformulation and decomposition of integer programs," LIDAM Reprints CORE 2188, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    41. Diegel, Adolf & Miller, Garth & Montocchio, Edouard & van Schalkwyk, Sias & Diegel, Olaf, 2006. "Enforcing minimum run length in the cutting stock problem," European Journal of Operational Research, Elsevier, vol. 171(2), pages 708-721, June.
    42. François Vanderbeck, 2000. "Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem," Operations Research, INFORMS, vol. 48(6), pages 915-926, December.
    43. 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.
    44. 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.
    45. Reinertsen, Harald & Vossen, Thomas W.M., 2010. "The one-dimensional cutting stock problem with due dates," European Journal of Operational Research, Elsevier, vol. 201(3), pages 701-711, March.
    46. 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.
    47. Luka Tomat & Mirko Gradišar, 2017. "One-dimensional stock cutting: optimization of usable leftovers in consecutive orders," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 25(2), pages 473-489, June.
    48. Kelly Poldi & Silvio Araujo, 2016. "Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem," Annals of Operations Research, Springer, vol. 238(1), pages 497-520, March.
    Full references (including those not matched with items on IDEAS)

    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. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    2. 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.
    3. Mateus Martin & Horacio Hideki Yanasse & Luiz Leduíno Salles-Neto, 2022. "Pattern-based ILP models for the one-dimensional cutting stock problem with setup cost," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 557-582, August.
    4. Gislaine Mara Melega & Silvio Alexandre de Araujo & Reinaldo Morabito, 2020. "Mathematical model and solution approaches for integrated lot-sizing, scheduling and cutting stock problems," Annals of Operations Research, Springer, vol. 295(2), pages 695-736, December.
    5. B. S. C. Campello & C. T. L. S. Ghidini & A. O. C. Ayres & W. A. Oliveira, 2022. "A residual recombination heuristic for one-dimensional cutting stock problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 194-220, April.
    6. Anselmo Ramalho Pitombeira-Neto & Bruno de Athayde Prata, 2020. "A matheuristic algorithm for the one-dimensional cutting stock and scheduling problem with heterogeneous orders," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 28(1), pages 178-192, April.
    7. Kallrath, Julia & Rebennack, Steffen & Kallrath, Josef & Kusche, Rüdiger, 2014. "Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges," European Journal of Operational Research, Elsevier, vol. 238(1), pages 374-389.
    8. Wang, Danni & Xiao, Fan & Zhou, Lei & Liang, Zhe, 2020. "Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation," European Journal of Operational Research, Elsevier, vol. 286(2), pages 547-563.
    9. Hadj Salem, Khadija & Silva, Elsa & Oliveira, José Fernando & Carravilla, Maria Antónia, 2023. "Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry," European Journal of Operational Research, Elsevier, vol. 306(2), pages 549-566.
    10. 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.
    11. Kelly Poldi & Silvio Araujo, 2016. "Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem," Annals of Operations Research, Springer, vol. 238(1), pages 497-520, March.
    12. Kelly Cristina Poldi & Silvio Alexandre Araujo, 2016. "Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem," Annals of Operations Research, Springer, vol. 238(1), pages 497-520, March.
    13. Pedro Rochavetz Lara Andrade & Silvio Alexandre Araujo & Adriana Cristina Cherri & Felipe Kesrouani Lemos, 2023. "The cutting stock problem applied to the hardening process in an automotive spring factory," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 31(2), pages 637-664, June.
    14. Tao Wu, 2022. "Predictive Search for Capacitated Multi-Item Lot Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 385-406, January.
    15. Amanda O. C. Ayres & Betania S. C. Campello & Washington A. Oliveira & Carla T. L. S. Ghidini, 2021. "A Bi-Integrated Model for coupling lot-sizing and cutting-stock problems," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(4), pages 1047-1076, December.
    16. Wuttke, David A. & Heese, H. Sebastian, 2018. "Two-dimensional cutting stock problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 265(1), pages 303-315.
    17. 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.
    18. Aktin, Tülin & Özdemir, RIfat Gürcan, 2009. "An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing," European Journal of Operational Research, Elsevier, vol. 196(2), pages 737-743, July.
    19. Delorme, Maxence & Iori, Manuel & Martello, Silvano, 2016. "Bin packing and cutting stock problems: Mathematical models and exact algorithms," European Journal of Operational Research, Elsevier, vol. 255(1), pages 1-20.
    20. Attila, Öykü Naz & Agra, Agostinho & Akartunalı, Kerem & Arulselvan, Ashwin, 2021. "Robust formulations for economic lot-sizing problem with remanufacturing," European Journal of Operational Research, Elsevier, vol. 288(2), pages 496-510.

    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:304:y:2023:i:2:p:443-460. 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.