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

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