Algorithms for Nesting Problems

The Nesting Problem naturally appears in the context of several production processes, as in the textile, wood or steel industries, whenever is necessary to cut pieces with irregular (non-rectangular) shapes from larger plates. This problem belongs to the more generic class of Cutting and Packing problems.Usually the Nesting Problem is solved using interactive computer graphics approaches, being very few the completely automatic approaches known. In this paper we present an automatic layout algorithm for the Nesting Problem, based in the Simulated Annealing approach to combinatorial optimization problems.Our algorithm has been implemented in two versions. The first version assumes that the irregular pieces are represented in a raster form. In the second one, a more precise one, the pieces are represented by a set of vertices that connected by straight lines define a polygon.The main purpose of the paper is to report, in a compact form, our extensive numerical experiences while developing the final versions of the algorithm. In addition, our experiences of solving the Nesting Problem with a simple local search algorithm will also be presented.