The nesting problem in the leather manufacturing industry

The part-nesting problem is the problem of arranging a set of plane irregularly shaped parts on a plane irregularly shaped surface, such that no parts overlap and as much of the surface is covered as possible. This problem occurs, e.g., in the textile and clothing industry, and one of the most challenging applications appears in the manufacturing of leather, e.g., in the furniture, car, clothing, and shoe industry. This application is characterized by a high degree of inhomogeneity of the surface as well as the parts and by severe restrictions on run time. The authors present an algorithmic method for computer-aided nesting in this context. The algorithm is characterized by selective data reduction, sequential part placement, a topological part fitting process, and a carefully tuned evaluation function for partial placements. Experiments show that the method is competitive with human nesters, for relatively nicely behaved part sets and surfaces.