A heuristic of simple tabu search for the problem of loading pallets of the producer

The manufacturer's pallet loading problem consists in arranging, orthogonally and without overlapping, the maximum number of boxes with dimensions (l,w) or (w,l) onto a rectangular pallet with dimensions (L,W). This problem has been handled successfully by block heuristics, which generate loading patterns composed by one or more blocks where the pieces have the same orientation. A feature of such methods is that the patterns are limited to the so called 1st order non-guillotine patterns. In this work we propose an approach based on the incorporation of simple tabu search (without longer term memory structures) in block heuristics. Starting from an initial pattern, the algorithm performs moves that increase the size of selected blocks in the current pattern; as a result, other blocks are decreased, eliminated or created. Computational results indicate that the approach is capable of generating superior order optimal patterns for difficult instances reported in the literature.