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.

Simulation studies of correlation functions and relaxation in polymeric systems

We investigate the statics and dynamics of a glassy,non-entangled, short bead-spring polymer melt with moleculardynamics simulations. Temperature ranges from slightlyabove the mode-coupling critical temperature to the liquidregime where features of a glassy liquid are absent. Ouraim is to work out the polymer specific effects on therelaxation and particle correlation. We find the intra-chain static structure unaffected bytemperature, it depends only on the distance of monomersalong the backbone. In contrast, the distinct inter-chainstructure shows pronounced site-dependence effects at thelength-scales of the chain and the nearest neighbordistance. There, we also find the strongest temperaturedependence which drives the glass transition. Both the siteaveraged coupling of the monomer and center of mass (CM) andthe CM-CM coupling are weak and presumably not responsiblefor a peak in the coherent relaxation time at the chain'slength scale. Chains rather emerge as soft, easilyinterpenetrating objects. Three particle correlations arewell reproduced by the convolution approximation with theexception of model dependent deviations. In the spatially heterogeneous dynamics of our system weidentify highly mobile monomers which tend to follow eachother in one-dimensional paths forming ``strings''. Thesestrings have an exponential length distribution and aregenerally short compared to the chain length. Thus, arelaxation mechanism in which neighboring mobile monomersmove along the backbone of the chain seems unlikely.However, the correlation of bonded neighbors is enhanced. When liquids are confined between two surfaces in relativesliding motion kinetic friction is observed. We study ageneric model setup by molecular dynamics simulations for awide range of sliding speeds, temperatures, loads, andlubricant coverings for simple and molecular fluids. Instabilities in the particle trajectories are identified asthe origin of kinetic friction. They lead to high particlevelocities of fluid atoms which are gradually dissipatedresulting in a friction force. In commensurate systemsfluid atoms follow continuous trajectories for sub-monolayercoverings and consequently, friction vanishes at low slidingspeeds. For incommensurate systems the velocity probabilitydistribution exhibits approximately exponential tails. Weconnect this velocity distribution to the kinetic frictionforce which reaches a constant value at low sliding speeds. This approach agrees well with the friction obtaineddirectly from simulations and explains Amontons' law on themicroscopic level. Molecular bonds in commensurate systemslead to incommensurate behavior, but do not change thequalitative behavior of incommensurate systems. However,crossed chains form stable load bearing asperities whichstrongly increase friction.

Dynamics, rheology and critical properties of colloidal fluid mixtures

Liquids under the influence of external fields exhibit a wide range of intriguing phenomena that can be markedly different from the behaviour of a quiescent system. This work considers two different systems — a glassforming Yukawa system and a colloid-polymer mixture — by Molecular Dynamics (MD) computer simulations coupled to dissipative particle dynamics. The former consists of a 50-50 binary mixture of differently-sized, like-charged colloids interacting via a screened Coulomb (Yukawa) potential. Near the glass transition the influence of an external shear field is studied. In particular, the transition from elastic response to plastic flow is of interest. At first, this model is characterised in equilibrium. Upon decreasing temperature it exhibits the typical dynamics of glassforming liquids, i.e. the structural relaxation time τα grows strongly in a rather small temperature range. This is discussed with respect to the mode-coupling theory of the glass transition (MCT). For the simulation of bulk systems under shear, Lees-Edwards boundary conditions are applied. At constant shear rates γ˙ ≫ 1/τα the relevant time scale is given by 1/γ˙ and the system shows shear thinning behaviour. In order to understand the pronounced differences between a quiescent system and a system under shear, the response to a suddenly commencing or terminating shear flow is studied. After the switch-on of the shear field the shear stress shows an overshoot, marking the transition from elastic to plastic deformation, which is connected to a super-diffusive increase of the mean squared displacement. Since the average static structure only depends on the value of the shear stress, it does not discriminate between those two regimes. The distribution of local stresses, in contrast, becomes broader as soon as the system starts flowing. After a switch-off of the shear field, these additional fluctuations are responsible for the fast decay of stresses, which occurs on a time scale 1/γ˙ . The stress decay after a switch-off in the elastic regime, on the other hand, happens on the much larger time scale of structural relaxation τα. While stresses decrease to zero after a switch-off for temperatures above the glass transition, they decay to a finite value for lower temperatures. The obtained results are important for advancing new theoretical approaches in the framework of mode-coupling theory. Furthermore, they suggest new experimental investigations on colloidal systems. The colloid-polymer mixture is studied in the context of the behaviour near the critical point of phase separation. For the MD simulations a new effective model with soft interaction potentials is introduced and its phase diagram is presented. Here, mainly the equilibrium properties of this model are characterised. While the self-diffusion constants of colloids and polymers do not change strongly when the critical point is approached, critical slowing down of interdiffusion is observed. The order parameter fluctuations can be determined through the long-wavelength limit of static structure factors. For this strongly asymmetric mixture it is shown how the relevant structure factor can be extracted by a diagonalisation of a matrix that contains the partial static structure factors. By presenting first results of this model under shear it is demonstrated that it is suitable for non-equilibrium simulations as well.

