On the car sequencing problem: analysis and solution methods

This work deals with the car sequencing (CS) problem, a combinatorial optimization problem for sequencing mixed-model assembly lines. The aim is to find a production sequence for different variants of a common base product, such that work overload of the respective line operators is avoided or minimized. The variants are distinguished by certain options (e.g., sun roof yes/no) and, therefore, require different processing times at the stations of the line. CS introduces a so-called sequencing rule H:N for each option, which restricts the occurrence of this option to at most H in any N consecutive variants. It seeks for a sequence that leads to no or a minimum number of sequencing rule violations. In this work, CS’ suitability for workload-oriented sequencing is analyzed. Therefore, its solution quality is compared in experiments to the related mixed-model sequencing problem. A new sequencing rule generation approach as well as a new lower bound for the problem are presented. Different exact and heuristic solution methods for CS are developed and their efficiency is shown in experiments. Furthermore, CS is adjusted and applied to a resequencing problem with pull-off tables.

Cut-first branch-and-price-second for the capacitated arc-routing problem

This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cuts and an excellent lower bound. It is known that this bound is typically stronger than relaxations of a pure set-partitioning CARP model.rnSuch a set-partitioning master program results from a Dantzig-Wolfe decomposition. In the second phase, the master program is initialized with the strong cuts, CARP tours are iteratively generated by a pricing procedure, and branching is required to produce integer solutions. This is a cut-first bap-second algorithm and its main function is, in fact, the splitting of edge flows into unique CARP tours.

Efficient subsequence alignment of time series

Zeitreihen sind allgegenwärtig. Die Erfassung und Verarbeitung kontinuierlich gemessener Daten ist in allen Bereichen der Naturwissenschaften, Medizin und Finanzwelt vertreten. Das enorme Anwachsen aufgezeichneter Datenmengen, sei es durch automatisierte Monitoring-Systeme oder integrierte Sensoren, bedarf außerordentlich schneller Algorithmen in Theorie und Praxis. Infolgedessen beschäftigt sich diese Arbeit mit der effizienten Berechnung von Teilsequenzalignments. Komplexe Algorithmen wie z.B. Anomaliedetektion, Motivfabfrage oder die unüberwachte Extraktion von prototypischen Bausteinen in Zeitreihen machen exzessiven Gebrauch von diesen Alignments. Darin begründet sich der Bedarf nach schnellen Implementierungen. Diese Arbeit untergliedert sich in drei Ansätze, die sich dieser Herausforderung widmen. Das umfasst vier Alignierungsalgorithmen und ihre Parallelisierung auf CUDA-fähiger Hardware, einen Algorithmus zur Segmentierung von Datenströmen und eine einheitliche Behandlung von Liegruppen-wertigen Zeitreihen.rnrnDer erste Beitrag ist eine vollständige CUDA-Portierung der UCR-Suite, die weltführende Implementierung von Teilsequenzalignierung. Das umfasst ein neues Berechnungsschema zur Ermittlung lokaler Alignierungsgüten unter Verwendung z-normierten euklidischen Abstands, welches auf jeder parallelen Hardware mit Unterstützung für schnelle Fouriertransformation einsetzbar ist. Des Weiteren geben wir eine SIMT-verträgliche Umsetzung der Lower-Bound-Kaskade der UCR-Suite zur effizienten Berechnung lokaler Alignierungsgüten unter Dynamic Time Warping an. Beide CUDA-Implementierungen ermöglichen eine um ein bis zwei Größenordnungen schnellere Berechnung als etablierte Methoden.rnrnAls zweites untersuchen wir zwei Linearzeit-Approximierungen für das elastische Alignment von Teilsequenzen. Auf der einen Seite behandeln wir ein SIMT-verträgliches Relaxierungschema für Greedy DTW und seine effiziente CUDA-Parallelisierung. Auf der anderen Seite führen wir ein neues lokales Abstandsmaß ein, den Gliding Elastic Match (GEM), welches mit der gleichen asymptotischen Zeitkomplexität wie Greedy DTW berechnet werden kann, jedoch eine vollständige Relaxierung der Penalty-Matrix bietet. Weitere Verbesserungen umfassen Invarianz gegen Trends auf der Messachse und uniforme Skalierung auf der Zeitachse. Des Weiteren wird eine Erweiterung von GEM zur Multi-Shape-Segmentierung diskutiert und auf Bewegungsdaten evaluiert. Beide CUDA-Parallelisierung verzeichnen Laufzeitverbesserungen um bis zu zwei Größenordnungen.rnrnDie Behandlung von Zeitreihen beschränkt sich in der Literatur in der Regel auf reellwertige Messdaten. Der dritte Beitrag umfasst eine einheitliche Methode zur Behandlung von Liegruppen-wertigen Zeitreihen. Darauf aufbauend werden Distanzmaße auf der Rotationsgruppe SO(3) und auf der euklidischen Gruppe SE(3) behandelt. Des Weiteren werden speichereffiziente Darstellungen und gruppenkompatible Erweiterungen elastischer Maße diskutiert.

An accurate combined 3 He,Cs magnetometer with fT sensitivity for the nEDM experiment at PSI

