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

G. Belov, G. Scheithauer, E. A. Mukhacheva

Research output: Contribution to journalArticleResearchpeer-review

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).

Original languageEnglish
Pages (from-to)823-832
Number of pages10
JournalJournal of the Operational Research Society
Volume59
Issue number6
DOIs
Publication statusPublished - 1 Jun 2008

Keywords

  • Greedy
  • Heuristics
  • Knapsack
  • Stochastic search
  • Strip packing

Cite this

@article{d10cec6c89814082a164bbcb12b81861,
title = "One-dimensional heuristics adapted for two-dimensional rectangular strip packing",
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).",
keywords = "Greedy, Heuristics, Knapsack, Stochastic search, Strip packing",
author = "G. Belov and G. Scheithauer and Mukhacheva, {E. A.}",
year = "2008",
month = "6",
day = "1",
doi = "10.1057/palgrave.jors.2602393",
language = "English",
volume = "59",
pages = "823--832",
journal = "Journal of the Operational Research Society",
issn = "0160-5682",
publisher = "Palgrave Macmillan",
number = "6",

}

One-dimensional heuristics adapted for two-dimensional rectangular strip packing. / Belov, G.; Scheithauer, G.; Mukhacheva, E. A.

In: Journal of the Operational Research Society, Vol. 59, No. 6, 01.06.2008, p. 823-832.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Belov, G.

AU - Scheithauer, G.

AU - Mukhacheva, E. A.

PY - 2008/6/1

Y1 - 2008/6/1

N2 - 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).

AB - 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).

KW - Greedy

KW - Heuristics

KW - Knapsack

KW - Stochastic search

KW - Strip packing

UR - http://www.scopus.com/inward/record.url?scp=43149109952&partnerID=8YFLogxK

U2 - 10.1057/palgrave.jors.2602393

DO - 10.1057/palgrave.jors.2602393

M3 - Article

VL - 59

SP - 823

EP - 832

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

SN - 0160-5682

IS - 6

ER -