Entwicklung und Analyse von Lösungsmethoden für die multikrieterielle Operationssaalplanung zur Berechnung einer Pareto-Front

Diese Masterarbeit befasst sich mit der Operationssaalplanung in Krankenhäusern. Dabei muss beachtet werden, dass Patienten nur von Chirurgen der richtigen Fachrichtung behandelt werden, die Öffnungszeiten der OP-Säle eingehalten werden und Zeit für Notfälle eingeplant werden. Dies ist ein NP-schweres Problem. Wir stellen zwei Ansätze vor, um das Problem zu lösen: einmal werden Teillösungen für einzelne Fachrichtungen betrachtet und einmal werden Patienten nach und nach zu verschiedenen Plänen hinzugefügt. Beide Ansätze resultieren in mehrere verschiedene Lösungen.

Modelle und Algorithmen für das Pooling Problem

Das Pooling Problem bezeichnet ein nicht konvexes Optimierungsproblem, bei dem in Flussnetzwerken mit Becken Kosten minimiert, beziehungsweise Gewinne maximiert werden sollen. Dieses Problem tritt insbesondere in der Ölindustrie auf, weshalb sich auch seit seiner ersten Formulierung zahlreiche Wissenschaftler mit dessen Lösung beschäftigt haben. In dieser Arbeit stellen wir das Problem vor, zeigen verschiedene Modelle, gehen auf die Komplexität ein und erörtern einige Lösungsansätze des Standard Pooling Problems mittels linearer Optimierung. Daraufhin führen wir die ALT-Methode zur Lösung des Problems in verschiedenen Formulierung an einigen Beispielen durch und analysieren, ob es sinnvoll ist, trivial berechenbare Starwerte zu verwenden.

Optimale Planung vernetzter Blockheizkraftwerke

Die vorliegende Arbeit behandelt die Bestimmung optimaler Produktionspane von Blockheizkraftwerken (BHKW), die gekoppelt Strom und arme erzeugen. Wir untersuchen zwei Varianten bei denen die einzelnen BHKW untereinander Strom oder armeuber entsprechende Strom- beziehungsweise armenetze austauschen urfen. Wir modellieren das Problem als Lot-Sizing Modell mit konstanten Lager- und Produktionsschranken sowie konstantem Lagerverlust. Wir pasentieren Rechenstudien zu beiden Problemen. Zudem geben wir ein heuristisches Verfahren ur die Variante mit Stromnetz an.

Optimal Cable Routing of Heliostats in Solar Tower Power Plants Using Integer Linear Programming

This thesis is concerned with the optimal cable routing of heliostats in solar tower power plants. Each heliostat in the field is connected to the solar tower via a data and a power cable, thereby providing the heliostat with information and power. The data and power cable optimization are seen as individual optimization problems and are solved independently. The data cable model is initially formulated as a traveling salesman problem. Adding capacity constraints to the model, a further formulation as a capacitated vehicle routing problem is implemented. Two variations of the subtour elimination constraints are implemented and analyzed. Furthermore, for the power cable model, different cable types are considered. At first, the problem is formulated as a capacitated vehicle routing problem using Miller-Tucker-Zemlin constraint formulations. The final model is defined as a distance and capacity constrained vehicle routing problem, taking all constraints of the power cable into account. The data cable model is applied to an existent solar tower power plant, the PS10 in Seville, Spain. Computational results for the data cable optimization are compared to existing layouts obtained by heuristic methods. The power cable model is tested for a small test case.

Crew Scheduling for Mobile GP Practises - Complexity and Exact Solution Approaches

Das Konzept der mobilen Hausarztpraxen dient zur Verbesserung der medizinischen Versorgung in ländlichen Gebieten. In diesem Vortrag wird das Problem der Schichtplanung für mobile Praxen vorgestellt. Weiter werden verschiedene Ansätze zur Modellierung des Problems diskutiert. Wir definieren daraus entstehende kombinatorische Probleme und untersuchen ihre Komplexität.

Gegenüberstellung von klassischen endlichen Matroiden und Matroiden mit Koeffizienten nach A. Dress

Die Arbeit beschäftigt sich mit einer von Andreas Dress eingeführten Verallgemeinerung der Klasse von Linearen Matroiden, indem sie eine algebraische Struktur, den Fuzzy Ring, einführt, und endliche Matroide als Matrizen über Fuzzy Ringen darstellt. Dieses Konzept, das sich Matroid mit Koeffizienten nennt, wird dazu genutzt, um existierende Beweise aus der klassischen Matroid Theorie zu vereinfachen

Das unfallfreie kantendisjunkte Pickup und Delivery Problem

