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).
Acknowledgements
We are grateful to the two anonymous referees for valuable suggestions concerning presentation quality. We also thank François Clautiaux and Antoine Jouglet for running the two-step method on the waste-free instances of Hopper and Turton.