Student Thesis STUD-2455

BibliographyHildinger, Markus: Algorithmen zur Optimierung von Packungsproblemen.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Student Thesis No. 2455 (2014).
25 pages, german.
CR-SchemaD.2.2 (Software Engineering Design Tools and Techniques)
D.2.3 (Software Engineering Coding Tools and Techniques)
D.2.6 (Software Engineering Programming Environments)
E.1 (Data Structures)
Abstract

Algorithmen zur Optimierung von Packungsproblemen

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.

Full text and
other links
PDF (1875984 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Funke, Stefan
Entry dateNovember 27, 2014
   Publ. Computer Science