IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v52y2015icp15-32.html
   My bibliography  Save this article

Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts

Author

Listed:
  • Martinez-Sykora, Antonio
  • Alvarez-Valdes, Ramon
  • Bennell, Julia
  • Tamarit, Jose Manuel

Abstract

This paper presents an approach for solving a new real problem in cutting and packing. At its core is an innovative mixed integer programme model that places irregular pieces and defines guillotine cuts. The two-dimensional irregular shape bin packing problem with guillotine constraints arises in the glass cutting industry, for example, the cutting of glass for conservatories. Almost all cutting and packing problems that include guillotine cuts deal with rectangles only, where all cuts are orthogonal to the edges of the stock sheet and a maximum of two angles of rotation are permitted. The literature tackling packing problems with irregular shapes largely focuses on strip packing i.e. minimizing the length of a single fixed width stock sheet, and does not consider guillotine cuts. Hence, this problem combines the challenges of tackling the complexity of packing irregular pieces with free rotation, guaranteeing guillotine cuts that are not always orthogonal to the edges of the stock sheet, and allocating pieces to bins. To our knowledge only one other recent paper tackles this problem. We present a hybrid algorithm that is a constructive heuristic that determines the relative position of pieces in the bin and guillotine constraints via a mixed integer programme model. We investigate two approaches for allocating guillotine cuts at the same time as determining the placement of the piece, and a two phase approach that delays the allocation of cuts to provide flexibility in space usage. Finally we describe an improvement procedure that is applied to each bin before it is closed. This approach improves on the results of the only other publication on this problem, and gives competitive results for the classic rectangle bin packing problem with guillotine constraints.