Interacting quantum-dissipative tunnelling systems

Die Untersuchung von dissipativen Quantensystemen erm¨oglicht es, Quantenph¨anomene auch auf makroskopischen L¨angenskalen zu beobachten. Das in dieser Dissertation gew¨ahlte mikroskopische Modell erlaubt es, den bisher nur ph¨anomenologisch zug¨anglichen Effekt der Quantendissipation mathematisch und physikalisch herzuleiten und zu untersuchen. Bei dem betrachteten mikroskopischen Modell handelt es sich um eine 1-dimensionale Kette von harmonischen Freiheitsgraden, die sowohl untereinander als auch an r anharmonische Freiheitsgrade gekoppelt sind. Die F¨alle einer, respektive zwei anharmonischer Bindungen werden in dieser Arbeit explizit betrachtet. Hierf¨ur wird eine analytische Trennung der harmonischen von den anharmonischen Freiheitsgraden auf zwei verschiedenen Wegen durchgef¨uhrt. Das anharmonische Potential wird als symmetrisches Doppelmuldenpotential gew¨ahlt, welches mit Hilfe der Wick Rotation die Berechnung der ¨Uberg¨ange zwischen beiden Minima erlaubt. Das Eliminieren der harmonischen Freiheitsgrade erfolgt mit Hilfe des wohlbekannten Feynman-Vernon Pfadintegral-Formalismus [21]. In dieser Arbeit wird zuerst die Positionsabh¨angigkeit einer anharmonischen Bindung im Tunnelverhalten untersucht. F¨ur den Fall einer fernab von den R¨andern lokalisierten anharmonischen Bindung wird ein Ohmsches dissipatives Tunneln gefunden, was bei der Temperatur T = 0 zu einem Phasen¨ubergang in Abh¨angigkeit einer kritischen Kopplungskonstanten Ccrit f¨uhrt. Dieser Phasen¨ubergang wurde bereits in rein ph¨anomenologisches Modellen mit Ohmscher Dissipation durch das Abbilden des Systems auf das Ising-Modell [26] erkl¨art. Wenn die anharmonische Bindung jedoch an einem der R¨ander der makroskopisch grossen Kette liegt, tritt nach einer vom Abstand der beiden anharmonischen Bindungen abh¨angigen Zeit tD ein ¨Ubergang von Ohmscher zu super- Ohmscher Dissipation auf, welche im Kern KM(τ ) klar sichtbar ist. F¨ur zwei anharmonische Bindungen spielt deren indirekteWechselwirkung eine entscheidende Rolle. Es wird gezeigt, dass der Abstand D beider Bindungen und die Wahl des Anfangs- und Endzustandes die Dissipation bestimmt. Unter der Annahme, dass beide anharmonischen Bindung gleichzeitig tunneln, wird eine Tunnelwahrscheinlichkeit p(t) analog zu [14], jedoch f¨ur zwei anharmonische Bindungen, berechnet. Als Resultat erhalten wir entweder Ohmsche Dissipation f¨ur den Fall, dass beide anharmonischen Bindungen ihre Gesamtl¨ange ¨andern, oder super-Ohmsche Dissipation, wenn beide anharmonischen Bindungen durch das Tunneln ihre Gesamtl¨ange nicht ¨andern.

Computer simulations of slowly relaxing systems in external fields

