Improved local search algorithms for the rectangle packing problem with general spatial costs

Improved local search algorithms for the rectangle packing problem with general spatial costs

0.00 Avg rating0 Votes
Article ID: iaor20062843
Country: Netherlands
Volume: 167
Issue: 1
Start Page Number: 48
End Page Number: 67
Publication Date: Nov 2005
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics, programming: dynamic
Abstract:

The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form. For this problem, we have previously presented local search algorithms using a pair of permutations of rectangles to represent a solution. In this paper, we propose speed-up techniques to evaluate solutions in various neighborhoods. Computational results for the rectangle packing problem and a real-world scheduling problem exhibit good prospects of the proposed techniques.

Reviews

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