A simple and effective recursive procedure for the manufacturer's pallet loading problem

In this paper we present a simple and effective heuristic to solve the problem of packing the maximum number of rectangles of sizes (l, w) and (w, l) into a larger rectangle (L, W) without overlapping. This problem appears in the loading of identical boxes on pallets, namely the manufacturer's pallet loading (MPL), as well as in package design and truck or rail car loading. Although apparently easy to be optimally solved, the MPL is claimed to be NP-complete and several authors have proposed approximate methods to deal with it. The procedure described in the present paper can be seen as a refinement of Bischoff and Dowsland's heuristic and can easily be implemented on a microcomputer. Using moderate computational resources, the procedure was able to find the optimal solution of 99.9% of more than 20 000 examples analysed.