A simple and effective heuristic to solve the manufacturing pallet loading problem

In this paper we present a simple and effective heuristic to solve the pallet loading problem (PLP) with identical boxes, namely the manufacturer's PLP. Basically, the problem consists of arranging the maximum number of rectangles (l, w) into a larger rectangle (L, W) without overlapping. This problem also arises in the loading of pallets into trucks or rail cars, and in the design of packages which will be further combined to form a unit load. Although apparently easy to be optimally solved, the manufacturer's PLP is difficult from the perspective of the complexity theory, and several authors have proposed approximate methods to treat it. In this paper we present a refinement of Bischoff and Dowsland's heuristic which is easily implementable in a computer and provided the optimal solution of all examples here analysed.