In diesem Vortrag befassen wir uns mit einer vom kantendisjunkten Wege Problem abgeleiteten Problemstellung. Diese beruht auf dem Spiel „RGB-Express“ des Spiele-Entwicklungsstudios Bad Crane. Über die Kantendisjunktheit hinaus müssen hierbei bestimmte Pickup- und Delivery-Bedingungen erfüllt werden. Wir führen zwei Ganzzahlige Lineare Programme ein, welche die Problemstellung modellieren und vergleichen die Ergebnisse. Abschließend betrachten wir die Komplexität des Problems für bestimmte Graphenklassen und stellen Lösungsansätze vor.

Greedy-Algorithmen für das robuste minimale Spannbaumproblem unter Γ-Szenarien

Das minimale Spannbaumproblem ist aufgrund seiner Anwendung in Telekommunikations- und Transportnetzwerken insbesondere in seiner robusten Formulierung von Bedeutung. In diesem Vortrag beschäftigen wir uns mit drei Greedy-Algorithmen für das robuste minimale Spannbaumproblem unter Γ-Szenarien. Wir zeigen, dass die Güte der Algorithmen von den Eigenschaften der Instanz abhängig ist. Darüber hinaus untersuchen wir den Einfluss von Γ auf die Güte der Lösung. Zum Abschluss diskutieren wir einige Ergebnisse unserer Rechenstudie, in welcher wir die Greedy-Algorithmen mit dem Algorithmus von Bertsimas und Sim für kombinatorische Optimierungsprobleme vergleichen.

Der Kegel der konvexen Funktion mit endlichem Definitionsbereich

In diesem Vortrag geht es um strukturelle Aussagen zum Kegel K(D) der konvexen Funktionen mit endlichem Definitionsbereich D. Dieser Kegel ist polyedrisch und volldimensional im Funktionenraum. Dabei betrachten wir den maximalen Teilraum V(D), der in K(D) enthalten ist, also den Raum der sowohl konvexen als auch konkaven Funktionen. Wir geben eine Klasse von Definitionsbereichen an, für die V(D) ausschließlich aus den affinen Funktionen mit Definitionsbereich D besteht. Außerdem bestimmen wir V(D) exakt, falls D Teilmenge des eindimensionalen oder zweidimensionalen Raums ist. Darüber hinaus betrachten wir den Kegel pK(D):=K(D)/V(D) und suchen nach extremalen Strahlen beziehungsweise nach einem Erzeugendensystem.

Optimierte Terminplanung in Hausarztpraxen

In dieser Arbeit beschäftigen wir uns mit der Terminplanung in Hausarztpraxen. Das Thema nimmt an Popularität stets zu, da die langen Wartezeiten das häufigste Beschwerdethema der Patienten sind. Praxisinhaber wünschen wiederum einen produktiven und effektiven Arbeitsablauf, welcher eine hohe Auslastung des Arztes erfordert. Um eine zufriedenstellende Terminplanung sowohl für Hauärzte als auch für Patienten zu finden, stellen wir ein Mixed-Integer-Program vor, welches die Kapazitätsplanung bezüglich der Arbeitszeit des Arztes unterstützt. Weiterhin führen wir ein Maskenkonzept ein, das Schablonen liefert, die zur Entscheidungsunterstützung in der Terminreservierung dienen. Schließlich testen wir unsere Ergebnisse mithilfe simulationsbasierter Untersuchungen.

Districting Airport Gates for Cleaning respecting Departure Times

Mathematical optimization is of critical importance in our modern, ever more busy world. In this thesis we examine the distribution of cleaning personnel among a number of gates in an airport facility. Finding optimal cleaning plans requires us to combine both districting and scheduling methods into compound integer programming models. On our way to these models, we analyze restrictive cases and less complex problems that allow us to gain additional insight into the structure of the global task. We further explore a heuristic approach and the concept of symmetry breaking to improve the effectiveness of the integer programming models. Lastly, we conduct a computational study to identify the solution quality of the different approaches that we take towards solving this complex problem.

Valid Inequalities for the Γ-Robust Knapsack Polytope

In this talk, we consider the robust knapsack problem with Γ-scenarios. We adapt the well known cover-inequalities from the classical knapsack and discuss different approaches for the corresponding separation problem. Furthermore, we generalize the concept of extended cover-inequalities from the classical case and give a class of previously unknown extensions for the robust problem. Finally, we consider the lifting problem for minimal cover-inequalities, which has not yet been studied for the robust case, and develop a fast algorithm that is based on combinatorial approaches for solving Γ-robust knapsack problems.