A survey and comparison of heuristics for the 2D oriented on-line strip packing problem

N Ntene, JH van Vuuren


The two dimensional oriented on-line strip packing problem requires items to be packed, one at a time, into a strip of fixed width and infinite height so as to minimise the total height of the packing. The items may neither be rotated nor overlap. In this paper, ten heuristics from the literature are considered for the special case where the items are rectangles. Six modifications to some of these heuristics are proposed, along with two entirely new shelf algorithms. The performances and efficiencies of all the algorithms are compared in terms of the total packing height achieved and computation time required in each case, when applied to 542 benchmark data sets documented in the literature.

Full Text:


DOI: https://doi.org/10.5784/24-2-65


  • There are currently no refbacks.

ISSN 2224-0004 (online); ISSN 0259-191X (print)

Powered by OJS and hosted by Stellenbosch University Library and Information Service since 2011.


This journal is hosted by the SU LIS on request of the journal owner/editor. The SU LIS takes no responsibility for the content published within this journal, and disclaim all liability arising out of the use of or inability to use the information contained herein. We assume no responsibility, and shall not be liable for any breaches of agreement with other publishers/hosts.

SUNJournals Help