Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

Finite element models of coseismic deformation due to the 2009 L'Aquila (Italy) and 2008 Wenchuan(China) earthquakes

The topic of my Ph.D. thesis is the finite element modeling of coseismic deformation imaged by DInSAR and GPS data. I developed a method to calculate synthetic Green functions with finite element models (FEMs) and then use linear inversion methods to determine the slip distribution on the fault plane. The method is applied to the 2009 L’Aquila Earthquake (Italy) and to the 2008 Wenchuan earthquake (China). I focus on the influence of rheological features of the earth's crust by implementing seismic tomographic data and the influence of topography by implementing Digital Elevation Models (DEM) layers on the FEMs. Results for the L’Aquila earthquake highlight the non-negligible influence of the medium structure: homogeneous and heterogeneous models show discrepancies up to 20% in the fault slip distribution values. Furthermore, in the heterogeneous models a new area of slip appears above the hypocenter. Regarding the 2008 Wenchuan earthquake, the very steep topographic relief of Longmen Shan Range is implemented in my FE model. A large number of DEM layers corresponding to East China is used to achieve the complete coverage of the FE model. My objective was to explore the influence of the topography on the retrieved coseismic slip distribution. The inversion results reveals significant differences between the flat and topographic model. Thus, the flat models frequently adopted are inappropriate to represent the earth surface topographic features and especially in the case of the 2008 Wenchuan earthquake.

Toeplitz operators on finite and infinite dimensional spaces with associated psi *-Fréchet algebras

The present thesis is a contribution to the multi-variable theory of Bergman and Hardy Toeplitz operators on spaces of holomorphic functions over finite and infinite dimensional domains. In particular, we focus on certain spectral invariant Frechet operator algebras F closely related to the local symbol behavior of Toeplitz operators in F. We summarize results due to B. Gramsch et.al. on the construction of Psi_0- and Psi^*-algebras in operator algebras and corresponding scales of generalized Sobolev spaces using commutator methods, generalized Laplacians and strongly continuous group actions. In the case of the Segal-Bargmann space H^2(C^n,m) of Gaussian square integrable entire functions on C^n we determine a class of vector-fields Y(C^n) supported in complex cones K. Further, we require that for any finite subset V of Y(C^n) the Toeplitz projection P is a smooth element in the Psi_0-algebra constructed by commutator methods with respect to V. As a result we obtain Psi_0- and Psi^*-operator algebras F localized in cones K. It is an immediate consequence that F contains all Toeplitz operators T_f with a symbol f of certain regularity in an open neighborhood of K. There is a natural unitary group action on H^2(C^n,m) which is induced by weighted shifts and unitary groups on C^n. We examine the corresponding Psi^*-algebra A of smooth elements in Toeplitz-C^*-algebras. Among other results sufficient conditions on the symbol f for T_f to belong to A are given in terms of estimates on its Berezin-transform. Local aspects of the Szegö projection P_s on the Heisenbeg group and the corresponding Toeplitz operators T_f with symbol f are studied. In this connection we apply a result due to Nagel and Stein which states that for any strictly pseudo-convex domain U the projection P_s is a pseudodifferential operator of exotic type (1/2, 1/2). The second part of this thesis is devoted to the infinite dimensional theory of Bergman and Hardy spaces and the corresponding Toeplitz operators. We give a new proof of a result observed by Boland and Waelbroeck. Namely, that the space of all holomorphic functions H(U) on an open subset U of a DFN-space (dual Frechet nuclear space) is a FN-space (Frechet nuclear space) equipped with the compact open topology. Using the nuclearity of H(U) we obtain Cauchy-Weil-type integral formulas for closed subalgebras A in H_b(U), the space of all bounded holomorphic functions on U, where A separates points. Further, we prove the existence of Hardy spaces of holomorphic functions on U corresponding to the abstract Shilov boundary S_A of A and with respect to a suitable boundary measure on S_A. Finally, for a domain U in a DFN-space or a polish spaces we consider the symmetrizations m_s of measures m on U by suitable representations of a group G in the group of homeomorphisms on U. In particular,in the case where m leads to Bergman spaces of holomorphic functions on U, the group G is compact and the representation is continuous we show that m_s defines a Bergman space of holomorphic functions on U as well. This leads to unitary group representations of G on L^p- and Bergman spaces inducing operator algebras of smooth elements related to the symmetries of U.

