Bibliographic Metadata

Title
Konstruktive Algorithmen für zweidimensionale Packungsprobleme: Implementierung und Analyse / Michél Rifaat
Additional Titles
Constructive algorithms for two-dimensional packing problems: Implementation and analysis
AuthorSchenouda, Michél Rifaat
CensorPferschy Ulrich
Published2012
DescriptionV, 51 Bl. : 2 Zsfassungen ; graph. Darst.
Institutional NoteGraz, Univ., Masterarb., 2012
Annotation
Zsfassung in dt. und engl. Sprache
Annotation
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
LanguageGerman
Document typeMaster Thesis
Keywords (GND)Packungsproblem / Algorithmus / Packungsproblem / Algorithmus / Online-Publikation
URNurn:nbn:at:at-ubg:1-34618 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Konstruktive Algorithmen für zweidimensionale Packungsprobleme: Implementierung und Analyse [1.5 mb]
Links
Reference
Classification
Abstract (German)

Das Ziel dieser Arbeit war es, zwei konstruktive Algorithmen für das zweidimensionale Rechtecke Packungsproblem zu vergleichen und analysieren. Dies wurde durch die Implementierung mit der Programmiersprache PERL, welche sich für die schnelle Softwareentwicklung eignet, bewerkstelligt. iel bei der Umsetzung der Algorithmen durch die Programmiersprache Perl war es, ohne den Einsatz von Modulen und Bibliotheken auszukommen und sich ausschließlich auf die Basissprachelemente und Konstrukte zu beschränken, um eine einfache Portierung in andere Programmiersprachen und Zielsysteme zu erleichtern, da vergleichbare Konstrukte in den meisten Programmiersprachen vorhanden sind oder sich leicht nachbilden lassen. Für das Testen der Algorithmen wurde auf die bekannten Vergleichsdaten von Hopper und Turton zurückgegriffen. Diese können als Standard für das Testen von Rechteckpackungsproblemen angesehen werden. Die Algorithmen in dieser Arbeit untersucht wurden sind folgenden zwei Artikeln entnommen:Wu, Yu-Liang et al. (2002). ?An effective quasi-human based heuristic for solving the rectangle packing problem? und Wei, Lijun et al. (2009). ?A least wasted first heuristic algorithm for the rectangular packing problem?. Die Absicht war, den less flexibility first Algorithmus (2002) mit dem least wasted first Algorithmus (2009) innerhalb der gleichen Umgebung zu vergleichen, um unverfälschte Resultate über deren Leistung zu erhalten. Für die ausgewählten Testdaten übertraf der least wasted first Algorithmus seinen Kontrahenten mit deutlichem Abstand. Dies bestätigte frühere Erkenntnisse von Hopper und Turton, dass Heuristiken mit Verbesserungsverfahren kombiniert zu einer besonders guten Leistung führen.

Abstract (English)

The objective of this work was to compare and analyze two constructive algorithms for the two-dimensional rectangle packing problem. This has been done by implementing both heuristic algorithms with the programming language PERL which is capable of rapid prototyping. Aim in implementing the algorithms in the Perl programming language was to dispense with the use of modules and libraries and to focus solely on the basis of language elements and constructs in order to facilitate easy porting to other programming languages ??and target systems, since similar constructs in most programming languages ??are available or can be easily simulated. The testing of algorithms has been done with classical benchmark instances provided by Hopper and Turton. These are seen as standard for testing rectangle packing problems. The two papers from which the algorithms examined in this thesis were taken are the following: Wu, Yu-Liang et al. (2002). ?An effective quasi-human based heuristic for solving the rectangle packing problem? and Wei, Lijun et al. (2009). ?A least wasted first heuristic algorithm for the rectangular packing problem?. The intention was also to compare the less flexibility first algorithm (2002) and the least wasted first algorithm (2009) within the same environment to obtain unbiased results over their performance. For the selected test-data the least wasted first algorithm outperformed its competitor by a considerable margin. This confirmed earlier findings by Hopper and Turton that heuristics combined with improvement strategies yield heuristics with favorable performance.

Stats
The PDF-Document has been downloaded 87 times.