One-Dimensional Heuristics Adapted for Two-Dimensional Rectangular Strip Packing
Authors: G. Belov, G. Scheithauer, E.A. Mukhacheva.
Technische Universitaet Dresden, Preprint MATH-NM-02-2006
Appeared in: Journal of Operat. Res. Soc. (2007) 1-10

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, i.e., 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 \emph{BubbleSearch}. It generates different item sequences and runs a new sequence-based heuristic \emph{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).
PPreprint version: PDF,