Nesting. Berechnung oberer und unterer Schranken

Wir präsentieren Algorithmen zur Berechnung oberer und unterer Schranken für zweidimensionale Anordnungsprobleme (bezeichnet als Nesting-Probleme). Beim Nesting-Problem ist eine Menge irregulär geformter planarer Objekte (bezeichnet als Schablonen) auf einer Unterlage zu plazieren, die als begrenzte oder unbegrenzte planare Region gegeben sein kann. Eine Plazierung der Schablonen auf der Unterlage wird als Schnittbild bezeichnet. Ziel ist die Minimierung des Verschnitts in dem zu erstellenden Schnittbild. Je nach industrieller Anwendung sind unterschiedliche Nebenbedingungen zu berücksichtigen. In dieser Arbeit untersuchen wir Nesting-Probleme unter den speziellen Randbedingungen, die in der textilverarbeitenden Industrie auftreten. In der gegenwärtigen industriellen Praxis werden Schnittbilder manuell durch hochqualifiziertes Personal erstellt. Wir entwickeln Verfahren, die vollautomatisch ohne jegliche Unterstützung von Experten Schnittbilder erstellen und die enge Garantien für die Qualität dieser Schnittbilder geben. Für die Berechnung oberer Schranken benutzen wir randomisierte, heuristische Greedy-Verfahren, die auf dem Konzept von Hodographen beruhen, datenbankgestützte Verfahren, die geometrische Mustererkennungsmethoden einsetzen, und globale Optimierung basierend auf Varianten von Simulated Annealing. Die Berechnung unterer Schranken erfolgt durch ein Branch-And-Bound Verfahren. Dieses Verfahren benutzt eine diskrete Beschreibung des Anordnungsraums, der die Menge legaler Plazierungspositionen der Schablonen relativ zueinander beschreibt, für eine hierarchische Suche basierend auf einer fortlaufenden Verfeinerung von Hodographen. Wir berechnen die unteren Schranken für Teilprobleme, die einen Schluß auf untere Schranken für das Gesamtproblem zulassen. Wir testen unsere Methoden auf einer großen Menge von Datensätzen, die wir aus der textilverarbeitenden Industrie erhalten haben. Gute obere Schranken für diese Datensätze können wir auf einem heute üblichen Arbeitsplatzrechner in weniger als einer Stunde berechnen. Die Auslastungen sind zu den von einem Experten erzielten Auslastungen konkurrenzfähig. Untere Schranken werden innerhalb weniger Stunden berechnet und sind nur wenige Prozentpunkte von den besten bekannten oberen Schranken entfernt (z.B. 0.4% bei Hosen).

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).