Non linear application of an in-house finite elements software

Questa tesi si pone come obiettivo l'analisi delle componenti di sollecitazione statica di un serbatoio, in acciaio API 5L X52, sottoposto a carichi di flessione e pressione interna attraverso il programma agli elementi finiti PLCd4, sviluppato presso l'International Center for Numerical Methods in Engineering (CIMNE - Barcelona). Questo tipo di analisi rientra nel progetto europeo ULCF, il cui traguardo è lo studio della fatica a bassissimo numero di cicli per strutture in acciaio. Prima di osservare la struttura completa del serbatoio è stato studiato il comportamento del materiale per implementare all'interno del programma una nuova tipologia di curva che rappresentasse al meglio l'andamento delle tensioni interne. Attraverso il lavoro di preparazione alla tesi è stato inserito all'interno del programma un algoritmo per la distribuzione delle pressioni superficiali sui corpi 3D, successivamente utilizzato per l'analisi della pressione interna nel serbatoio. Sono state effettuate analisi FEM del serbatoio in diverse configurazioni di carico ove si è cercato di modellare al meglio la struttura portante relativa al caso reale di "full scale test". Dal punto di vista analitico i risultati ottenuti sono soddisfacenti in quanto rispecchiano un corretto comportamento del serbatoio in condizioni di pressioni molto elevate e confermano la bontà del programma nell'analisi computazionale.

Finite-element discretization of 3D energy-transport equations for semiconductors

In this thesis a mathematical model was derived that describes the charge and energy transport in semiconductor devices like transistors. Moreover, numerical simulations of these physical processes are performed. In order to accomplish this, methods of theoretical physics, functional analysis, numerical mathematics and computer programming are applied. After an introduction to the status quo of semiconductor device simulation methods and a brief review of historical facts up to now, the attention is shifted to the construction of a model, which serves as the basis of the subsequent derivations in the thesis. Thereby the starting point is an important equation of the theory of dilute gases. From this equation the model equations are derived and specified by means of a series expansion method. This is done in a multi-stage derivation process, which is mainly taken from a scientific paper and which does not constitute the focus of this thesis. In the following phase we specify the mathematical setting and make precise the model assumptions. Thereby we make use of methods of functional analysis. Since the equations we deal with are coupled, we are concerned with a nonstandard problem. In contrary, the theory of scalar elliptic equations is established meanwhile. Subsequently, we are preoccupied with the numerical discretization of the equations. A special finite-element method is used for the discretization. This special approach has to be done in order to make the numerical results appropriate for practical application. By a series of transformations from the discrete model we derive a system of algebraic equations that are eligible for numerical evaluation. Using self-made computer programs we solve the equations to get approximate solutions. These programs are based on new and specialized iteration procedures that are developed and thoroughly tested within the frame of this research work. Due to their importance and their novel status, they are explained and demonstrated in detail. We compare these new iterations with a standard method that is complemented by a feature to fit in the current context. A further innovation is the computation of solutions in three-dimensional domains, which are still rare. Special attention is paid to applicability of the 3D simulation tools. The programs are designed to have justifiable working complexity. The simulation results of some models of contemporary semiconductor devices are shown and detailed comments on the results are given. Eventually, we make a prospect on future development and enhancements of the models and of the algorithms that we used.

Numerical methods for the dispersion analysis of Guided Waves

