IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v59y2008i6d10.1057_palgrave.jors.2602393.html
   My bibliography  Save this article

One-dimensional heuristics adapted for two-dimensional rectangular strip packing

Author

Listed:
  • G Belov

    (Technische Universität Dresden)

  • G Scheithauer

    (Technische Universität Dresden)

  • E A Mukhacheva

    (Ufa State Aviation Technical University)

Abstract

We consider two-dimensional rectangular strip packing without rotation of items and without the guillotine cutting constraint. We propose two iterative heuristics. The first one, SVC(SubKP), is based on a single-pass heuristic SubKP which fills every most bottom-left free space in a one-dimensional knapsack fashion, that is, considering only item widths. It appears especially important to assign suitable ‘pseudo-profits’ in this knapsack problem. The second heuristic BS(BLR) is based on the known randomized framework Bubble-Search. It generates different item sequences and runs a new sequence-based heuristic Bottom-Left-Right (BLR), a simple modification of the Bottom-Left heuristic. We investigate the solution sets of SubKP and BLR and their relation to each other. In the tests, SVC(SubKP) improves the results for larger instances of the waste-free classes of Hopper and Turton and, on average, for the tested non-waste-free classes, compared to the latest literature. BS(BLR) gives the best results in some classes with smaller number of items (20,40).

Suggested Citation

  • 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.
    • Handle: RePEc:pal:jorsoc:v:59:y:2008:i:6:d:10.1057_palgrave.jors.2602393
    DOI: 10.1057/palgrave.jors.2602393
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2602393
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2602393?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. Silvano Martello & Daniele Vigo, 1998. "Exact Solution of the Two-Dimensional Finite Bin Packing Problem," Management Science, INFORMS, vol. 44(3), pages 388-399, March.
    2. Sándor P. Fekete & Jörg Schepers, 2004. "A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing," Mathematics of Operations Research, INFORMS, vol. 29(2), pages 353-368, May.
    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. Bortfeldt, Andreas, 2006. "A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces," European Journal of Operational Research, Elsevier, vol. 172(3), pages 814-837, August.
    6. Silvano Martello & David Pisinger & Paolo Toth, 1999. "Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem," Management Science, INFORMS, vol. 45(3), pages 414-424, March.
    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Wei, Lijun & Oon, Wee-Chong & Zhu, Wenbin & Lim, Andrew, 2011. "A skyline heuristic for the 2D rectangular packing and strip packing problems," European Journal of Operational Research, Elsevier, vol. 215(2), pages 337-346, December.
    8. Thiago Queiroz & Flávio Miyazawa, 2014. "Order and static stability into the strip packing problem," Annals of Operations Research, Springer, vol. 223(1), pages 137-154, December.
    9. 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.
    10. Defu Zhang & Yuxin Che & Furong Ye & Yain-Whar Si & Stephen C. H. Leung, 2016. "A hybrid algorithm based on variable neighbourhood for the strip packing problem," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 513-530, August.
    11. Selma Khebbache-Hadji & Christian Prins & Alice Yalaoui & Mohamed Reghioui, 2013. "Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows," 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(2), pages 307-336, March.
    12. Rosephine G. Rakotonirainy & Jan H. Vuuren, 2021. "The effect of benchmark data characteristics during empirical strip packing heuristic performance evaluation," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(2), pages 467-495, June.
    13. Stéphane Grandcolas & Cyril Pain-Barre, 2022. "A hybrid metaheuristic for the two-dimensional strip packing problem," Annals of Operations Research, Springer, vol. 309(1), pages 79-102, February.
    14. 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.

    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. Wei, Lijun & Tian, Tian & Zhu, Wenbin & Lim, Andrew, 2014. "A block-based layer building approach for the 2D guillotine strip packing problem," European Journal of Operational Research, Elsevier, vol. 239(1), pages 58-69.
    2. Lei Wang & Aihua Yin, 2016. "A quasi-human algorithm for the two dimensional rectangular strip packing problem: in memory of Prof. Wenqi Huang," Journal of Combinatorial Optimization, Springer, vol. 32(2), pages 416-444, August.
    3. Hadjiconstantinou, Eleni & Iori, Manuel, 2007. "A hybrid genetic algorithm for the two-dimensional single large object placement problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1150-1166, December.
    4. 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.
    5. Clautiaux, Francois & Carlier, Jacques & Moukrim, Aziz, 2007. "A new exact method for the two-dimensional orthogonal packing problem," European Journal of Operational Research, Elsevier, vol. 183(3), pages 1196-1211, December.
    6. Marco Antonio Boschetti & Lorenza Montaletti, 2010. "An Exact Algorithm for the Two-Dimensional Strip-Packing Problem," Operations Research, INFORMS, vol. 58(6), pages 1774-1791, December.
    7. 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.
    8. Felix Prause & Kai Hoppmann-Baum & Boris Defourny & Thorsten Koch, 2021. "The maximum diversity assortment selection problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 93(3), pages 521-554, June.
    9. Selma Khebbache-Hadji & Christian Prins & Alice Yalaoui & Mohamed Reghioui, 2013. "Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows," 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(2), pages 307-336, March.
    10. 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.
    11. Hong, Shaohui & Zhang, Defu & Lau, Hoong Chuin & Zeng, XiangXiang & Si, Yain-Whar, 2014. "A hybrid heuristic algorithm for the 2D variable-sized bin packing problem," European Journal of Operational Research, Elsevier, vol. 238(1), pages 95-103.
    12. Rosephine G. Rakotonirainy & Jan H. Vuuren, 2021. "The effect of benchmark data characteristics during empirical strip packing heuristic performance evaluation," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(2), pages 467-495, June.
    13. Zhu, Wenbin & Zhang, Zhaoyi & Oon, Wee-Chong & Lim, Andrew, 2012. "Space defragmentation for packing problems," European Journal of Operational Research, Elsevier, vol. 222(3), pages 452-463.
    14. Schmid, Verena & Doerner, Karl F. & Laporte, Gilbert, 2013. "Rich routing problems arising in supply chain management," European Journal of Operational Research, Elsevier, vol. 224(3), pages 435-448.
    15. Gregory S. Taylor & Yupo Chan & Ghulam Rasool, 2017. "A three-dimensional bin-packing model: exact multicriteria solution and computational complexity," Annals of Operations Research, Springer, vol. 251(1), pages 397-427, April.
    16. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    17. M. Muntazir Mehdi & Le Wang & Sean P. Willems, 2022. "Developing a Maximum Inscribed Rectangle Heuristic to Satisfy Rush Orders for Heavy Plate Steel," Interfaces, INFORMS, vol. 52(3), pages 283-294, May.
    18. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Christos T., 2009. "A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 195(3), pages 729-743, June.
    19. Lodi, Andrea & Martello, Silvano & Monaci, Michele, 2002. "Two-dimensional packing problems: A survey," European Journal of Operational Research, Elsevier, vol. 141(2), pages 241-252, September.
    20. 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.

    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:pal:jorsoc:v:59:y:2008:i:6:d:10.1057_palgrave.jors.2602393. 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.palgrave-journals.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.