Volumenpackungen nach SAE J1100

We 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.

High precision swept volume approximation with conservative error bounds

In technical design processes in the automotive industry, digital prototypes rapidly gain importance, because they allow for a detection of design errors in early development stages. The technical design process includes the computation of swept volumes for maintainability analysis and clearance checks. The swept volume is very useful, for example, to identify problem areas where a safety distance might not be kept. With the explicit construction of the swept volume an engineer gets evidence on how the shape of components that come too close have to be modified.rnIn this thesis a concept for the approximation of the outer boundary of a swept volume is developed. For safety reasons, it is essential that the approximation is conservative, i.e., that the swept volume is completely enclosed by the approximation. On the other hand, one wishes to approximate the swept volume as precisely as possible. In this work, we will show, that the one-sided Hausdorff distance is the adequate measure for the error of the approximation, when the intended usage is clearance checks, continuous collision detection and maintainability analysis in CAD. We present two implementations that apply the concept and generate a manifold triangle mesh that approximates the outer boundary of a swept volume. Both algorithms are two-phased: a sweeping phase which generates a conservative voxelization of the swept volume, and the actual mesh generation which is based on restricted Delaunay refinement. This approach ensures a high precision of the approximation while respecting conservativeness.rnThe benchmarks for our test are amongst others real world scenarios that come from the automotive industry.rnFurther, we introduce a method to relate parts of an already computed swept volume boundary to those triangles of the generator, that come closest during the sweep. We use this to verify as well as to colorize meshes resulting from our implementations.

Konzept eines aktiven Pulverinhalators

In dieser Arbeit wird das Konzept eines aktiven Pulverinhalators entwickelt. Im Gegensatz zu einem passiven Pulverinhalator ist bei solch einem Gerät die Abgabe und Dispergierung der Arzneistoffformulierung nicht von einem Inhalationsmanöver abhängig, welches von Patient zu Patient variiert. Solch ein System würde folglich die Zuverlässigkeit und Effizienz der inhalativen Therapie verbessern. Mögliche Anwendungen für einen aktiven Pulverinhalator wären vor allem Indikationen, die die Abgabe hoher Dosen erfordern, wie z.B. in der Therapie mit Antibiotika.rnIn einem Designprozess, der alle aus Kundenwünschen ermittelten Konstruktionsanforderungen sammelt und verschiedene Lösungsansätze vergleicht, wird ein mit Treibgas betriebener atemzugsausgelöster, Mehrfach-Dosis Pulverinhalator als aussichtsreichstes Konzept ermittelt. Dieses Konzept wird in Form von eigens konstruierten Labor-Test-Rigs entwickelt und vor allem hinsichtlich Höhe der Dosierung, Dosiergenauigkeit, und Flussratenabhängigkeit evaluiert. In der Spitze können über 16 mg lungengängiger Dosis erreicht werden, bei im Vergleich zu dem eingesetzten passiven Inhalator mindestens nur halb so großer Streuung. Bei niedrigen Flussraten können immer noch bis zu 80 % der erzielten inhalierbaren Dosis von hohen Flussraten erreicht werden und damit die Ergebnisse des passiven Inhalators deutlich übertreffen.rnTeil der Aufgabe war es, dieses treibgasbetriebene Labor-Test-Rig so zu entwickeln, dass es implementierbar in einen atemzugsausgelösten Mehrfachdosis-Pulverinhalator ist. Dieser treibgasbetriebene, atemzugsausgelöste Mehrfachdosis-Pulverinhalator würde die Kundenwünsche und Konstruktionsanforderungen in sehr hohen Maße erfüllen, so dass hier die Möglichkeit besteht einen Inhalator mit sehr hohem Grad an Patienten-Compliance zu verwirklichen. Durch die Verwendung und Neukombination bereits etablierter Technologien und einen akzeptablen Stückkostenpreis besteht die Möglichkeit den Inhalator tatsächlich zu realisieren und zu vermarkten.

Optimized scheduling in real-time environments with column generation

Im Bereich sicherheitsrelevanter eingebetteter Systeme stellt sich der Designprozess von Anwendungen als sehr komplex dar. Entsprechend einer gegebenen Hardwarearchitektur lassen sich Steuergeräte aufrüsten, um alle bestehenden Prozesse und Signale pünktlich auszuführen. Die zeitlichen Anforderungen sind strikt und müssen in jeder periodischen Wiederkehr der Prozesse erfüllt sein, da die Sicherstellung der parallelen Ausführung von größter Bedeutung ist. Existierende Ansätze können schnell Designalternativen berechnen, aber sie gewährleisten nicht, dass die Kosten für die nötigen Hardwareänderungen minimal sind. Wir stellen einen Ansatz vor, der kostenminimale Lösungen für das Problem berechnet, die alle zeitlichen Bedingungen erfüllen. Unser Algorithmus verwendet Lineare Programmierung mit Spaltengenerierung, eingebettet in eine Baumstruktur, um untere und obere Schranken während des Optimierungsprozesses bereitzustellen. Die komplexen Randbedingungen zur Gewährleistung der periodischen Ausführung verlagern sich durch eine Zerlegung des Hauptproblems in unabhängige Unterprobleme, die als ganzzahlige lineare Programme formuliert sind. Sowohl die Analysen zur Prozessausführung als auch die Methoden zur Signalübertragung werden untersucht und linearisierte Darstellungen angegeben. Des Weiteren präsentieren wir eine neue Formulierung für die Ausführung mit fixierten Prioritäten, die zusätzlich Prozessantwortzeiten im schlimmsten anzunehmenden Fall berechnet, welche für Szenarien nötig sind, in denen zeitliche Bedingungen an Teilmengen von Prozessen und Signalen gegeben sind. Wir weisen die Anwendbarkeit unserer Methoden durch die Analyse von Instanzen nach, welche Prozessstrukturen aus realen Anwendungen enthalten. Unsere Ergebnisse zeigen, dass untere Schranken schnell berechnet werden können, um die Optimalität von heuristischen Lösungen zu beweisen. Wenn wir optimale Lösungen mit Antwortzeiten liefern, stellt sich unsere neue Formulierung in der Laufzeitanalyse vorteilhaft gegenüber anderen Ansätzen dar. Die besten Resultate werden mit einem hybriden Ansatz erzielt, der heuristische Startlösungen, eine Vorverarbeitung und eine heuristische mit einer kurzen nachfolgenden exakten Berechnungsphase verbindet.