The use of guided ultrasonic waves (GUW) has increased considerably in the fields of non-destructive (NDE) testing and structural health monitoring (SHM) due to their ability to perform long range inspections, to probe hidden areas as well as to provide a complete monitoring of the entire waveguide. Guided waves can be fully exploited only once their dispersive properties are known for the given waveguide. In this context, well stated analytical and numerical methods are represented by the Matrix family methods and the Semi Analytical Finite Element (SAFE) methods. However, while the former are limited to simple geometries of finite or infinite extent, the latter can model arbitrary cross-section waveguides of finite domain only. This thesis is aimed at developing three different numerical methods for modelling wave propagation in complex translational invariant systems. First, a classical SAFE formulation for viscoelastic waveguides is extended to account for a three dimensional translational invariant static prestress state. The effect of prestress, residual stress and applied loads on the dispersion properties of the guided waves is shown. Next, a two-and-a-half Boundary Element Method (2.5D BEM) for the dispersion analysis of damped guided waves in waveguides and cavities of arbitrary cross-section is proposed. The attenuation dispersive spectrum due to material damping and geometrical spreading of cavities with arbitrary shape is shown for the first time. Finally, a coupled SAFE-2.5D BEM framework is developed to study the dispersion characteristics of waves in viscoelastic waveguides of arbitrary geometry embedded in infinite solid or liquid media. Dispersion of leaky and non-leaky guided waves in terms of speed and attenuation, as well as the radiated wavefields, can be computed. The results obtained in this thesis can be helpful for the design of both actuation and sensing systems in practical application, as well as to tune experimental setup.

Spectral theory of differential operators on finite metric graphs and on bounded domains

Die vorliegende Arbeit widmet sich der Spektraltheorie von Differentialoperatoren auf metrischen Graphen und von indefiniten Differentialoperatoren auf beschränkten Gebieten. Sie besteht aus zwei Teilen. Im Ersten werden endliche, nicht notwendigerweise kompakte, metrische Graphen und die Hilberträume von quadratintegrierbaren Funktionen auf diesen betrachtet. Alle quasi-m-akkretiven Laplaceoperatoren auf solchen Graphen werden charakterisiert, und Abschätzungen an die negativen Eigenwerte selbstadjungierter Laplaceoperatoren werden hergeleitet. Weiterhin wird die Wohlgestelltheit eines gemischten Diffusions- und Transportproblems auf kompakten Graphen durch die Anwendung von Halbgruppenmethoden untersucht. Eine Verallgemeinerung des indefiniten Operators $-tfrac{d}{dx}sgn(x)tfrac{d}{dx}$ von Intervallen auf metrische Graphen wird eingeführt. Die Spektral- und Streutheorie der selbstadjungierten Realisierungen wird detailliert besprochen. Im zweiten Teil der Arbeit werden Operatoren untersucht, die mit indefiniten Formen der Art $langlegrad v, A(cdot)grad urangle$ mit $u,vin H_0^1(Omega)subset L^2(Omega)$ und $OmegasubsetR^d$ beschränkt, assoziiert sind. Das Eigenwertverhalten entspricht in Dimension $d=1$ einer verallgemeinerten Weylschen Asymptotik und für $dgeq 2$ werden Abschätzungen an die Eigenwerte bewiesen. Die Frage, wann indefinite Formmethoden für Dimensionen $dgeq 2$ anwendbar sind, bleibt offen und wird diskutiert.

Exact quantum Monte Carlo methods for correlated electron systems

