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

Number of bins and maximum lateness minimization in two-dimensional bin packing

Author

Listed:
  • Arbib, Claudio
  • Marinelli, Fabrizio
  • Pizzuti, Andrea

Abstract

In this work we address an orthogonal non-oriented two-dimensional bin packing problem where items are associated with due-dates. Two objectives are considered: minimize (i) the number of bins and (ii) the maximum lateness of the items. We discuss basic properties of non-dominated solutions and propose a sequential value correction heuristic that outperforms two benchmark algorithms specifically designed for this problem. We also extend the benchmark dataset for this problem with new and larger industrial instances obtained from a major manufacturer of cutting machines. Finally, we give some insights into the structure of Pareto-optimal sets in the classes of instances here considered.

Suggested Citation

  • Arbib, Claudio & Marinelli, Fabrizio & Pizzuti, Andrea, 2021. "Number of bins and maximum lateness minimization in two-dimensional bin packing," European Journal of Operational Research, Elsevier, vol. 291(1), pages 101-113.
    • Handle: RePEc:eee:ejores:v:291:y:2021:i:1:p:101-113
    DOI: 10.1016/j.ejor.2020.09.023
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720308274
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.09.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. 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. G Belov & G Scheithauer & E A Mukhacheva, 2008. "One-dimensional heuristics adapted for two-dimensional rectangular strip packing," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 823-832, June.
    3. 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.
    4. Gleb Belov & Guntram Scheithauer, 2007. "Setup and Open-Stacks Minimization in One-Dimensional Stock Cutting," INFORMS Journal on Computing, INFORMS, vol. 19(1), pages 27-35, February.
    5. S. Ruzika & M. M. Wiecek, 2005. "Approximation Methods in Multiobjective Programming," Journal of Optimization Theory and Applications, Springer, vol. 126(3), pages 473-501, September.
    6. Cui, Yi-Ping & Cui, Yaodong & Tang, Tianbing, 2015. "Sequential heuristic for the two-dimensional bin-packing problem," European Journal of Operational Research, Elsevier, vol. 240(1), pages 43-53.
    7. Polyakovskiy, Sergey & M’Hallah, Rym, 2018. "A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates," European Journal of Operational Research, Elsevier, vol. 266(3), pages 819-839.
    8. Bennell, Julia A. & Soon Lee, Lai & Potts, Chris N., 2013. "A genetic algorithm for two-dimensional bin packing with due dates," International Journal of Production Economics, Elsevier, vol. 145(2), pages 547-560.
    9. 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.
    10. Andrea Lodi & Silvano Martello & Michele Monaci & Claudio Cicconetti & Luciano Lenzini & Enzo Mingozzi & Carl Eklund & Jani Moilanen, 2011. "Efficient Two-Dimensional Packing Algorithms for Mobile WiMAX," Management Science, INFORMS, vol. 57(12), pages 2130-2144, December.
    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. Arbib, Claudio & Marinelli, Fabrizio & Pezzella, Ferdinando, 2012. "An LP-based tabu search for batch scheduling in a cutting process with finite buffers," International Journal of Production Economics, Elsevier, vol. 136(2), pages 287-296.
    3. Yi-Ping Cui & Yongwu Zhou & Yaodong Cui, 2017. "Triple-solution approach for the strip packing problem with two-staged patterns," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 588-604, August.
    4. Polyakovskiy, Sergey & M’Hallah, Rym, 2021. "Just-in-time two-dimensional bin packing," Omega, Elsevier, vol. 102(C).
    5. Leung, Stephen C.H. & Zhang, Defu & Sim, Kwang Mong, 2011. "A two-stage intelligent search algorithm for the two-dimensional strip packing problem," European Journal of Operational Research, Elsevier, vol. 215(1), pages 57-69, November.
    6. Andreas Bortfeldt & Sabine Jungmann, 2012. "A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint," Annals of Operations Research, Springer, vol. 196(1), pages 53-71, July.
    7. Parreño, F. & Alvarez-Valdes, R., 2021. "Mathematical models for a cutting problem in the glass manufacturing industry," Omega, Elsevier, vol. 103(C).
    8. Polyakovskiy, Sergey & M’Hallah, Rym, 2018. "A hybrid feasibility constraints-guided search to the two-dimensional bin packing problem with due dates," European Journal of Operational Research, Elsevier, vol. 266(3), pages 819-839.
    9. 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.
    10. Bortfeldt, Andreas, 2013. "A reduction approach for solving the rectangle packing area minimization problem," European Journal of Operational Research, Elsevier, vol. 224(3), pages 486-496.
    11. 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.
    12. Nestor M Cid-Garcia & Yasmin A Rios-Solis, 2020. "Positions and covering: A two-stage methodology to obtain optimal solutions for the 2d-bin packing problem," PLOS ONE, Public Library of Science, vol. 15(4), pages 1-22, April.
    13. Bennell, Julia A. & Soon Lee, Lai & Potts, Chris N., 2013. "A genetic algorithm for two-dimensional bin packing with due dates," International Journal of Production Economics, Elsevier, vol. 145(2), pages 547-560.
    14. Ortmann, Frank G. & Ntene, Nthabiseng & van Vuuren, Jan H., 2010. "New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems," European Journal of Operational Research, Elsevier, vol. 203(2), pages 306-315, June.
    15. Arbib, Claudio & Felici, Giovanni & Servilio, Mara, 2019. "Common operation scheduling with general processing times: A branch-and-cut algorithm to minimize the weighted number of tardy jobs," Omega, Elsevier, vol. 84(C), pages 18-30.
    16. Cui, Yi-Ping & Cui, Yaodong & Tang, Tianbing, 2015. "Sequential heuristic for the two-dimensional bin-packing problem," European Journal of Operational Research, Elsevier, vol. 240(1), pages 43-53.
    17. Polyakovskiy, Sergey & M’Hallah, Rym, 2022. "A lookahead matheuristic for the unweighed variable-sized two-dimensional bin packing problem," European Journal of Operational Research, Elsevier, vol. 299(1), pages 104-117.
    18. Li, Xueping & Zhang, Kaike, 2018. "Single batch processing machine scheduling with two-dimensional bin packing constraints," International Journal of Production Economics, Elsevier, vol. 196(C), pages 113-121.
    19. Arbib, Claudio & Marinelli, Fabrizio, 2017. "Maximum lateness minimization in one-dimensional bin packing," Omega, Elsevier, vol. 68(C), pages 76-84.
    20. Francisco Trespalacios & Ignacio E. Grossmann, 2017. "Symmetry breaking for generalized disjunctive programming formulation of the strip packing problem," Annals of Operations Research, Springer, vol. 258(2), pages 747-759, November.

    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:291:y:2021:i:1:p:101-113. 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.