Suggested Citation

  • Martinez-Sykora, Antonio & Alvarez-Valdes, Ramon & Bennell, Julia & Tamarit, Jose Manuel, 2015. "Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts," Omega, Elsevier, vol. 52(C), pages 15-32.
    • Handle: RePEc:eee:jomega:v:52:y:2015:i:c:p:15-32
    DOI: 10.1016/j.omega.2014.10.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048314001285
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2014.10.007?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. Andrea Lodi & Silvano Martello & Daniele Vigo, 1999. "Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems," INFORMS Journal on Computing, INFORMS, vol. 11(4), pages 345-357, November.
    3. Polyakovsky, Sergey & M'Hallah, Rym, 2009. "An agent-based approach to the two-dimensional guillotine bin packing problem," European Journal of Operational Research, Elsevier, vol. 192(3), pages 767-781, February.
    4. Malaguti, Enrico & Medina Durán, Rosa & Toth, Paolo, 2014. "Approaches to real world two-dimensional cutting problems," Omega, Elsevier, vol. 47(C), pages 99-115.
    5. Dyckhoff, Harald, 1990. "A typology of cutting and packing problems," European Journal of Operational Research, Elsevier, vol. 44(2), pages 145-159, January.
    6. Alvarez-Valdes, R. & Martinez, A. & Tamarit, J.M., 2013. "A branch & bound algorithm for cutting and packing irregularly shaped pieces," International Journal of Production Economics, Elsevier, vol. 145(2), pages 463-477.
    7. Dyckhoff, H & Kruse, H-J & Abel, D & Gal, T, 1985. "Trim loss and related problems," Omega, Elsevier, vol. 13(1), pages 59-72.
    8. E. K. Burke & R. S. R. Hellier & G. Kendall & G. Whitwell, 2010. "Irregular Packing Using the Line and Arc No-Fit Polygon," Operations Research, INFORMS, vol. 58(4-part-1), pages 948-970, August.
    9. Bennell, Julia A. & Oliveira, Jose F., 2008. "The geometry of nesting problems: A tutorial," European Journal of Operational Research, Elsevier, vol. 184(2), pages 397-415, January.
    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. Martinez-Sykora, A. & Alvarez-Valdes, R. & Bennell, J.A. & Ruiz, R. & Tamarit, J.M., 2017. "Matheuristics for the irregular bin packing problem with free rotations," European Journal of Operational Research, Elsevier, vol. 258(2), pages 440-455.
    2. Bennell, J.A. & Cabo, M. & Martínez-Sykora, A., 2018. "A beam search approach to solve the convex irregular bin packing problem with guillotine guts," European Journal of Operational Research, Elsevier, vol. 270(1), pages 89-102.
    3. Hu, Qian & Wei, Lijun & Lim, Andrew, 2018. "The two-dimensional vector packing problem with general costs," Omega, Elsevier, vol. 74(C), pages 59-69.
    4. Cherri, Luiz Henrique & Carravilla, Maria Antónia & Ribeiro, Cristina & Toledo, Franklina Maria Bragion, 2019. "Optimality in nesting problems: New constraint programming models and a new global constraint for non-overlap," Operations Research Perspectives, Elsevier, vol. 6(C).
    5. Gajda, Mikele & Trivella, Alessio & Mansini, Renata & Pisinger, David, 2022. "An optimization approach for a complex real-life container loading problem," Omega, Elsevier, vol. 107(C).
    6. Irawan, Chandra Ade & Song, Xiang & Jones, Dylan & Akbari, Negar, 2017. "Layout optimisation for an installation port of an offshore wind farm," European Journal of Operational Research, Elsevier, vol. 259(1), pages 67-83.

    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. Leao, Aline A.S. & Toledo, Franklina M.B. & Oliveira, José Fernando & Carravilla, Maria Antónia & Alvarez-Valdés, Ramón, 2020. "Irregular packing problems: A review of mathematical models," European Journal of Operational Research, Elsevier, vol. 282(3), pages 803-822.
    2. Lastra-Díaz, Juan J. & Ortuño, M. Teresa, 2024. "Mixed-integer programming models for irregular strip packing based on vertical slices and feasibility cuts," European Journal of Operational Research, Elsevier, vol. 313(1), pages 69-91.
    3. Iori, Manuel & de Lima, Vinícius L. & Martello, Silvano & Miyazawa, Flávio K. & Monaci, Michele, 2021. "Exact solution techniques for two-dimensional cutting and packing," European Journal of Operational Research, Elsevier, vol. 289(2), pages 399-415.
    4. Gardeyn, Jeroen & Wauters, Tony, 2022. "A goal-driven ruin and recreate heuristic for the 2D variable-sized bin packing problem with guillotine constraints," European Journal of Operational Research, Elsevier, vol. 301(2), pages 432-444.
    5. Umetani, Shunji & Murakami, Shohei, 2022. "Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1009-1026.
    6. Cherri, Luiz Henrique & Carravilla, Maria Antónia & Ribeiro, Cristina & Toledo, Franklina Maria Bragion, 2019. "Optimality in nesting problems: New constraint programming models and a new global constraint for non-overlap," Operations Research Perspectives, Elsevier, vol. 6(C).
    7. Han, Wei & Bennell, Julia A. & Zhao, Xiaozhou & Song, Xiang, 2013. "Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints," European Journal of Operational Research, Elsevier, vol. 230(3), pages 495-504.
    8. Akang Wang & Christopher L. Hanselman & Chrysanthos E. Gounaris, 2018. "A customized branch-and-bound approach for irregular shape nesting," Journal of Global Optimization, Springer, vol. 71(4), pages 935-955, August.
    9. 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.
    10. J A Bennell & J F Oliveira, 2009. "A tutorial in irregular shape packing problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 93-105, May.
    11. Hu, Qian & Lim, Andrew & Zhu, Wenbin, 2015. "The two-dimensional vector packing problem with piecewise linear cost function," Omega, Elsevier, vol. 50(C), pages 43-53.
    12. Cherri, Luiz H. & Mundim, Leandro R. & Andretta, Marina & Toledo, Franklina M.B. & Oliveira, José F. & Carravilla, Maria Antónia, 2016. "Robust mixed-integer linear programming models for the irregular strip packing problem," European Journal of Operational Research, Elsevier, vol. 253(3), pages 570-583.
    13. Önder Aşık & Ender Özcan, 2009. "Bidirectional best-fit heuristic for orthogonal rectangular strip packing," Annals of Operations Research, Springer, vol. 172(1), pages 405-427, November.
    14. Chehrazad, Sahar & Roose, Dirk & Wauters, Tony, 2022. "A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation," European Journal of Operational Research, Elsevier, vol. 300(3), pages 809-826.
    15. Kimms, Alf & Király, Hédi, 2023. "An extended model formulation for the two-dimensional irregular strip packing problem considering general industry-relevant aspects," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1202-1218.
    16. Rapine, Christophe & Pedroso, Joao Pedro & Akbalik, Ayse, 2022. "The two-dimensional knapsack problem with splittable items in stacks," Omega, Elsevier, vol. 112(C).
    17. Yainier Labrada-Nueva & Martin H. Cruz-Rosales & Juan Manuel Rendón-Mancha & Rafael Rivera-López & Marta Lilia Eraña-Díaz & Marco Antonio Cruz-Chávez, 2021. "Overlap Detection in 2D Amorphous Shapes for Paper Optimization in Digital Printing Presses," Mathematics, MDPI, vol. 9(9), pages 1-22, May.
    18. 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.
    19. Nikolaus Furian & Siegfried Vössner, 2013. "Constrained order packing: comparison of heuristic approaches for a new bin packing problem," 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. 21(1), pages 237-264, January.
    20. Bennell, J.A. & Cabo, M. & Martínez-Sykora, A., 2018. "A beam search approach to solve the convex irregular bin packing problem with guillotine guts," European Journal of Operational Research, Elsevier, vol. 270(1), pages 89-102.

    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:jomega:v:52:y:2015:i:c:p:15-32. 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/wps/find/journaldescription.cws_home/375/description#description .

    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.