A skyline heuristic for the 2D rectangular packing and strip packing problems

A skyline heuristic for the 2D rectangular packing and strip packing problems

0.00 Avg rating0 Votes
Article ID: iaor20118273
Volume: 215
Issue: 2
Start Page Number: 337
End Page Number: 346
Publication Date: Dec 2011
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: heuristics
Abstract:

In this paper, we propose a greedy heuristic for the 2D rectangular packing problem (2DRP) that represents packings using a skyline; the use of this heuristic in a simple tabu search approach outperforms the best existing approach for the 2DRP on benchmark test cases. We then make use of this 2DRP approach as a subroutine in an ‘iterative doubling’ binary search on the height of the packing to solve the 2D rectangular strip packing problem (2DSP). This approach outperforms all existing approaches on standard benchmark test cases for the 2DSP.

Reviews

Required fields are marked *. Your email address will not be published.