Affordable Access

Nesting. Berechnung oberer und unterer Schranken

GMD Forschungszentrum Informationstechnik, Sankt Augustin
Publication Date
  • Computer Science
  • Law
  • Mathematics


We present lower and upper bound algorithms for two-dimensional arrangement problems (called nesting problems). In a nesting problem, a set of irregularly shaped planar objects called stencils has to be placed onto a surface which can be a bounded or unbounded planar region. A placement of the stencils on the surface is called cutting image or marker. The goal is to minimize the waste of a marker. Diverse constraints coming from the different fields of industrial application have to be considered. In this study, we examine nesting problems under the special constraints given in the textile manufacturing industry. Today's industrial practice is characterized by interactive placement systems which are used by highly skilled personnel. We develop algorithms which solve the task of generating cutting images fully automatically and which can give tight performance guarantees on the quality of these markers. For the calculation of upper bounds we use greedy strategies based on hodographs which apply randomized heuristic rules for generating legal arrangements of the stencils, a database approach which uses geometric pattern matching methods, and global optimization based on variants of simulated annealing. For the lower bounds we use branch-and-bound methods which work on discrete representations of the configuration space describing the set of legal placement positions of the stencils relative to each other. We calculate our lower bounds on placement subproblems that determine the performance of the overall problem. We validate our methods on a large amount of data sets taken from the textile manufacturing industry. The upper bounds are computed in less than an hour on a common-day workstation and are competitive in quality with results obtained by human nesters. The lower bounds take a few hours to compute and are within a few percentage points of the best known upper bounds (e.g., 0.4% for pants).

There are no comments yet on this publication. Be the first to share your thoughts.