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.

Estimating persistent Betti numbers for discrete shape analysis

Persistent Topology is an innovative way of matching topology and geometry, and it proves to be an effective mathematical tool in shape analysis. In order to express its full potential for applications, it has to interface with the typical environment of Computer Science: It must be possible to deal with a finite sampling of the object of interest, and with combinatorial representations of it. Following that idea, the main result claims that it is possible to construct a relation between the persistent Betti numbers (PBNs; also called rank invariant) of a compact, Riemannian submanifold X of R^m and the ones of an approximation U of X itself, where U is generated by a ball covering centered in the points of the sampling. Moreover we can state a further result in which, this time, we relate X with a finite simplicial complex S generated, thanks to a particular construction, by the sampling points. To be more precise, strict inequalities hold only in "blind strips'', i.e narrow areas around the discontinuity sets of the PBNs of U (or S). Out of the blind strips, the values of the PBNs of the original object, of the ball covering of it, and of the simplicial complex coincide, respectively.

Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Gleichmäßig dünne Basen zweiter Ordnung

Eine Menge B nicht negativer ganzer Zahlen heißt Basis h-ter Ordnung, wenn jede nicht negative ganze Zahl Summe von höchstens h Elementen von B ist. Eine der großen Fragen der additiven Zahlentheorie ist die nach der effektivsten Basis h-ter Ordnung für ein gegebenes h>=2. Im Fokus des Interesses steht dabei der immer noch offene Fall h=2. Bezeichnet B(x) die Anzahl der Elemente b aus B mit 0= af(x), wobei f die Wurzelfunktion bezeichne. Andererseits gibt es Basen B zweiter Ordnung mit B(x) <= cf(x). Daher kann man den Limes superior S(B), den Limes inferior s(B) sowie im Falle der Existenz den Limes d(B) des Quotienten B(x) / f(x) als Dichtefunktionen von Basen zweiter Ordnung betrachten. J. W. S. Cassels konstruierte 1957 eine Basis C zweiter Ordnung mit d(C)=5,196…. G. Hofmeister gab 2001 eine Basis H zweiter Ordnung mit asymptotischer Wurzeldichte d(H)=4,638… an. In der vorliegenden Arbeit wird eine Basis S zweiter Ordnung mit asymptotischer Wurzeldichte d(S)=3,464… konstruiert. Darüber hinaus wird für die von J. W. S. Cassels, für die von G. Hofmeister und für die in dieser Arbeit verwendete Klasse von Basen zweiter Ordnung gezeigt, dass die asymptotische Wurzeldichte innerhalb der jeweiligen Klasse nicht mehr zu verbessern ist. Bisher war die Frage nach möglichen Verbesserungen innerhalb der jeweiligen Konstruktionsprinzipien offen geblieben.

Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

The cutting stock problem in the wood industry

This thesis proposes a solution for board cutting in the wood industry with the aim of usage minimization and machine productivity. The problem is dealt with as a Two-Dimensional Cutting Stock Problem and specific Combinatorial Optimization methods are used to solve it considering the features of the real problem.

Selektiv deblockierbare 2,6-Diamino-2,6-didesoxy-D-glucose-Scaffolds für die kombinatorische Synthese potentieller RNA-Liganden

