Determining an upper bound for a class of rectangular packing problems

Solutions to the two-dimensional, rectangular orthogonal packing problem rarely guarantee optimality, as exact algorithms require a prohibitive amount of computing time. A means of calculating the maximum number of boxes which can be fitted would be useful, both as a measure of optimality, and as an aspiration level. Existing estimates are accurate for approximately 15% of problems typically encountered in pallet loading applications. This paper discusses a technique for reducing the loading area before applying these estimates and shows that their effectiveness can be increased to provide an exact solution for over 70% of a random data sample.