Abstract

In vielen industriellen Anwendungsgebieten sind geometrische Packungsprobleme zu lösen, so möchte man zum Beispiel bei der Verarbeitung von Blech den Verschnitt minimieren: Gegeben ist eine Menge von Blechteilen, von denen möglichst viele auf einem größeren Blech verteilt werden. Die verbleibenden Blechreste sollen dann noch von der Arbeitsfläche entfernt werden. Typischerweise geschieht dies durch „Wegstanzen“ der Blechreste. Es stehen hierfür verschieden Stanzköpfe zur Verfügung. Ziel ist es, mit möglichst wenig Stanzvorgängen und möglichst wenig Wechseln des Stanzkopfes alle Blechreste zu entfernen. Hierbei gilt es zwei Dinge zu beachten:

die verbleibende Restfläche sollte aus Stabilitätsgründen zusammenhängend bleiben

beim Stanzvorgang muss mindestens die Hälfte der Stanzkopffläche auch wirklich mit Material unterlegt sein (d.h. Ausschließliche Benutzung des größten Stanzkopfes ist nicht immer möglich)

Im Rahmen dieser Diplomarbeit wurde von Grund auf ein Verfahren entwickelt, welches dieses Problem zu lösen versucht. Um die Komplexität des Problems zu reduzieren wurden einige Einschränkungen bezügliche der Probleminstanzen vorgenommen. So wurde festgelegt, dass nur polygonale Wertstücke vom Blech entfernt werden dürfen und die Form der zur Auswahl stehenden Stanzköpfe muss rund sein. Der Hauptaugenmerk der Arbeit liegt auf der Beachtung der Nebenbedingungen. Vor allem für die Sicherstellung des Zusammenhangs der Fläche wurden Ideen entwickelt um umgesetzt. Hierbei spielt die mediale Achse eine besondere Rolle, indem sie als Grundlage für einen Großteil der vorgestellten Verfahren eingesetzt wird. Neben dem Einsatz für die Konnektivitätstest dient sie zusätzlich als Struktur für eine vereinfachte Darstellung einer Fläche. Besondere Merkmale des zu überdeckenden Gebiets können so besser erkannt und genutzt werden.