Aminoglydosid-Antibiotika wie Neomycin B oder Cyclopeptid-Antibiotike wie Viaomycin sind dafür bekannt, daß sie selektiv an RNA binden können. Diese Interaktionen beruhen sowohl auf elektrostatischen Wechselwirkungen als auch auf H-Brücken-Bindungen. Des weiteren ist die definierte räumliche Anordnung von Donor- und Akzeptor-Resten in den Strukturen der RNA-Liganden wichtig für die Affinität. Eine Möglichkeit natürliche RNA-Liganden zu imitieren ist der Einsatz polyfunktioneller Template wie zum Beispiel das 2,6-Diamino-2,6-didesoxy-D-glucose-Scaffold. Mit Hilfe dieser Scaffolds können dann verschiedene positv geladene Reste und Donatoren sowie Akzeptoren für H-Brücken-Bindungen oder auch Interkalatoren räumlich definiert präsentiert werden. Für die unabhängige Funktionalisierung einer jeden Position ist ein Satz orthogonal stabiler Schutzgruppen nötig, wobei eine Hydroxylguppe durch einen Anker ersetzt wird, der eine Anbindung des Scaffolds an einen polymeren Träger ermöglicht. Das neu entwickelte 2,6-Diamino-2,6-didesoxy-D-glucose-Scaffold ist das erste Monosaccharid-Templat, das in allen fünf Positionen mit orthogonal stabilen Schutzgruppen blockiert ist. Alle Positionen könne in beliebiger Reihenfolge selektiv deblockiert und anschließend derivatisiert werden. Das Scaffold kann mit Aminosäuren, Guanidinen oder Interkalatoren umgesetzt werden, um so natürlich vorkommende RNA-bindende Aminoglycoside oder Peptide zu imitieren. Aufbauend auf diesem Monosaccharid-Templat wurde eine Bibliothek von über 100 potentiellen RNA-Liganden synthetisiert, die im Rahmen des Sonderforschungsbereichs 579 (RNA-Liganden-Wechselwirkungen) in Zellassays auf ihre Fähigkeit zur Hemmung der Tat/TAR-Wechselwirkung untersucht wurden, wobei bis jetzt 9 Verbindungen mit einer hemmenden Wirkung im micromolaren Bereich gefunden wurden.

Determination of the gluon polarisation from open charm production at COMPASS

One of the main goals of the COMPASS experiment at CERN is the determination of the gluon polarisation in the nucleon. It is determined from spin asymmetries in the scattering of 160 GeV/c polarised muons on a polarised LiD target. The gluon polarisation is accessed by the selection of photon-gluon fusion (PGF) events. The PGF-process can be tagged through hadrons with high transverse momenta or through charmed hadrons in the final state. The advantage of the open charm channel is that, in leading order, the PGF-process is the only process for charm production, thus no physical background contributes to the selected data sample. This thesis presents a measurement of the gluon polarisation from the COMPASS data taken in the years 2002-2004. In the analysis, charm production is tagged through a reconstructed D0-meson decaying in $D^{0}-> K^{-}pi^{+}$ (and charge conjugates). The reconstruction is done on a combinatorial basis. The background of wrong track pairs is reduced using kinematic cuts to the reconstructed D0-candidate and the information on particle identification from the Ring Imaging Cerenkov counter. In addition, the event sample is separated into D0-candidates, where a soft pion from the decay of the D*-meson to a D0-meson, is found, and the D0-candidates without this tag. Due to the small mass difference between D*-meson and D0-meson the signal purity of the D*-tagged sample is about 7 times higher than in the untagged sample. The gluon polarisation is measured from the event asymmetries for the for the different spin configurations of the COMPASS target. To improve the statistical precision of the final results, the events in the final sample are weighted. This method results in an average value of the gluon polarisation in the x-range covered by the data. For the COMPASS data from 2002-2004, the resulting value of the gluon polarisation is $=-0.47+-0.44 (stat)+-0.15(syst.)$. The result is statistically compatible with the existing measurements of $$ in the high-pT channel. Compared to these, the open charm measurement has the advantage of a considerably smaller model dependence.

Mathematical aspects of Feynman integrals

