Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-3232
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBaumann, Tobias
dc.date.accessioned2008-12-16T13:06:32Z
dc.date.available2008-12-16T14:06:32Z
dc.date.issued2008
dc.identifier.urihttps://openscience.ub.uni-mainz.de/handle/20.500.12030/3234-
dc.description.abstractWe present new algorithms to approximate the discrete volume of a polyhedral geometry using boxes defined by the US standard SAE J1100. This problem is NP-hard and has its main application in the car design process. The algorithms produce maximum weighted independent sets on a so-called conflict graph for a discretisation of the geometry. We present a framework to eliminate a large portion of the vertices of a graph without affecting the quality of the optimal solution. Using this framework we are also able to define the conflict graph without the use of a discretisation. For the solution of the maximum weighted independent set problem we designed an enumeration scheme which uses the restrictions of the SAE J1100 standard for an efficient upper bound computation. We evaluate the packing algorithms according to the solution quality compared to manually derived results. Finally, we compare our enumeration scheme to several other exact algorithms in terms of their runtime. Grid-based packings either tend to be not tight or have intersections between boxes. We therefore present an algorithm which can compute box packings with arbitrary placements and fixed orientations. In this algorithm we make use of approximate Minkowski Sums, computed by uniting many axis-oriented equal boxes. We developed an algorithm which computes the union of equal axis-oriented boxes efficiently. This algorithm also maintains the Minkowski Sums throughout the packing process. We also extend these algorithms for packing arbitrary objects in fixed orientations.en_GB
dc.description.abstractIn dieser Arbeit werden neue Packalgorithmen für die US-Norm SAE J1100 vorgestellt. Das diskrete Packproblem ist NP-schwer und hat hier einen direkten Bezug zur Fahrzeugentwicklung. Die Algorithmen sind exakte Verfahren für das Maximum Weighted Independent Set Problem (MWIS). Wir beschreiben eine Methode, mit der ein großer Anteil der Knoten eines Graphen entfernt werden kann, ohne dass davon die optimale Lösung des MWIS-Problems beeinträchtigt wird. Mit Hilfe dieses Verfahrens wird auch ein kontinuierlicher Graph für das Packproblem definiert. Das MWIS-Problem selbst wird mit Hilfe eines Aufzählungsalgorithmus exakt gelöst. Dieser Algorithmus nutzt die Vorgaben der US-Norm SAE J1100 zur Berechnung guter oberer Schranken. Wir vergleichen die erzielten Packungen mit denen manueller Packprozesse. Weiterhin untersuchen wir die verwendeten Aufzählungsschemata hinsichtlich ihrer Laufzeit und vergleichen sie mit weiteren Algorithmen aus der Literatur. Da bei einer gitterbasierten Packung Lücken auftreten können oder Quader sich über-schneiden, beschreiben wir einen weiteren Algorithmus, der Quaderpackungen mit beliebigen Platzierungen erzeugen kann. Dieser Packalgorithmus verwendet approximierte Minkowskisummen, die die Vereinigung vieler gleich orientierter und gleich großer Quader darstellen. Hierfür wird ebenfalls ein neuer effizienter Algorithmus vorgestellt, der auch die Verwaltung der Minkowskisummen während des Packens übernimmt. Diese Algorithmen werden erweitert, so dass beliebige Objekte gepackt werden können.de_DE
dc.language.isoeng
dc.rightsin Copyrightde_DE
dc.rights.urihttps://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc004 Informatikde_DE
dc.subject.ddc004 Data processingen_GB
dc.titleVolumenpackungen nach SAE J1100de_DE
dc.typeDissertationde_DE
dc.identifier.urnurn:nbn:de:hebis:77-18421
dc.identifier.doihttp://doi.org/10.25358/openscience-3232-
jgu.type.dinitypedoctoralThesis
jgu.type.versionOriginal worken_GB
jgu.type.resourceText
jgu.organisation.departmentFB 08 Physik, Mathematik u. Informatik-
jgu.organisation.year2008
jgu.organisation.number7940-
jgu.organisation.nameJohannes Gutenberg-Universität Mainz-
jgu.rights.accessrightsopenAccess-
jgu.organisation.placeMainz-
jgu.subject.ddccode004
opus.date.accessioned2008-12-16T13:06:32Z
opus.date.modified2008-12-16T13:06:32Z
opus.date.available2008-12-16T14:06:32
opus.subject.otherKofferraumpacken, rekursive Enumerierung, Graphenalgorithmen, Graphenverkleinerungde_DE
opus.subject.othertrunkpacking, recursive enumeration, graph algorithms, graph simplificationen_GB
opus.organisation.stringFB 08: Physik, Mathematik und Informatik: FB 08: Physik, Mathematik und Informatikde_DE
opus.identifier.opusid1842
opus.institute.number0800
opus.metadataonlyfalse
opus.type.contenttypeDissertationde_DE
opus.type.contenttypeDissertationen_GB
Appears in collections:JGU-Publikationen

Files in This Item:
File SizeFormat 
1842.pdf6.68 MBAdobe PDFView/Open