A survey and comparison of heuristics for the 2D oriented on-line strip packing problem
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 ar...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Operations Research Society of South Africa (ORSSA)
2008-12-01
|
| Series: | ORiON |
| Online Access: | http://orion.journals.ac.za/pub/article/view/65 |
| _version_ | 1818081634484748288 |
|---|---|
| author | N Ntene JH van Vuuren |
| author_facet | N Ntene JH van Vuuren |
| author_sort | N Ntene |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-10T19:09:19Z |
| format | Article |
| id | doaj.art-c14f9e8d7ef0471892c657e477de39d8 |
| institution | Directory Open Access Journal |
| issn | 2224-0004 |
| language | English |
| last_indexed | 2024-12-10T19:09:19Z |
| publishDate | 2008-12-01 |
| publisher | Operations Research Society of South Africa (ORSSA) |
| record_format | Article |
| series | ORiON |
| spelling | doaj.art-c14f9e8d7ef0471892c657e477de39d82022-12-22T01:36:49ZengOperations Research Society of South Africa (ORSSA)ORiON2224-00042008-12-0124210.5784/24-2-6565A survey and comparison of heuristics for the 2D oriented on-line strip packing problemN NteneJH van VuurenThe 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.http://orion.journals.ac.za/pub/article/view/65 |
| spellingShingle | N Ntene JH van Vuuren A survey and comparison of heuristics for the 2D oriented on-line strip packing problem ORiON |
| title | A survey and comparison of heuristics for the 2D oriented on-line strip packing problem |
| title_full | A survey and comparison of heuristics for the 2D oriented on-line strip packing problem |
| title_fullStr | A survey and comparison of heuristics for the 2D oriented on-line strip packing problem |
| title_full_unstemmed | A survey and comparison of heuristics for the 2D oriented on-line strip packing problem |
| title_short | A survey and comparison of heuristics for the 2D oriented on-line strip packing problem |
| title_sort | survey and comparison of heuristics for the 2d oriented on line strip packing problem |
| url | http://orion.journals.ac.za/pub/article/view/65 |
| work_keys_str_mv | AT nntene asurveyandcomparisonofheuristicsforthe2dorientedonlinestrippackingproblem AT jhvanvuuren asurveyandcomparisonofheuristicsforthe2dorientedonlinestrippackingproblem AT nntene surveyandcomparisonofheuristicsforthe2dorientedonlinestrippackingproblem AT jhvanvuuren surveyandcomparisonofheuristicsforthe2dorientedonlinestrippackingproblem |