In the present dissertation we consider Feynman integrals in the framework of dimensional regularization. As all such integrals can be expressed in terms of scalar integrals, we focus on this latter kind of integrals in their Feynman parametric representation and study their mathematical properties, partially applying graph theory, algebraic geometry and number theory. The three main topics are the graph theoretic properties of the Symanzik polynomials, the termination of the sector decomposition algorithm of Binoth and Heinrich and the arithmetic nature of the Laurent coefficients of Feynman integrals.rnrnThe integrand of an arbitrary dimensionally regularised, scalar Feynman integral can be expressed in terms of the two well-known Symanzik polynomials. We give a detailed review on the graph theoretic properties of these polynomials. Due to the matrix-tree-theorem the first of these polynomials can be constructed from the determinant of a minor of the generic Laplacian matrix of a graph. By use of a generalization of this theorem, the all-minors-matrix-tree theorem, we derive a new relation which furthermore relates the second Symanzik polynomial to the Laplacian matrix of a graph.rnrnStarting from the Feynman parametric parameterization, the sector decomposition algorithm of Binoth and Heinrich serves for the numerical evaluation of the Laurent coefficients of an arbitrary Feynman integral in the Euclidean momentum region. This widely used algorithm contains an iterated step, consisting of an appropriate decomposition of the domain of integration and the deformation of the resulting pieces. This procedure leads to a disentanglement of the overlapping singularities of the integral. By giving a counter-example we exhibit the problem, that this iterative step of the algorithm does not terminate for every possible case. We solve this problem by presenting an appropriate extension of the algorithm, which is guaranteed to terminate. This is achieved by mapping the iterative step to an abstract combinatorial problem, known as Hironaka's polyhedra game. We present a publicly available implementation of the improved algorithm. Furthermore we explain the relationship of the sector decomposition method with the resolution of singularities of a variety, given by a sequence of blow-ups, in algebraic geometry.rnrnMotivated by the connection between Feynman integrals and topics of algebraic geometry we consider the set of periods as defined by Kontsevich and Zagier. This special set of numbers contains the set of multiple zeta values and certain values of polylogarithms, which in turn are known to be present in results for Laurent coefficients of certain dimensionally regularized Feynman integrals. By use of the extended sector decomposition algorithm we prove a theorem which implies, that the Laurent coefficients of an arbitrary Feynman integral are periods if the masses and kinematical invariants take values in the Euclidean momentum region. The statement is formulated for an even more general class of integrals, allowing for an arbitrary number of polynomials in the integrand.

Funktionelle Analyse der Gliazellwanderung im Drosophila-Embryo

Gliazellen kommen in allen höheren Organismen vor und sind sowohl für die korrekte Entwicklung, als auch für die Funktionalität des adulten Nervensystems unerlässlich. Eine der mannigfachen Funktionen dieses Zelltyps ist die Umhüllung von Axonen im zentralen und peripheren Nervensystem (ZNS und PNS). Um eine vollständige Umhüllung zu gewährleisten, wandern Gliazellen während der Neurogenese zum Teil über enorme Distanzen von ihrem Entstehungsort aus. Dies trifft insbesondere auf die Gliazellen zu, durch deren Membranausläufer die distalen Axonbereiche der peripheren Nerven isoliert werden.rnIn dieser Arbeit wurde die Migration von Gliazellen anhand des Modelorganismus Drosophila untersucht. Ein besonderes Interesse galt dabei der Wanderung einer distinkten Population von Gliazellen, den sogenannten embryonalen Peripheren Gliazellen (ePG). Die ePGs werden überwiegend im sich entwickelnden ventralen Bauchmark geboren und wandern anschließend entlang der peripheren Nerventrakte nach dorsal aus, um diese bis zum Ende der Embryogenese zu umhüllen und dadurch die gliale Blut-Nerv-Schranke zu etablieren. Das Hauptziel dieser Arbeit bestand darin, neue Faktoren bzw. Mechanismen aufzudecken, durch welche die Migration der ePGs reguliert wird. Dazu wurde zunächst der wildtypische Verlauf ihrer Wanderung detailliert analysiert. Es stellte sich heraus, dass in jedem abdominalen Hemisegment eine invariante Anzahl von 12 ePGs von distinkten neuralen Vorläuferzellen generiert wird, die individuelle Identitäten besitzen und mittels molekularer Marker auf Einzelzellebene identifiziert werden können. Basierend auf der charakteristischen Lage der Zellen erfolgte die Etablierung einer neuen, konsistenten Nomenklatur für sämtliche ePGs. Darüber hinaus offenbarten in vivo Migrationsanalysen, dass die Wanderung individueller ePGs stereotyp verläuft und demzufolge weitestgehend prädeterminiert ist. Die genaue Kenntnis der wildtypischen ePG Migration auf Einzelzellebene diente anschließend als Grundlage für detaillierte Mutantenanalysen. Anhand derer konnte für den ebenfalls als molekularen Marker verwendeten Transkriptionsfaktor Castor eine Funktion als zellspezifische Determinante für die korrekte Spezifizierung der ePG6 und ePG8 nachgewiesen werden, dessen Verlust in einem signifikanten Migrationsdefekt dieser beiden ePGs resultiert. Des Weiteren konnte mit Netrin (NetB) der erste diffusible und richtungsweisende Faktor für die Migration von ePGs enthüllt werden, der in Interaktion mit dem Rezeptor Uncoordinated5 speziell die Wanderung der ePG6 und ePG8 leitet. Die von den übrigen Gliazellen unabhängige Navigation der ePG6 und ePG8 belegt, dass zumindest die Migration von Gruppen der ePGs durch unterschiedliche Mechanismen kontrolliert wird, was durch die Resultate der durchgeführten Ablationsexperimente bestätigt wird. rnFerner konnte gezeigt werden, dass während der frühen Gliogenese eine zuvor unbekannte, von Neuroblasten bereitgestellte Netrinquelle an der initialen Wegfindung der Longitudinalen Gliazellen (eine Population Neuropil-assoziierter Gliazellen im ZNS) beteiligt ist. In diesem Kontext erfolgt die Signaldetektion bereits in deren Vorläuferzelle, dem Longitudinalen Glioblasten, zellautonom über den Rezeptor Frazzled. rnFür künftige Mutantenscreens zur Identifizierung weiterer an der Migration der ePGs beteiligter Faktoren stellt die in dieser Arbeit präsentierte detaillierte Beschreibung eine wichtige Grundlage dar. Speziell in Kombination mit den vorgestellten molekularen Markern liefert sie die Voraussetzung dafür, individuelle ePGs auch im mutanten Hintergrund zu erfassen, wodurch selbst subtile Phänotypen überhaupt erst detektiert und auf Einzelzellebene analysiert werden können. Aufgrund der aufgezeigten voneinander unabhängigen Wegfindung, erscheinen Mutantenanalysen ohne derartige Möglichkeiten wenig erfolgversprechend, da Mutationen vermutlich mehrheitlich die Migration einzelner oder weniger ePGs beeinträchtigen. Letzten Endes wird somit die Aussicht verbessert, weitere neuartige Migrationsfaktoren im Modellorganismus Drosophila zu entschlüsseln, die gegebenenfalls bis hin zu höheren Organismen konserviert sind und folglich zum Verständnis der Gliazellwanderung in Vertebraten beitragen.