Thema dieser Arbeit ist die Entwicklung und Kombination verschiedener numerischer Methoden, sowie deren Anwendung auf Probleme stark korrelierter Elektronensysteme. Solche Materialien zeigen viele interessante physikalische Eigenschaften, wie z.B. Supraleitung und magnetische Ordnung und spielen eine bedeutende Rolle in technischen Anwendungen. Es werden zwei verschiedene Modelle behandelt: das Hubbard-Modell und das Kondo-Gitter-Modell (KLM). In den letzten Jahrzehnten konnten bereits viele Erkenntnisse durch die numerische Lösung dieser Modelle gewonnen werden. Dennoch bleibt der physikalische Ursprung vieler Effekte verborgen. Grund dafür ist die Beschränkung aktueller Methoden auf bestimmte Parameterbereiche. Eine der stärksten Einschränkungen ist das Fehlen effizienter Algorithmen für tiefe Temperaturen.rnrnBasierend auf dem Blankenbecler-Scalapino-Sugar Quanten-Monte-Carlo (BSS-QMC) Algorithmus präsentieren wir eine numerisch exakte Methode, die das Hubbard-Modell und das KLM effizient bei sehr tiefen Temperaturen löst. Diese Methode wird auf den Mott-Übergang im zweidimensionalen Hubbard-Modell angewendet. Im Gegensatz zu früheren Studien können wir einen Mott-Übergang bei endlichen Temperaturen und endlichen Wechselwirkungen klar ausschließen.rnrnAuf der Basis dieses exakten BSS-QMC Algorithmus, haben wir einen Störstellenlöser für die dynamische Molekularfeld Theorie (DMFT) sowie ihre Cluster Erweiterungen (CDMFT) entwickelt. Die DMFT ist die vorherrschende Theorie stark korrelierter Systeme, bei denen übliche Bandstrukturrechnungen versagen. Eine Hauptlimitation ist dabei die Verfügbarkeit effizienter Störstellenlöser für das intrinsische Quantenproblem. Der in dieser Arbeit entwickelte Algorithmus hat das gleiche überlegene Skalierungsverhalten mit der inversen Temperatur wie BSS-QMC. Wir untersuchen den Mott-Übergang im Rahmen der DMFT und analysieren den Einfluss von systematischen Fehlern auf diesen Übergang.rnrnEin weiteres prominentes Thema ist die Vernachlässigung von nicht-lokalen Wechselwirkungen in der DMFT. Hierzu kombinieren wir direkte BSS-QMC Gitterrechnungen mit CDMFT für das halb gefüllte zweidimensionale anisotrope Hubbard Modell, das dotierte Hubbard Modell und das KLM. Die Ergebnisse für die verschiedenen Modelle unterscheiden sich stark: während nicht-lokale Korrelationen eine wichtige Rolle im zweidimensionalen (anisotropen) Modell spielen, ist in der paramagnetischen Phase die Impulsabhängigkeit der Selbstenergie für stark dotierte Systeme und für das KLM deutlich schwächer. Eine bemerkenswerte Erkenntnis ist, dass die Selbstenergie sich durch die nicht-wechselwirkende Dispersion parametrisieren lässt. Die spezielle Struktur der Selbstenergie im Impulsraum kann sehr nützlich für die Klassifizierung von elektronischen Korrelationseffekten sein und öffnet den Weg für die Entwicklung neuer Schemata über die Grenzen der DMFT hinaus.

Influence of Smoothing on Voxel-Based Mesh Accuracy in Micro-Finite Element

The interest in automatic volume meshing for finite element analysis (FEA) has grown more since the appearance of microfocus CT (μCT), due to its high resolution, which allows for the assessment of mechanical behaviour at a high precision. Nevertheless, the basic meshing approach of generating one hexahedron per voxel produces jagged edges. To prevent this effect, smoothing algorithms have been introduced to enhance the topology of the mesh. However, whether smoothing also improves the accuracy of voxel-based meshes in clinical applications is still under question. There is a trade-off between smoothing and quality of elements in the mesh. Distorted elements may be produced by excessive smoothing and reduce accuracy of the mesh. In the present work, influence of smoothing on the accuracy of voxel-based meshes in micro-FE was assessed. An accurate 3D model of a trabecular structure with known apparent mechanical properties was used as a reference model. Virtual CT scans of this reference model (with resolutions of 16, 32 and 64 μm) were then created and used to build voxel-based meshes of the microarchitecture. Effects of smoothing on the apparent mechanical properties of the voxel-based meshes as compared to the reference model were evaluated. Apparent Young’s moduli of the smooth voxel-based mesh were significantly closer to those of the reference model for the 16 and 32 μm resolutions. Improvements were not significant for the 64 μm, due to loss of trabecular connectivity in the model. This study shows that smoothing offers a real benefit to voxel-based meshes used in micro-FE. It might also broaden voxel-based meshing to other biomechanical domains where it was not used previously due to lack of accuracy. As an example, this work will be used in the framework of the European project ContraCancrum, which aims at providing a patient-specific simulation of tumour development in brain and lungs for oncologists. For this type of clinical application, such a fast, automatic, and accurate generation of the mesh is of great benefit.

