Browsing by Author "Hildinger, Markus"

Now showing 1 - 2 of 2

Open Access
Abdeckung von Verschnittresten unter Konnektivitätsbedingungen
(2015) Hildinger, Markus
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.
Open Access
Algorithmen zur Optimierung von Packungsproblemen
(2014) Hildinger, Markus
In vielen industriellen Anwendungsgebieten sind geometrische Packungsprobleme zu lösen, so möchte man zum Beispiel bei der Verarbeitung von Blech oder Stoffen oft den Verschnitt minimieren. Dass heißt, es wird eine Form vorgegeben, die möglichst oft auf einer größeren Fläche platziert werden soll. Die platzierten Formen müssen komplett sein, dass heißt, sie dürfen sich nicht überschneiden und nicht über den Rand hinausragen. Packungsprobleme gehören zur Klasse der NP-vollständigen Probleme. Dies bedeutet, es gibt keinen effizienten Algorithmus (Polynomialzeit-Algorithmus), der in jedem Fall eine optimale Lösung liefern kann, es sei denn, es kann bewiesen werden, dass die Komplexitätsklasse NP gleich der Komplexitätsklasse P ist. Da also keine optimale Lösung in vertretbarer Zeit gefunden werden kann, gilt es, Algorithmen zu entwickeln, welche Ergebnisse liefern, die einer optimalen Lösung so nahe wie möglich kommen. Ziel dieser Studienarbeit ist es, solche Algorithmen zu entwickeln. Um die Komplexität des Problems im Rahmen zu halten, wurden einige Vereinfachungen vorgenommen. So wird das Feld, auf dem die Figuren platziert werden sollen, stets ein Rechteck sein. Des weiteren wird es auch nur eine Figur geben, die auf der Fläche verteilt werden kann und, damit keine gekrümmten Begrenzungen beachtet werden müssen, muss die Figur ein Polygon sein.