Bioinformatische Identifizierung und Charakterisierung von Zyklin-abhängigen Kinasen und Zyklinen des Parasiten Eimeria tenella und deren Nutzung im rationalen Wirkstoffdesign

Parasiten der Apicomplexa umfassen sowohl humanpathogene, als auch tierpathogene Protozoen. Beispiele für wichtige Vertreter human- und tierpathogener Parasiten sind Plasmodium falciparum und Eimeria tenella. E. tenella verursacht die Kokzidiose des Hühnchens, eine Darmerkrankung die weltweit für Verluste in einer geschätzten Höhe von bis zu 3 Milliarden US$ verantwortlich zeichnet. Eine prophylaktische Vakzinierung gegen diese Krankheit ist ökonomisch meist ineffizient, und eine Behandlung mit Kokzidiostatika wird durch häufige Resistenzbildung gegen bekannte Wirkstoffe erschwert. Diese Situation erfordert die Entwicklung neuer kostengünstiger Alternativen. Geeignete Zielproteine für die Entwicklung neuartiger Arzneistoffe zur Behandlung der Kokzidiose sind die Zyklin-abhängigen Kinasen (CDKs), zu denen auch die CDK-related Kinase 2 (EtCRK2) aus E. tenella gehört. Diese Proteine sind maßgeblich an der Regulation des Zellzyklus beteiligt. Durch chemische Validierung mit dem CDK Inhibitor Flavopiridol konnte nachgewiesen werden, dass ein Funktionsverlust von CDKs in E. tenella die Vermehrung des Parasiten in Zellkultur inhibiert. E. tenella CDKs sind daher als Zielproteine für die Entwicklung einer Chemotherapie der Kokzidiose geeignet. Mittels bioinformatischer Tiefenanalysen sollten CDK Proteine im Parasiten E. tenella identifiziert werden. Das Genom von E. tenella liegt in Rohfassung vor [ftp://ftp.sanger.ac.uk]. Jedoch waren zum Zeitpunkt dieser Arbeiten viele Sequenzen des Genoms noch nicht annotiert. Homologe CDK Proteine von E. tenella konnten durch den Vergleich von Sequenzinformationen mit anderen Organismen der Apicomplexa identifiziert und analysiert werden. Durch diese Analysen konnten neben der bereits bekannten EtCRK2, drei weitere, bislang nicht annotierte CDKs in E. tenella identifiziert werden (EtCRK1, EtCRK3 sowie EtMRK). Darüber hinaus wurde eine Analyse der entsprechenden Zykline – der Aktivatoren der CDKs – bezüglich Funktion und Struktur, sowie eine Datenbanksuche nach bisher nicht beschriebenen Zyklinen in E. tenella durchgeführt. Diese Suchen ergaben vier neue potentielle Zykline für E. tenella, wovon EtCYC3a als Aktivator der EtCRK2 von María L. Suárez Fernández (Intervet Innovation GmbH, Schwabenheim) bestätigt werden konnte. Sequenzvergleiche lassen vermuten, dass auch EtCYC1 und EtCYC3b in der Lage sind, EtCRK2 zu aktivieren. Außerdem ist anzunehmen, dass EtCYC4 als Aktivator der EtCRK1 fungiert. Ein weiterer Schwerpunkt der vorliegenden Arbeit war die Suche und Optimierung nach neuen Inhibitoren von CDKs aus E. tenella. In vorangegangenen Arbeiten konnten bereits Inhibitoren der EtCRK2 gefunden werden [BEYER, 2007]. Mittels Substruktur- und Ähnlichkeitssuchen konnten im Rahmen dieser Arbeit weitere Inhibitoren der EtCRK2 identifiziert werden. Vier dieser Strukturklassen erfüllen die Kriterien einer Leitstruktur. Eine dieser Leitstrukturen gehört zur Strukturklasse der Benzimidazol-Carbonitrile und ist bislang nicht als Inhibitor anderer Kinasen beschrieben. Diese neu identifizierte Leitstruktur konnte in silico weiter optimiert werden. Im Rahmen dieser Arbeit wurden Bindungsenergien von Vertretern dieser Strukturklasse berechnet, um einen wahrscheinlichen Bindemodus vorherzusagen. Für die weiterführende in silico Optimierung wurde eine virtuelle kombinatorische Substanzbibliothek dieser Klasse erstellt. Die Auswahl geeigneter Verbindungen für eine chemische Synthese erfolgte durch molekulares Docking unter Nutzung von Homologiemodellen der EtCRK2. Darüber hinaus wurde ein in silico Screening nach potentiellen Inhibitoren der PfMRK und EtMRK durchgeführt. Dabei konnten weitere interessante virtuelle Hit-Strukturen aus einer Substanzdatenbank kommerziell erhältlicher Verbindungen gefunden werden. Durch dieses virtuelle Screening konnten jeweils sieben Verbindungen als virtuelle Hits der PfMRK sowie der EtMRK identifiziert werden. Die Häufung von Strukturklassen mit bekannter CDK Aktivität deutet darauf hin, dass während des virtuellen Screenings eine Anreicherung von CDK Inhibitoren stattgefunden hat. Diese Ergebnisse lassen auf eine Weiterentwicklung neuer Wirkstoffe gegen Kokzidiose und Malaria hoffen.

Operational research applied to regional healthcare system

In this thesis we focus on optimization and simulation techniques applied to solve strategic, tactical and operational problems rising in the healthcare sector. At first we present three applications to Emilia-Romagna Public Health System (SSR) developed in collaboration with Agenzia Sanitaria e Sociale dell'Emilia-Romagna (ASSR), a regional center for innovation and improvement in health. Agenzia launched a strategic campaign aimed at introducing Operations Research techniques as decision making tools to support technological and organizational innovations. The three applications focus on forecast and fund allocation of medical specialty positions, breast screening program extension and operating theater planning. The case studies exploit the potential of combinatorial optimization, discrete event simulation and system dynamics techniques to solve resource constrained problem arising within Emilia-Romagna territory. We then present an application in collaboration with Dipartimento di Epidemiologia del Lazio that focuses on population demand of service allocation to regional emergency departments. Finally, a simulation-optimization approach, developed in collaboration with INESC TECH center of Porto, to evaluate matching policies for the kidney exchange problem is discussed.

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.

Problem-specific design of metaheuristics for constrained spanning tree problems

When designing metaheuristic optimization methods, there is a trade-off between application range and effectiveness. For large real-world instances of combinatorial optimization problems out-of-the-box metaheuristics often fail, and optimization methods need to be adapted to the problem at hand. Knowledge about the structure of high-quality solutions can be exploited by introducing a so called bias into one of the components of the metaheuristic used. These problem-specific adaptations allow to increase search performance. This thesis analyzes the characteristics of high-quality solutions for three constrained spanning tree problems: the optimal communication spanning tree problem, the quadratic minimum spanning tree problem and the bounded diameter minimum spanning tree problem. Several relevant tree properties, that should be explored when analyzing a constrained spanning tree problem, are identified. Based on the gained insights on the structure of high-quality solutions, efficient and robust solution approaches are designed for each of the three problems. Experimental studies analyze the performance of the developed approaches compared to the current state-of-the-art.

Segmentale Musterbildung in der terminalen Abdominalregion des zentralen Nervensystems von Drosophila melanogaster

In dieser Arbeit wurden Mechanismen der Musterbildung in der terminalen Abdominalregion des Zentralnervensystems von Drosophila melanogaster untersucht. Dazu wurden zunächst die Anzahl der angelegten Neuromere und das Muster der dort lokalisierten neuralen Stammzellen (Neuroblasten) analysiert. Dabei zeigte sich, dass sowohl die Größe der Neuromere, als auch die Anzahl an Neuroblasten von anterior nach posterior sukzessiv abnimmt, wobei keine geschlechtsspezifischen Unterschiede in der Anzahl der vorhandenen Neuroblasten festgestellt werden konnten. Durch die Kombination einer Vielzahl von molekularen Markern war es anschließend möglich, die Identität aller Neuroblasten in diesem Bereich aufzuklären und in einer Karte zusammenzutragen. Sie weisen alle eine serielle Homologie zu Neuroblasten in weiter anterior gelegenen Segmenten auf. Des Weiteren wurde die embryonale Identität der geschlechtsspezifischen Neuroblasten untersucht und deren postembryonalen mänchenspezifischen Zellstammbäume charakterisiert. Diese detaillierten Beschreibungen bildeten die Grundlage für die funktionelle Analyse von geschlechts- und segmentspezifischen Faktoren, die zur Musterbildung in dieser Region des Zentralnervensystems beitragen. So konnte gezeigt werden, dass die weibliche Isoform von doublesex den programmierten Zelltod der geschlechtsspezifischen Neuroblasten induziert, während die männliche Isoform diesen verhindert. Das Hox-Gen Abdominal-B zeigt relativ milde Effekte auf das Überleben dieser Neuroblasten, was darauf hindeutet, dass weitere Faktoren benötigt werden, um diesen Prozess in segmentspezifischer Weise zu kontrollieren. Die Funktion von Hox-Genen wurde ferner im Hinblick auf die abgeleitete Morphologie der terminalen Neuromere untersucht. Es konnte herausgefunden werden, dass die regulatorische Isoform von Abdominal-B auf mehreren Ebenen wirkt: Sie beeinflusst die Zusammensetzung bestimmter Zellstammbäume durch Modifikation von Zelldeterminationsprozessen und durch die Kontrolle des programmierten Zelltods. Außerdem unterdrückt sie die Bildung einer spezifischen Subpopulation von Neuroblasten. Allerdings benötigt Abdominal-B.r die Co-Expression des ParaHox-Gens caudal, um sein gesamtes Potenzial bezüglich der Suppression dieser Neuroblasten zu entfalten. Die vorliegende Arbeit hat somit erste Einblicke in die geschlechtsspezifische und segmentspezifische Spezifizierung der terminalen Abdominalregion des Zentralnervensystems von Drosophila auf Ebene des Neuroektoderms, der daraus hervorgehenden Neuroblasten und deren Tochterzellen gewährt. Die vollständige und detailgetreue Beschreibung des Neuroblasten-Musters und der postembryonalen männchenspezifischen Zellstammbäume hat zudem attraktive Modellsysteme für zukünftige Untersuchungen etabliert, an denen sich weitere Mechanismen der Musterbildung im Zentralnervensystem analysieren lassen.