Post-mortem virtual estimation of free abdominal blood volume

PURPOSE: The purpose of this retrospective study was to examine the reliability of virtually estimated abdominal blood volume using segmentation from postmortem computed tomography (PMCT) data. MATERIALS AND METHODS: Twenty-one cases with free abdominal blood were investigated by PMCT and autopsy. The volume of the blood was estimated using a manual segmentation technique (Amira, Visage Imaging, Germany) and the results were compared to autopsy data. Six of 21 cases had undergone additional post-mortem computed tomographic angiography (PMCTA). RESULTS: The virtually estimated abdominal blood volumes did not differ significantly from those measured at autopsy. Additional PMCTA did not bias data significantly. CONCLUSION: Virtual estimation of abdominal blood volume is a reliable technique. The virtual blood volume estimation is a useful tool to deliver additional information in cases where autopsy is not performed or in cases where a postmortem angiography is performed.

Compression hosiery for occupational leg symptoms and leg volume: a randomized crossover trial in a cohort of hairdressers

OBJECTIVE: Occupational leg symptoms are highly prevalent in the general population and impair the psychic state of health. We investigated hairdressers, a cohort exposed to prolonged standing during work, in a randomized crossover trial. We hypothesized that hairdressers wearing low-strength compression hosiery would benefit from less leg volume increase and discomfort. METHODS: One hundred and eight hairdressers were randomized to wear medical compression stockings (MCS; 15-20 mmHg) in a crossover study. The effect of MCS on symptoms and on lower leg volume was compared with no compression treatment. Symptoms were assessed with a comprehensive questionnaire, categorized using factor analysis with varimax rotation and correlated with leg volume changes. RESULTS: Wearing MCS reduced the symptom score for pain and feelings of swelling (range 0-4) by an average of 0.22 (12%, P < 0.001). Sleep disturbance, feeling of unattractive legs and depressiveness improved with MCS compared with no MCS. Subjects initially obliged to refrain from wearing stockings showed a significant decrease of pain and feelings of swelling as well (by 0.10 [6%], P = 0.015). Wearing MCS was associated with a decrease of lower leg volume by an average of 19 mL (P < 0.001), with preference in older hairdressers (P < 0.001). The effects of wearing MCS on symptoms and on leg volume were not correlated with each other. CONCLUSIONS: Individuals working in a standing profession experience leg pain, feelings of swelling, heaviness and various other disturbing feelings. These symptoms can be alleviated by wearing low-strength MCS.

Chapter II: Diagnostic methods