Eine der offenen Fragen der aktuellen Physik ist das Verständnis von Systemen im Nichtgleichgewicht. Im Gegensatz zu der Gleichgewichtsphysik ist in diesem Bereich aktuell kein Formalismus bekannt der ein systematisches Beschreiben der unterschiedlichen Systeme ermöglicht. Um das Verständnis über diese Systeme zu vergrößern werden in dieser Arbeit zwei unterschiedliche Systeme studiert, die unter einem externen Feld ein starkes nichtlineares Verhalten zeigen. Hierbei handelt es sich zum einen um das Verhalten von Teilchen unter dem Einfluss einer extern angelegten Kraft und zum anderen um das Verhalten eines Systems in der Nähe des kritischen Punktes unter Scherung. Das Modellsystem in dem ersten Teil der Arbeit ist eine binäre Yukawa Mischung, die bei tiefen Temperaturen einen Glassübergang zeigt. Dies führt zu einer stark ansteigenden Relaxationszeit des Systems, so dass man auch bei kleinen Kräften relativ schnell ein nichtlineares Verhalten beobachtet. In Abhängigkeit der angelegten konstanten Kraft können in dieser Arbeit drei Regime, mit stark unterschiedlichem Teilchenverhalten, identifiziert werden. In dem zweiten Teil der Arbeit wird das Ising-Modell unter Scherung betrachtet. In der Nähe des kritischen Punkts kommt es in diesem Modell zu einer Beeinflussung der Fluktuationen in dem System durch das angelegte Scherfeld. Dies hat zur Folge, dass das System stark anisotrop wird und man zwei unterschiedliche Korrelationslängen vorfindet, die mit unterschiedlichen Exponenten divergieren. Infolgedessen lässt sich der normale isotrope Formalismus des "finite-size scaling" nicht mehr auf dieses System anwenden. In dieser Arbeit wird gezeigt, wie dieser auf den anisotropen Fall zu verallgemeinern ist und wie damit die kritischen Punkte, sowie die dazu gehörenden kritischen Exponenten berechnet werden können.

Characterisation of human co-culture systems for applications in bone tissue engineering

For the successful integration of bone tissue engineering constructs into patients, an adequate supply with oxygen and nutrients is critical. Therefore, prevascularisation of bone tissue engineering constructs is desirable for bone formation, remodelling and regeneration. Co-culture systems, consisting of human endothelial cells and primary osteoblasts (pOB) as well as osteosarcoma cell lines, represent a promising method for studying the mechanisms involved in the vascularisation of constructs in bone tissue en- gineering and could provide new insights into the molecular and cellular mechanisms that control essential processes during angiogenesis. The present study demonstrated the im- portant components of co-culture systems with a focus on bone tissue replacement and the angiogenic effects of pOB and osteosarcoma cell lines on human endothelial cells. Furthermore, the studies emphasised an overall approach for analysis of signal molecules that are involved in the angiogenic activation of human endothelial cells by the regulation of VEGF-related pathways at the transcriptional and translational levels. The osteosarcoma cell lines Cal-72, MG-63 and SaOS-2, as well as pOB from several donors, differed in their angiogenesis-inducing potential in 2-D and 3-D co-culture systems. SaOS-2 cells appeared to have a high osteogenic differentiation level with no detectable angiogenesis-inducing potential in co-culture with human endothelial cells. The angiogenic potential of the osteoblast-like cells is mainly correlated with the upregulation of essential angiogenic growth factors, such as VEGF, bFGF and HGF and the downregulation of the angiogenesis inhibitor, endostatin. However, other factors involved in angiogenic regulation were found to differ between SaOS-2 cells, compared to Cal-72 and MG-63. The present study focuses on VEGF pathway-effecting genes as key players in the regulation of angiogenesis. The levels of VEGF and VEGF-effecting genes, such as TGF-α and TIMP-2 are down-regulated in SaOS-2 cells. In contrast, direct regulators of VEGF, such as IL6, IL8 and TNF are strongly upregulated, which indicates disruptions in growth factor regulating pathways in SaOS-2 cells. Potential pathways, which could be involved include MEK, PI3K, MAPK, STAT3, AKT or ERK. Additional treatment of co-cultures with single growth factors did not accelerate or improve the angiogenesis-inducing potential of SaOS-2 cells. Knowledge of the detailed molecular mechanisms involved in angiogenesis control will hopefully allow improved approaches to be developed for prevascularisation of bone tissue engineering constructs.