IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v26y2020i4d10.1007_s10732-020-09443-z.html
   My bibliography  Save this article

Meta-heuristics for the one-dimensional cutting stock problem with usable leftover

Author

Listed:
  • Santiago V. Ravelo

    (Federal University of Rio Grande do Sul)

  • Cláudio N. Meneses

    (Federal University of ABC)

  • Maristela O. Santos

    (University of Sao Paulo)

Abstract

This work considers the one-dimensional cutting stock problem in which the non-used material in the cutting patterns may be used in the future, if large enough. We show that a multiobjective criteria to classify the solutions could be more accurate than previous classifications attempts, also we give a heuristic algorithm and two meta-heuristic approaches to the problem and we use them to solve practical and randomly generated instances from the literature. The results obtained by the computational experiments are quite good for all the tested instances.

Suggested Citation

  • Santiago V. Ravelo & Cláudio N. Meneses & Maristela O. Santos, 2020. "Meta-heuristics for the one-dimensional cutting stock problem with usable leftover," Journal of Heuristics, Springer, vol. 26(4), pages 585-618, August.
    • Handle: RePEc:spr:joheur:v:26:y:2020:i:4:d:10.1007_s10732-020-09443-z
    DOI: 10.1007/s10732-020-09443-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-020-09443-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-020-09443-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. 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.
    2. Cui, Yaodong & Yang, Yuli, 2010. "A heuristic for the one-dimensional cutting stock problem with usable leftover," European Journal of Operational Research, Elsevier, vol. 204(2), pages 245-250, July.
    3. Cherri, Adriana Cristina & Arenales, Marcos Nereu & Yanasse, Horacio Hideki, 2009. "The one-dimensional cutting stock problem with usable leftover - A heuristic approach," European Journal of Operational Research, Elsevier, vol. 196(3), pages 897-908, August.
    4. Alexander Abuabara & Reinaldo Morabito, 2009. "Cutting optimization of structural tubes to build agricultural light aircrafts," Annals of Operations Research, Springer, vol. 169(1), pages 149-165, July.
    5. Ricardo Andrade & Ernesto G Birgin & Reinaldo Morabito & Débora P Ronconi, 2014. "MIP models for two-dimensional non-guillotine cutting problems with usable leftovers," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(11), pages 1649-1663, November.
    6. Gradisar, Miro & Kljajic, Miroljub & Resinovic, Gortan & Jesenko, Joze, 1999. "A sequential heuristic procedure for one-dimensional cutting," European Journal of Operational Research, Elsevier, vol. 114(3), pages 557-568, May.
    7. Cherri, Adriana Cristina & Arenales, Marcos Nereu & Yanasse, Horacio Hideki & Poldi, Kelly Cristina & Gonçalves Vianna, Andréa Carla, 2014. "The one-dimensional cutting stock problem with usable leftovers – A survey," European Journal of Operational Research, Elsevier, vol. 236(2), pages 395-402.
    8. Miro Gradisar & Jure Erjavec & Luka Tomat, 2011. "One-Dimensional Cutting Stock Optimization with Usable Leftover: A Case of Low Stock-to-Order Ratio," International Journal of Decision Support System Technology (IJDSST), IGI Global, vol. 3(1), pages 54-66, January.
    9. 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.
    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. Cherri, Adriana Cristina & Cherri, Luiz Henrique & Oliveira, Beatriz Brito & Oliveira, José Fernando & Carravilla, Maria Antónia, 2023. "A stochastic programming approach to the cutting stock problem with usable leftovers," European Journal of Operational Research, Elsevier, vol. 308(1), pages 38-53.
    2. Jie Fang & Yunqing Rao & Qiang Luo & Jiatai Xu, 2023. "Solving One-Dimensional Cutting Stock Problems with the Deep Reinforcement Learning," Mathematics, MDPI, vol. 11(4), pages 1-16, February.
    3. 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.

    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. Sierra-Paradinas, María & Soto-Sánchez, Óscar & Alonso-Ayuso, Antonio & Martín-Campo, F. Javier & Gallego, Micael, 2021. "An exact model for a slitting problem in the steel industry," European Journal of Operational Research, Elsevier, vol. 295(1), pages 336-347.
    2. Cherri, Adriana Cristina & Arenales, Marcos Nereu & Yanasse, Horacio Hideki & Poldi, Kelly Cristina & Gonçalves Vianna, Andréa Carla, 2014. "The one-dimensional cutting stock problem with usable leftovers – A survey," European Journal of Operational Research, Elsevier, vol. 236(2), pages 395-402.
    3. D. N. Nascimento & S. A. Araujo & A. C. Cherri, 2022. "Integrated lot-sizing and one-dimensional cutting stock problem with usable leftovers," Annals of Operations Research, Springer, vol. 316(2), pages 785-803, September.
    4. Cherri, Adriana Cristina & Cherri, Luiz Henrique & Oliveira, Beatriz Brito & Oliveira, José Fernando & Carravilla, Maria Antónia, 2023. "A stochastic programming approach to the cutting stock problem with usable leftovers," European Journal of Operational Research, Elsevier, vol. 308(1), pages 38-53.
    5. 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.
    6. 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.
    7. Cui, Yaodong & Huang, Baixiong, 2012. "Reducing the number of cuts in generating three-staged cutting patterns," European Journal of Operational Research, Elsevier, vol. 218(2), pages 358-365.
    8. Cui, Yaodong & Yang, Yuli, 2010. "A heuristic for the one-dimensional cutting stock problem with usable leftover," European Journal of Operational Research, Elsevier, vol. 204(2), pages 245-250, July.
    9. Douglas Nogueira Nascimento & Adriana Cristina Cherri & José Fernando Oliveira, 2022. "The two-dimensional cutting stock problem with usable leftovers: mathematical modelling and heuristic approaches," Operational Research, Springer, vol. 22(5), pages 5363-5403, November.
    10. Yaodong Cui & Xiang Song & Yan Chen & Yi-Ping Cui, 2017. "New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(3), pages 269-280, March.
    11. Erjavec, J. & Gradisar, M. & Trkman, P., 2012. "Assessment of stock size to minimize cutting stock production costs," International Journal of Production Economics, Elsevier, vol. 135(1), pages 170-176.
    12. 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.
    13. Lorena Pradenas & Marco Fuentes & Víctor Parada, 2020. "Optimizing waste storage areas in health care centers," Annals of Operations Research, Springer, vol. 295(1), pages 503-516, December.
    14. Alyne Toscano & Socorro Rangel & Horacio Hideki Yanasse, 2017. "A heuristic approach to minimize the number of saw cycles in small-scale furniture factories," Annals of Operations Research, Springer, vol. 258(2), pages 719-746, November.
    15. Gonçalves, José Fernando & Wäscher, Gerhard, 2020. "A MIP model and a biased random-key genetic algorithm based approach for a two-dimensional cutting problem with defects," European Journal of Operational Research, Elsevier, vol. 286(3), pages 867-882.
    16. Keehoon Kwon & Doyeong Kim & Sunkuk Kim, 2021. "Cutting Waste Minimization of Rebar for Sustainable Structural Work: A Systematic Literature Review," Sustainability, MDPI, vol. 13(11), pages 1-21, May.
    17. 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.
    18. Dongho Lee & Seunghyun Son & Doyeong Kim & Sunkuk Kim, 2020. "Special-Length-Priority Algorithm to Minimize Reinforcing Bar-Cutting Waste for Sustainable Construction," Sustainability, MDPI, vol. 12(15), pages 1-15, July.
    19. 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.
    20. Haoqing Wang & Wen Yi, 2022. "Optimization Models for Reducing Off-Cuts of Raw Materials in Construction Site," Mathematics, MDPI, vol. 10(24), pages 1-16, December.

    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:joheur:v:26:y:2020:i:4:d:10.1007_s10732-020-09443-z. 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.