New Heuristic and Interactive Approaches to 2D Rectangular Strip Packing.pdf

MITSUBISHI ELECTRIC RESEARCH LABORATORIES New Heuristic and Interactive Approaches to 2D Rectangular Strip Packing N. Lesh, J. Marks, A. McMahon, M. Mitzenmacher TR2005-113 December 2005 Abstract In this paper, we consider the two-dimensional rectangular strip packing problem. A standard simple heutistic, Bottom-Left-Decreasing (BLD), has been shown to perform quite well in prac- tice. We introduce and demonstrate the effectiveness of BLD, a stochastic search variation of BLD. While BLD places the rectangles in decreasing order of heigh, width, area and perime- ter, BLD successively tries random orderings, chosen from a distribution determined by their Kendall-tau distance from one of these fixed orderings. Our experiments on benchmark prob- lems show that BLD produces significantly better packings than BLD after only 1 minute of computation. Furthermore, we show that BLD outperforms recently reported methaheuristics. Furthermore, we observe that people seem able to reason about packing problems extremely well. We incorporate our new algorithms in an interactive system that combines the advantages of computer speed and human reasoning. Using the interactive system, we are able to quickly produce signiticantly better solutions than BLD by itself. Journal of Experimental Algorithmics (JEA) This work may not be copied or reproduced in whole or in part for any commercial purpose. Permission to copy in whole or in part without payment of fee is granted for nonprofit educational and research purposes provided that all such whole or partial copies include the following: a notice that such copying is by permission of Mitsubishi Electric Research Laboratories, Inc.; an acknowledgment of the authors and individual contributions to the work; and all applicable portions of the copyright notice. Copying, reproduction, or republishing for any other purpose shall require a license with payment of fee to Mitsubishi Electric Research Laboratories, Inc. All rights reserved. Copyright