Diese Arbeit beschreibt die Entwicklung, Konstruktion und Untersuchung eines Magnetometers zur exakten und präzisen Messung schwacher Magnetfelder. Diese Art von Magnetometer eignet sich zur Anwendung in physikalischen hochpräzisions Experimenten wie zum Beispiel der Suche nach dem elektrischen Dipolmomentrndes Neutrons. Die Messmethode beruht auf der gleichzeitigen Detektion der freien Spin Präzession Kern-Spin polarisierten 3He Gases durch mehrere optisch gepumpte Cäsium Magnetometer. Es wird gezeigt, dass Cäsium Magnetometer eine zuverlässige und vielseitige Methode zur Messung der 3He Larmor Frequenz und eine komfortable Alternative zur Benutzung von SQUIDs für diesen Zweck darstellen. Ein Prototyp dieses Magnetometers wurde gebaut und seine Funktion in der magnetisch abgeschirmten Messkabine der Physikalisch Technischen Bundesanstalt untersucht. Die Sensitivität des Magnetometers in Abhängigkeitrnvon der Messdauer wurde experimentell untersucht. Es wird gezeigt, dass für kurze Messperioden (< 500s) Cramér-Rao limitierte Messungen möglich sind während die Sensitivität bei längeren Messungen durch die Stabilität des angelegten Magnetfeldes limitiert ist. Messungen eines 1 muT Magnetfeldes mit einer relative Genauigkeit von besser als 5x10^(-8) in 100s werden präsentiert. Es wird gezeigt, dass die Messgenauigkeit des Magnetometers durch die Zahl der zur Detektion der 3He Spin Präzession eingesetzten Cäsium Magnetometer skaliert werden kann. Prinzipiell ist dadurch eine Anpassung der Messgenauigkeit an jegliche experimentellen Bedürfnisse möglich. Es wird eine gradiometrische Messmethode vorgestellt, die es erlaubt den Einfluss periodischerrnmagnetischer Störungen auf dieMessung zu unterdrücken. Der Zusammenhang zwischen der Sensitivität des kombinierten Magnetometers und den Betriebsparametern der Cäsium Magnetometer die zur Spin Detektion verwendet werden wird theoretisch untersucht und anwendungsspezifische Vor- und Nachteile verschiedener Betriebsartenwerden diskutiert. Diese Zusammenhänge werden in einer Formel zusammengefasst die es erlaubt, die erwartete Sensitivität des Magnetometers zu berechnen. Diese Vorhersagen befinden sich in perfekter Übereinstimmung mit den experimentellen Daten. Die intrinsische Sensitivität des Magnetometer Prototyps wird auf Basis dieser Formel theoretisch bestimmt. Ausserdem wird die erwartete Sensitivität für die Anwendung im Rahmen des Experiments der nächsten Generation zur Bestimmung des elektrischenrnDipolmoments des Neutrons am Paul Scherrer Institut abgeschätzt. Des weiteren wird eine bequeme experimentelle Methode zur Messung des Polarisationsgrades und des Rabi Flip-Winkels der 3He Kernspin Polarisation vorgestellt. Letztere Messung ist sehr wichtig für die Anwendung in hochpräzisions Experimenten.

Aircraft-based in-situ aerosol mass spectrometry: Chemical characterization and source identification of submicron particulate matter in the free and upper troposphere and lower stratosphere

The composition of the atmosphere is frequently perturbed by the emission of gaseous and particulate matter from natural as well as anthropogenic sources. While the impact of trace gases on the radiative forcing of the climate is relatively well understood the role of aerosol is far more uncertain. Therefore, the study of the vertical distribution of particulate matter in the atmosphere and its chemical composition contribute valuable information to bridge this gap of knowledge. The chemical composition of aerosol reveals information on properties such as radiative behavior and hygroscopicity and therefore cloud condensation or ice nucleus potential. rnThis thesis focuses on aerosol pollution plumes observed in 2008 during the POLARCAT (Polar Study using Aircraft, Remote Sensing, Surface Measurements and Models, of Climate, Chemistry, Aerosols, and Transport) campaign over Greenland in June/July and CONCERT (Contrail and Cirrus Experiment) campaign over Central and Western Europe in October/November. Measurements were performed with an Aerodyne compact time-of-flight aerosol mass spectrometer (AMS) capable of online size-resolved chemical characterization of non-refractory submicron particles. In addition, the origins of pollution plumes were determined by means of modeling tools. The characterized pollution episodes originated from a large variety of sources and were encountered at distinct altitudes. They included pure natural emissions from two volcanic eruptions in 2008. By the time of detection over Western Europe between 10 and 12 km altitude the plume was about 3 months old and composed to 71 % of particulate sulfate and 21 % of carbonaceous compounds. Also, biomass burning (BB) plumes were observed over Greenland between 4 and 7 km altitude (free troposphere) originating from Canada and East Siberia. The long-range transport took roughly one and two weeks, respectively. The aerosol was composed of 78 % organic matter and 22 % particulate sulfate. Some Canadian and all Siberian BB plumes were mixed with anthropogenic emissions from fossil fuel combustion (FF) in North America and East Asia. It was found that the contribution of particulate sulfate increased with growing influences from anthropogenic activity and Asia reaching up to 37 % after more than two weeks of transport time. The most exclusively anthropogenic emission source probed in the upper troposphere was engine exhaust from commercial aircraft liners over Germany. However, in-situ characterization of this aerosol type during aircraft chasing was not possible. All long-range transport aerosol was found to have an O:C ratio close to or greater than 1 implying that low-volatility oxygenated organic aerosol was present in each case despite the variety of origins and the large range in age from 3 to 100 days. This leads to the conclusion that organic particulate matter reaches a final and uniform state of oxygenation after at least 3 days in the free troposphere. rnExcept for aircraft exhaust all emission sources mentioned above are surface-bound and thus rely on different types of vertical transport mechanisms, such as direct high altitude injection in the case of a volcanic eruption, or severe BB, or uplift by convection, to reach higher altitudes where particles can travel long distances before removal mainly caused by cloud scavenging. A lifetime for North American mixed BB and FF aerosol of 7 to 11 days was derived. This in consequence means that emission from surface point sources, e.g. volcanoes, or regions, e.g. East Asia, do not only have a relevant impact on the immediate surroundings but rather on a hemispheric scale including such climate sensitive zones as the tropopause or the Arctic.