Materialoptimierung durch AutoNesting

Eine immer wiederkehrende Anforderung in vielen Industriezweigen ist der effiziente Umgang mit Material, um aus einem Rohling möglichst viele Produkte und möglichst wenig Verschnitt zu erzeugen. Dabei variieren die Anforderungen nach Einsatz deutlich.

So geht es in der glasverarbeitenden Industrie meistens darum, aus einem großen rechteckigen Stück Glas möglichst viele kleinere, ebenfalls rechteckige Scheiben zu schneiden. Bei der Verarbeitung von Leder liegt hingegen kein rechteckiges Ausgangmaterial vor und auch die daraus zu schneidenden Formen (beispielsweise für Bekleidung oder Autositze) sind sehr unregelmäßig.

Die Optimierung der Materialausnutzung wird von hoch spezialisierten Experten oder, in zunehmendem Maße, von softwaretechnischen Lösungen durchgeführt.

Lachmann & Rink stellte sich im zurückliegenden Jahr der Herausforderung, ein solches System zu entwickeln. Die prinzipielle Aufgabe besteht darin, auf einem rechteckigen Ausgangsmaterial beliebig geformte Teile zu platzieren (zu „nesten“). Neben der Verschnittminimierung ist eine möglichst geringe Laufzeit bis zur Findung der Lösung ebenfalls eine Forderung.

So stand am Anfang des Projekts die Suche nach bekannten Lösungen für diese Problemstellung. Dabei stellte sich nach recht kurzer Zeit heraus, dass es zu der Platzierung von „irregulären, nicht-konvexen Objekten“ kein bekanntes (und praktikables) Verfahren gibt, welches immer die optimale Lösung liefert. Zudem
sind alle veröffentlichten Lösungsansätze, die dann auf Heuristiken basieren, zum Zwecke der Vereinfachung mit starken Einschränkungen versehen.

So setzte sich dann recht schnell die Erkenntnis durch, dass das Entwickeln eines tragfähigen Lösungsansatzes eine große Herausforderung darstellt.

Zur Überwindung der ersten Hürde entschlossen wir uns zur Kooperation mit dem Fachbereich Informatik der Universität Dortmund. Dort erklärte sich Herr Matthias Hebbel bereit, sich der Aufgabenstellung im Rahmen seiner Diplomarbeit anzunehmen. Im ersten Schritt wurde dann folgende grundsätzliche Lösungsidee entwickelt: Jedes Teil wird durch das umschreibende Rechteck, die so genannte „Bounding Box“ repräsentiert.

Diese Rechtecke werden anschließend mit Hilfe eines bekannten Algorithmus auf das Rohmaterial „genestet“, so dass ein erstes Zwischenergebnis entsteht, das allerdings kaum den Anforderungen an das System genügen dürfte.

Zur Verbesserung des Ergebnisses betrachtet man als nächstes das Teil, das innerhalb seiner Bounding Box den größten Verschnitt aufweist (Teil A). Zu diesem Teil sucht man dann aus der Menge der zu platzierenden Teile das Teil (Teil B), das sich zu Teil A so anordnen lässt, dass die gemeinsame Bounding Box nun wiederum möglich wenig Verschnitt aufweist.

Dabei dürfen die Teile, gemäß den jeweils geltenden Einschränkungen, in belie-bigen Schritten oder nur in 90° oder 180° Schritten gedreht werden. Auch Spie-gelungen sind optional zulässig. Dabei muss, je nach Verwendungszweck, auch ein gewisser Mindestabstand zwischen den Teilen eingehalten werden, da es ja

z. B. keine beliebig dünnen Sägen o. ä. gibt.