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 practice. 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 perimeter, 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 problems 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.