Abstract:

In this paper, we consider the two-dimensional rectangular strip packing problem. Computers are especially efficient at producing and evaluating possible packings of a given set of rectangles. However, the characteristics of the search space appear to make it not amenable to standard local search techniques, such as simulated annealing or genetic algorithms. A standard simple heuristic, Bottom-Left-Decreasing, has been shown to handily beat these more sophisticated search techniques. We present several new approaches to the problem. We show that a branch-and-bound-based exhaustive search is much more effective than previous methods for problems with less than 30 rectangles when the rectangles can be tightly packed with little or no unused space. For larger problems, we introduce and demonstrate the effectiveness of a natural improvement to the Bottom-Left-Decreasing heuristic. Furthermore, 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 significantly better solutions than previous methods on benchmark problems.