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

G Belov (), G Scheithauer () and E A Mukhacheva
Additional contact information
G Belov: Technische Universität Dresden
G Scheithauer: Technische Universität Dresden
E A Mukhacheva: Ufa State Aviation Technical University

Journal of the Operational Research Society, 2008, vol. 59, issue 6, 823-832

Abstract: 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: strip packing; heuristics; greedy; stochastic search; knapsack (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2602393 Abstract (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:59:y:2008:i:6:d:10.1057_palgrave.jors.2602393

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2602393

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().