Non-invasive vascular studies can provide crucial information on the presence, location, and severity of critical limb ischaemia (CLI), as well as the initial assessment or treatment planning. Ankle-brachial index with Doppler ultrasound, despite limitations in diabetic and end-stage renal failure patients, is the first-line evaluation of CLI. In this group of patients, toe-brachial index measurement may better establish the diagnosis. Other non-invasive measurements, such as segmental limb pressure, continuous-wave Doppler analysis and pulse volume recording, are of limited accuracy. Transcutaneous oxygen pressure (TcPO(2)) measurement may be of value when rest pain and ulcerations of the foot are present. Duplex ultrasound is the most important non-invasive tool in CLI patients combining haemodynamic evaluation with imaging modality. Computed tomography angiography (CTA) and magnetic resonance angiography (MRA) are the next imaging studies in the algorithm for CLI. Both CTA and MRA have been proven effective in aiding the decision-making of clinicians and accurate planning of intervention. The data acquired with CTA and MRA can be manipulated in a multiplanar and 3D fashion and can offer exquisite detail. CTA results are generally equivalent to MRA, and both compare favourably with contrast angiography. The individual use of different imaging modalities depends on local availability, experience, and costs. Contrast angiography represents the gold standard, provides detailed information about arterial anatomy, and is recommended when revascularisation is needed.

Finite element analysis of aortic root dilation: a new procedure to reproduce pathology based on experimental data

Sinotubular junction dilation is one of the most frequent pathologies associated with aortic root incompetence. Hence, we create a finite element model considering the whole root geometry; then, starting from healthy valve models and referring to measures of pathological valves reported in the literature, we reproduce the pathology of the aortic root by imposing appropriate boundary conditions. After evaluating the virtual pathological process, we are able to correlate dimensions of non-functional valves with dimensions of competent valves. Such a relation could be helpful in recreating a competent aortic root and, in particular, it could provide useful information in advance in aortic valve sparing surgery.

Development of an ultra mini-oxygenator for use in low-volume, buffer-perfused preparations

Introduction: Small animal models are widely used in basic research. However, experimental systems requiring extracorporeal circuits are frequently confronted with limitations related to equipment size. This is particularly true for oxygenators in systems with limited volumes. Thus we aimed to develop and validate an ultra mini-oxygenator for low-volume, buffer-perfused systems. Methods: We have manufactured a series of ultra mini-oxygenators with approximately 175 aligned, microporous, polypropylene hollow fibers contained inside a shell, which is sealed at each of the two extremities to isolate perfusate and gas compartments. With this construction, gas passes through hollow fibers, while perfusate circulates around fibers. Performance of ultra mini-oxygenators (oxygen partial pressure (PO2 ), gas and perfusate flow, perfusate pressure and temperature drop) were assessed with modified Krebs-Henseleit buffer in an in vitro perfusion circuit and an ex vivo rat heart preparation. Results: Mean priming volume of ultra mini-oxygenators was 1.2±0.5 mL and, on average, 86±6% of fibers were open (n=17). In vitro, effective oxygenation (PO2=400-500 mmHg) was achieved for all flow rates up to 50 mL/min and remained stable for at least 2 hours (n=5). Oxygenation was also effective and stable (PO2=456±40 mmHg) in the isolated heart preparation for at least 60 minutes ("venous" PO2=151±11 mmHg; n=5). Conclusions: We have established a reproducible procedure for fabrication of ultra mini-oxygenators, which provide reliable and stable oxygenation for at least 60-120 min. These oxygenators are especially attractive for pre-clinical protocols using small, rather than large, animals.

CT based volume measurement and estimation in cases of pericardial effusion

The measurement of fluid volumes in cases of pericardial effusion is a necessary procedure during autopsy. With the increased use of virtual autopsy methods in forensics, the need for a quick volume measurement method on computed tomography (CT) data arises, especially since methods such as CT angiography can potentially alter the fluid content in the pericardium. We retrospectively selected 15 cases with hemopericardium, which underwent post-mortem imaging and autopsy. Based on CT data, the pericardial blood volume was estimated using segmentation techniques and downsampling of CT datasets. Additionally, a variety of measures (distances, areas and 3D approximations of the effusion) were examined to find a quick and easy way of estimating the effusion volume. Segmentation of CT images as shown in the present study is a feasible method to measure the pericardial fluid amount accurately. Downsampling of a dataset significantly increases the speed of segmentation without losing too much accuracy. Some of the other methods examined might be used to quickly estimate the severity of the effusion volumes.