Volumenpackungen nach SAE J1100 [Elektronische Ressource] / Tobias Baumann

Volumenpackungen nachSAE J1100Dissertationzur Erlangung des Grades\Doktorder Naturwissenschaften"am Fachbereich 08 { Physik, Mathematik und Informatikder Johannes Gutenberg-Universit atin MainzDipl.-Inf. Tobias Baumanngeb. am 25.10.1980 in SchlemaMainz, im August 2008Tag der mundlic hen Prufung: 27. November 20082ZusammenfassungIn dieser Arbeit werden neue Packalgorithmen fur die US-Norm SAE J1100 vorgestellt.Das diskrete Packproblem istNP-schwer und hat hier einen direkten Bezug zur Fahrzeug-entwicklung. Die Algorithmen sind exakte Verfahren fur das Maximum Weighted Inde-pendent Set Problem (MWIS). Wir beschreiben eine Methode, mit der ein gro er Anteilder Knoten eines Graphen entfernt werden kann, ohne dass davon die optimale L osungdes MWIS-Problems beeintr achtigt wird. Mit Hilfe dieses Verfahrens wird auch einkontinuierlicher Graph fur das Packproblem de niert.Das MWIS-Problem selbst wird mit Hilfe eines Aufzahlungsalgorithmus exakt gel ost.Dieser Algorithmus nutzt die Vorgaben der US-Norm SAE J1100 zur Berechnung guteroberer Schranken. Wir vergleichen die erzielten Packungen mit denen manueller Pack-prozesse. Weiterhin untersuchen wir die verwendeten Aufz ahlungsschemata hinsichtlichihrer Laufzeit und vergleichen sie mit weiteren Algorithmen aus der Literatur.