One-Dimensional Heuristics Adapted for Two-Dimensional Rectangular Strip Packing

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

  • G. Belov - , TUD Dresden University of Technology (Author)
  • G. Scheithauer - , Chair of Numerical Optimization (Author)
  • E. A. Mukhacheva - , Ufa State Aviation Technical University (Author)

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

Details

Original languageEnglish
Pages (from-to)823-832
JournalJournal of the Operational Research Society : OR
Volume59
Issue number6
Publication statusPublished - 2008
Peer-reviewedYes

External IDs

Scopus 43149109952

Keywords

DFG Classification of Subject Areas according to Review Boards

Keywords

  • Rectangular Strip Packing, Heuristic