Abschlussarbeiten

Laufende Bachelor-, Master-, Diplom- und Zulassungsarbeiten

  • Masterarbeit: The Guaranteed Service Model with Demand Propagation: New Models Based on Flow Networks

    Zusammenfassung: Das Guaranteed Service Model (GSM) modelliert optimale Sicherheitsbestände für mehrstufige Lagernetze über garantierte Service-Zeiten. Für das GSM existieren approximative Modelle aus der Gemischt-Ganzzahligen Linearen Optimierung (MILP). Ein Nachteil dieser Modelle ist, dass sie davon ausgehen, dass die gesamte Nachfrage im Lagernetz unverändert propagiert wird. In einem divergenten Netz kann so z. B. die Nachfrage für jeden Knoten aus den Nachfragen der Endkundenknoten ermittelt werden. Insbesondere sind diese Nachfragen unabhängig von den berechneten Entscheidungen. Im Falle von Outsourcing, Lost Sales oder Substitution in einem Mehrproduktsystem trifft das nicht mehr zu.

    In einem von der DFG geförderten Projekt sollen neuartige Modelle untersucht werden, die auch korrekt sind, wenn die Propagierung der Nachfrage im Netz von den Entscheidungen abhängt. In dieser Masterarbeit soll der Stand der Forschung dargestellt werden. Ferner sollen alternative Modellansätze auf Basis von Flussnetzwerken vorgestellt werden, die im einfachen GSM-Fall logisch äquivalent zum GSM sind, aber leichter um eine korrekte Nachfragepropagierung erweitert werden können. Aus diesen Modellansätzen sollen erste alternative MILPs entwickelt und auf einfachen Beispielen auf logische Korrektheit, Struktur (z. B. Ganzzahligkeitslücke) und Lösbarkeit mit einem Standardlöser getestet werden. Fortgeschrittene Techniken wie Dynamische Spaltengenerierung sollen kurz skizziert und ihre Chancen diskutiert werden.

    Diese Masterarbeit soll gleichzeitig als Forschungsplan für die Bayreuther Graduiertenschule für Mathematik und Naturwissenschaften dienen und daher auf englisch verfasst werden. Relevante Literatur findet sich im Forschungsantrag.

    Abgabe: 31.07.2021

Abgeschlossene Bachelorarbeiten

  • Bachelorarbeit: Das Firefighter-Problem zur Evaluierung von Maßnahmen gegen die Ausbreitung von Viren.

    Zusammenfassung: Die Grundversion des „Firefighter-Problems“ (FFP) sucht nach der „besten Vorgehensweise“, ein Feuer, das sich in einem Graphen über Kanten von Knoten zu Knoten ausbreitet, zu löschen, indem man ein oder mehrere Feuerwehrleute an die Knoten schickt. Ist ein Knoten gelöscht, bleibt das so, und die Ausbreitung des Feuers ist unterbrochen. Was genau „beste Vorgehensweise“ bedeutet, hängt von der genauen Problemstellung ab: Möglichst schneller Stillstand der Ausbreitung, möglichst viele unverbrannte Knoten etc. Je nach genauer Problemstellung ist das Problem effizient lösbar oder NP-schwer. Für die NP-schweren Fälle ist eine Modellierung als Ganzzahliges Lineares Programm (ILP) interessant: Die Untersuchung der Ganzzahligkeitslücke kann Resultate in Bezug auf Approximationsalgorithmen und andere Informationen liefern.

    Aufgabe dieser Bachelorarbeit ist es, die verschiedenen Varianten des FFP vorzustellen, Beispiele für ihre Anwendbarkeit zu entwerfen und die Bedeutung und Ermittlung von Ganzzahligkeitslücken des ILP-Modells zu diskutieren. Darüber hinaus soll eine kritische Betrachtung des FFP in Zusammenhang mit der Bekämpfung der Ausbreitung von Viren vorgenommen werden. Testrechnungen auf eigenen Beispielen auf Basis der ILP-Modellierung mit verschiedenen Optionen (z. B. mit und ohne Feasibility Pump oder Ähnliches) im Lösungsprozess sollen beurteilt werden in Bezug auf Anwendungsfall und Lösungsmethode.

    Abgabe: 31.07.2020

  • Bachelorarbeit: Spieltheorie für Klimaschutz.

    Zusammenfassung: Vernünftiges Verhalten einzelner Nationen in internationalen Verhandlungen zum Thema Klimaschutz ist ein aktuelles Problem. Im Buchbeitrag von Caleiro und Koautoren in der Literatur wird dieses Problem mit Hilfe von Spieltheorie modelliert.

    Aufgabe dieser Bachelorarbeit ist es, die Spieltheorie, die für die Betrachtungen im Artikel gebraucht wird, zu erklären und die Übertragung auf den Anwendungsfall zu diskutieren. Dies soll vorwiegend mit Hilfe von eigenen Beispielen geschehen, die ggf. Stärken und Schwächen der spieltheoretischen Sichtweise aufzeigen.

    Abgabe: 31.01.2020

  • Bachelorarbeit: Ranking Games und Sportspiele.

    Zusammenfassung: In der Spieltheorie wird der Erfolg der Mitspielenden traditionell in Form einer Auszahlung gemessen. Manchmal führt dies zu unerwünschten Effekten, wenn nämlich nur die Platzierung wichtig ist. Soetwas kann man sich im Sport bei großen Wettbewerben gut vorstellen. Um hier eine theoretische Untersuchungsgrundlage zu schaffen, haben Brandt und Koautoren in der Literatur Ranking Games (RG) eingeführt.

    Aufgabe dieser Bachelorarbeit ist es, das Konzept von RG zu erklären, Beispiele aus dem Sport dafür zu betrachten und die Theorie im Sportkontext zu interpretieren. Ferner sollen für ganz konkrete Beipiel-Sport-RGs ganz konkrete Gleichgewichte mit den im Artikel angegebenen Methoden berechnet und interpretiert werden.

    Abgabe: 31.01.2020

  • Bachelorarbeit: Optimierte Tourenplanung für Sicherheitdienste.

    Zusammenfassung: Optimierte Fahrzeugeinsatzplanung (engl: Vehicle Routing Problem (VRP)) wird in verschiedensten Anwendungsfällen benötigt. Beispiele sind Rundtouren eines Handlungsreisenden (das klassische TSP), Pakete einsammeln und ausliefern, Einsatzplanung von Pannenhilfefahrzeugen, Robotereinsatzplanung, Winterdienst, . . .

    Der Anwendungsfall dieser Bachelorarbeit scheint bislang wenig erforscht: Sicherheitsdienste. Die Besonderheit: die berechneten Touren sollten nicht leicht vorhersagbar sein. Häufigere Besuche desselben Ortes sollten möglich sein und zeitlich nicht zu nah aufeinanderfolgen. Eine Möglichkeit: Man berechnet nicht nur einen Routenplan sondern mehrere und wählt kurz vor der Anwendung einen davon zufällig aus. Dafür muss man ein Modell haben, das eine geeignete Menge von Routenplänen generiert.

    Aufgabe dieser Bachelorarbeit ist es, ein Modell auf Basis der Gemischt-Ganzzahligen Linearen Optimierung (MILP) für eine VRP-Tourenplan-Menge zu entwickeln, dass die Belange eines Sicherheitsdienstes beachtet. Mindestens eine neue Klasse von Nebenbedingungen und/oder Kostenfaktoren muss einem klassischen VRP-Modelle auf Basis einer fundierten Diskussion hinzugefügt werden. Die Gestalt optimaler Lösungen soll anhand von konstruierten Beispielen und Testrechnungen bewertet werden.

    Abgabe: 31.01.2020

  • Bachelorarbeit: Online-Searching.

    Zusammenfassung: Im Problem Online-Searching versucht man in einem Graphen einen bestimmten Zielknoten zu finden. Den Sucherfolg bemerkt man erst, wenn man den Zielknoten erreicht. Das sogenannte Cow-Path Problem ist ein Spezialfall: Eine Kuh sucht ein Loch im Zaun und kann links oder rechts beginnen zu suchen und nach beliebieger Zeit auch umkehren. Ziel ist eine Online-Strategie, die, egal wo das Loch sich befindet, immer nur einen möglichst kleinen konstanten Faktor der Entfernung des Lochs vom Startpunkt laufen muss. Jaillet und Stafford haben dieses Problem in der Literatur auf Bäumen untersucht. Fleischer und Koautoren haben in der Literatur einige der Resultate verbessert.

    Aufgabe dieser Bachelorarbeit ist es, Anwendungsfälle (z. B. Evakuierungsprobleme) von Online-Searching zu identifizieren und die aus der Theorie generierten Handlungsempfehlungen kritisch im Anwendungsfall zu bewerten.

    Abgabe: 31.01.2020

  • Bachelorarbeit: Optimierte Bewegung von Strecken in Polygonen.

    Zusammenfassung: Man möchte einen Baumstamm in einem durch eine polygonale Mauer begrenzten Gelände vollständig herumdrehen. Wie lang kann der Baumstamm höchstens sein? Aufgabe dieser Bachelorarbeit ist es, theoretischen Überlegungen und Computer-Experimente zu Algorithmen vorzunehmen, die uns der Lösung dieser Frage (in idealisierter Form) näher bringen. Das Problem selbst ist bislang offen, so dass jede Form von Fortschritt erwünscht ist. Teil der Aufgabe ist eine saubere formalmathematische Formulierung und die Untersuchung von (vereinfachten) Spezialfällen und Beispielen in diesem formalen Rahmen. Hierbei sind Aspekte der Mathematik (Geoemtrie in der Ebene) und Informatik (Optimierungsprobleme, Entscheidungsprobleme, Komplexität) einzubringen sowie praktische Fähigkeiten (Computerprogrammierung). Die formalen Details der Aufgabenstellung finden sich in der Anlage.

    Abgabe: 31.08.2019

  • Bachelorarbeit: Dynamic Programming versus MILP für das Guaranteed Service Model.

    Zusammenfassung: Das Guaranteed Service Model (GSM) ist ein Optimierungsmodell zur Bestimmung von garantierten Service-Zeiten in Liefernetzen zur Erreichung eines vorgegebenen Servie-Grads bei stochastischer Nachfrage. Davon kann man unter anderem Sicherheitsbestände ableiten, die ausreichend sind, um diesen Service-Grad zu erreichen.

    Zur Lösung des GSM auf divergenten Netzen existieren zwei konkurrierende Ansätze: Dynamic Programming (DP), angewandt in der Literatur, und Mixed Integer Linear Programming (MILP). Bei komplizierten Liefernetzen und Nachfragen kann die Lösung des GSM über die MILP-Technik auf- wendig werden, was für eine stochastische Erweiterung SGSM des GSM noch amplifiziert wird.

    Aufgabe dieser Bachelor-Arbeit ist es, für den Anwendungsfall in der Literatur beide Lösungsmethoden zu vergleichen und Empfehlungen abzuleiten.

    Abgabe: 31.07.2018

  • Bachelorarbeit: Das Guaranteed Service Model mit Stochastischen Lieferzeiten.

    Zusammenfassung: Zur Abfederung der Nachfragevariabilität in Liefernetzwerken werden als Puffer Lager eingesetzt. Einen großen Einfluss auf die erwarteten Gesamtkosten hat die Festlegung der Sicherheitslagerbestände. Ein dafür vorgeschlagener Modellierungsansatz ist das Guaranteed Service Model (GSM): Statt direkt Sicherheitsbestände zu bestimmen, werden garantierte Servicezeiten für jeden Lieferanten ermittelt, aus denen sich geeignete Sicherheitslagerbestände berechnen lassen. Im Grundmodell sind die Lieferzeiten (gerechnet ohne Auslieferungsverzögerungen) deterministisch angenommen. In der Literatur wurden die Konsequenzen stochastischer Lieferzeiten analysiert und festgestellt, dass das GSM dadurch zu einem nicht-konvexen, sehr komplizierten Optimierungsproblem wird. Auf der anderen Seite wurde in der Literatur ein Ansatz aus der gemischt-ganzzahligen Programmierung (MILP) zur Lösung des GSM vorgeschlagen, in den sich möglicherweise durch zusätzliche binäre Variablen und Nebenbedingungen stochastische Lieferzeiten integrieren lassen, wenn man nur endlich viele Szenarien von Lieferzeiten untersucht (ähnlich wie in der Literatur). Aufgabe in dieser Bachelorarbeit ist es, zu erklären, was die Schwierigkeit der stochastischen Lieferzeiten im GSM ausmacht und ob man evtl. mit MILP-Methoden für lineare Nachfragenschranken und (wenige) endlich viele Szenarien stochastische Lieferzeiten logisch konsistent behandeln kann.

    Abgabe: 31.07.2018

  • Bachelorarbeit: Optimale Lagerhaltung mit Kapazitäten und Nachfrage-Vorabinformation.

    In der klassischen Lagerhaltungstheorie, die mit Markovschen Entscheidungsproblemen modelliert wird, gibt es keine Kapazitätsbeschränkungen. Manchmal sind aber Lager- und/oder Produktionskapazitäten beschränkt. In der Literatur wird gezeigt, dass man die beschränkten Kapazitäten durch Nachfrage-Vorabinformationen in gewisser Weise ausgleichen kann, so dass die wesentliche Struktur der Optimalkostenfunktion (Konvexität) gegenüber der Problemstellung ohne Kapazitätsbeschränkungen erhalten bleibt.

    Aufgabe dieser Bachelorarbeit ist es, diese Zusammenhänge genau zu erklären und mit eigenen Beispielen zu illustrieren.

    Abgabe: 31.01.2018

  • Bachelorarbeit: Organspender-Tauschverfahren und das Handlungsreisendenproblem.

    Das Nierenaustauschproblem (KEG, kidney exchange problem) entsteht bei der Zuordnung von Nierenspendern zu Patienten: Wenn spendenbereite Angehörige von Patienten aus medizinischen Gründen nicht als Spender in Frage kommen, dann können von verschiedenen Spender-Patienten-Paaren die Spender ausgetauscht werden, so dass die Transplantation in den neuen Paarungen möglich ist. Tauscht man die Spender aus zwei Spender-Patienten-Paaren, so kann man die maximal erreichbare Menge von Transplantationen durch die Lösung eines Matchingproblems effizient berechnen. Erlaubt man auch längere Austausch-Zykel mit einer Obergrenze auf die Zykel-Länge, so wird das Problem NP-schwer. Daher versucht man u. a. mit Hilfe von Ganzzahliger Linearer Optimierung (ILP) optimale Lösungen zu erreichen. Hierzu gibt es einen Ansatz in der angegebenen Literatur, in dem ein direktes Modell verglichen wird mit einem Modell, dass vom Handlungsreisendenproblem inspiriert ist.

    Aufgabe dieser Bachelorarbeit ist es, die Modelle aus der angegebenen Literatur zu erklären und ihr Verhalten anhand von selbst konstruierten instruktiven Beispielen zu vergleichen.

    Abgabe: 31.12.2017

  • Bachelorarbeit: Online-Lagerhaltung bei unsicheren Preisen.

    Üblicherweise wird die Steuerung eines Warenlagers auf Basis stochastischer Informationen über eine unsichere Nachfrage mit Hilfe von Markovschen Entscheidungsproblemen (MDP) optimiert. Es gibt aber auch eine andere Quelle von Unsicherheit: Zukünftige Preise. In manchen Branchen mit stark volatilen Preisen (z. B. manche Rohstoffmärkte) kann diese Quelle der Unsicherheit sehr wichtig sein.

    Eine Art der Betrachtung von Unsicherheiten ist die Online-Optimierung. In diesem Fall werden Online-Algorithmen mit bestmöglicher Kompetitivität gesucht. Werden also die Tagespreise für Material zwischen einem Minimalpreis und einem Maximalpreis jeden Tag neu bekannt gegeben ohne stochastische Vorabinformation, dann muss ein Online-Algorithmus jeden Tag über die Nachbestellung von Material entscheiden, ohne zukünftige Preise zu kennen. Dies ist eine Erweiterung des Economic Order Quantity-Modells (EOQ) und wurde von Larsen und Wøhlk (2010) untersucht.

    Aufgabe dieser Bachelorarbeit ist es, Lagerhaltungspolitiken, die unter dem Blickwinkel der kompetitiven Analyse gut sind, zu vergleichen mit typischen Politiken, die unter dem MDP-Blickwinkel gut sind. Hierzu sollen vor allem Beispiele entworfen werden, bei denen sich Unterschiede und Gemeinsamkeiten deutlich zeigen. Sollte es keine substanziellen Unterschiede geben, ist nach einer Begründung dafür zu suchen.

    Abgabe: 30.09.2017

  • Bachelorarbeit: Anwendung des minimax-Q learning Algorithmus auf Beachvolleyball.

    Der Q-learning Algorithmus für Markovsche Entscheidungsprobleme ist mit der Wertiteration für Markovsche Entscheidungsprobleme verwandt. Anstatt die Kostenfunktion einer bestimmten Politik zu approximieren, werden Q-Faktoren, die mit der Optimalkostenfunktion verknüpft sind, approximiert. Dieser Algorithmus wurde für einen adaptiven Spieler in einer Umgebung, die sich nach festen Übergangswahrscheinlichkeiten entwickelt in der angegebenen Literatur beschrieben. Littman hat diesen Ansatz auf Zwei-Personen Markov Spiele übertragen und einen minimax-Q learning Algorithmus für zwei adaptive Spieler entwickelt. Dieser Algorithmus wird auf in der Arbeit beispielhaft auf ein stark vereinfachtes Markov Spiel für Fußball angewendet.

    Aufgabe dieser Bachelorarbeit ist es, ein stark vereinfachtes Modell für Beachvolleyball als Markov Spiel zu entwickeln und den minimax-Q learning Algorithmus darauf anzuwenden. Dabei sollen verschiedene Rechenexperimente mit Spielen gegen unterschiedlich trainierte Gegner durchgeführt werden.

    Abgabe: 31.07.2017

  • Bachelorarbeit: Zwölf Geschworene und optimale Diplomatie in mehrdimensionalen Meinungsräumen.

    Optimale Diplomatie ist best-mögliche Art und Weise, in einer Reihe von Meetings eine Meinung zu vertreten, um am Ende möglichst viele Unterstützer zu gewinnen. Formell wurde dieses Problem in der Literatur aufgebracht und erste Untersuchungen durchgeführt. Grundlage ist die Hegselmann-Krause-Dynamik (HK-Dynamik) auf Basis des sogenannten "Bounded-Confidence"-Konzepts. In einer populärwissenschaftlichen Darstellung wurde das Konzept anhand der Meinungsdynamik im Kinofilm "12 angry men" (deutscher Verleihtitel: "Die zwölf Geschworenen") plastisch gemacht. Der Artikel endet damit, dass die Dynamik im Film nicht vollständig durch die im Artikel eingenommene eindimensional Sichtweise erklärt werden könne. Für die plausible Behauptung wurde jedoch bislang keine stichhaltige Argumentation vorgelegt. Ferner ist offen, ob die Dynamik im Film ("Wer stimmt in der soundsovielten Abstimmung für was?") nicht vielleicht durch mehrdimensionale Meinungsräume als formale Instanz einer kontrollierten Meinungsdynamik darstellbar ist.

    Aufgabe dieser Bachelorarbeit ist es, diese Fragen ergebnisoffen zu untersuchen und die Ergebnisse angemessen zu dokumentieren.

    Abgabe: 31.07.2017

  • Bachelorarbeit: Ähnlichkeitsanalyse von Musikstücken mit Ganzzahliger Linearer Modellierung.

    Die Beurteilung der Ähnlichkeit von Musikstücken spielt eine große Rolle in der Zuordnung der tatsächlichen Urheberschaft von Musikstücken. Um Urteile wenigstens teilweise auf objektive Fakten zu stützen, wird nach mathematischen Klassifikationssystemen gesucht. Ein neuerer Ansatz nutzt Ganzzahlige Lineare Modelle (ILP). Für ein Beispielmusikstück wird sein Stil wie folgt durch die zulässige Menge eines ILP beschrieben: Für das Beispielmusikstück werden die verschiedenen musikalischen Dimensionen (Harmonie, Melodie, Rhythmus, ...) in Binärwerte kodiert, und zwar für verschiedene zeitliche Auflösungen. Aus diesen Werten werden Statistiken ermittelt, von denen man denkt, dass sie wichtig sind für den musikalischen Eindruck. Alle Stücke mit denselben oder ähnlichen Statistiken werden als ähnlich im Stil aufgefasst. Im speziellen Ansatz wird das durch lineare Gleichungen und Ungleichungen in den Binärvariablen ausgedrückt.

    Ziel dieser Bachelorarbeit ist es, dieses ILP-System auf eine Reihe von (vereinfachten) Musikstücken auszuprobieren und ein paar Fragen dazu zu klären.

    Abgabe: 31.07.2017

  • Bachelorarbeit: Optimale Lagerhaltung mit robuster Optimierung.

    Üblicherweise wird optimale Lagerhaltung in diskreter Zeit (z. B. tägliche Nachbestellmöglichkeit) modelliert mit Markovschen Entscheidungsproblemen (MDP), um die Unsicherheiten (vor allem der Nachfrage) mathematisch abzubilden. Für einfache Spezialfälle kennt man optimale Politiken, die auch in komplizierteren Umgebungen wegen ihrer einfachen Struktur bevorzugt angewendetet werden, sogar wenn sie bekanntermaßen suboptimal sind. Es gibt aber auch eine Alternative zur Behandlung der Unsicherheiten: Robuste Optimierung (RO). In dieser Arbeit soll ein Ansatz aus der RO zur optimalen Lagerhaltung anhand von selbst entwickelten instruktiven Beispielen mit den Resultaten der MDP-Methoden verglichen werden.

    Abgabe: 31.07.2017

  • Bachelorarbeit: Fuzzy-Linear-Programming für unsichere Produktionsplanungsprobleme.

    In der Produktionplanung kann man mit Hilfe der Linearen Programmierung (LP) Produktionsmengen mit maximalem Deckkungsbeitrag bei gegebenen Ressourcenbeständen ausrechnen. Aber nur, wenn man alle Daten tatsächlich genau kennt. Ist Unsicherheit im Spiel, dann muss man Optimierungsmethoden für unsichere Optimierungsprobleme anwenden wie stochastische Optimierung oder robuste Optimierung. Eine Alternative, die auch die Unsicherheit bei der Formulierung der Wünsche des Anwenders mit berücksichtigen kann, ist die Methode Fuzzy-Linear-Programming (FLP). Hierbei wird die Zugehörigkeit eines Punktes zur zulässigen Menge nicht scharf sondern durch eine parametrisierbar schwammige Mitgliedschaftsfunktion dargestellt.

    Ziel dieser Bachelorarbeit ist es, die Lösungsvorschläge von FLP für ein konkretes Produktionsplanungsbeispiel zu ermittlen und mit den Lösungsvorschlägen von LP zu vergleichen, wenn Unsicherheiten auftreten.

    Abgabe: 30.06.2017

  • Bachelorarbeit: Integriertes Routen und Verteilen von Ganzladungstransporten.

    Im Ganzladungs-Güterverkehr ("Full Truckload") wird der ganze LKW für nur eine Lieferung verwendet. Bei großen Entfernungen sind manchmal auch bei kürzest-möglichen Transportrouten lange Pausen und damit nutzlose Standzeiten der (teuren) Fahrzeuge unvermeidlich. Im ILAN-Projekt der FH Erfurt wird untersucht, wie eine Gruppe von Kleinspediteuren Lieferungen kooperativ transportieren können, so dass möglichst viele Fahrer jeden Abend wieder zu Hause sind. Das geht zum Beispiel dadurch, dass sich die Spediteure die Ladungen auf gemeinschaftlich genutzten Trailern übergeben, so dass die Zugmaschinen jedes Spediteurs nur eine halbe Tagesfahrt entfernt vom eigenen Depot unterwegs sind.

    In der Literatur wurde dazu ein Modell entwickelt: Möglichst viele Lieferungen sollen kooperativ transportiert werden, ohne dass Leerfahrten entstehen. Das ist ein Matching-Problem mit einer Set-Covering-Bedingung. Im Artikel wird das Problem mit einem ad-hoc-Algorithmus gelöst. Die Rechenzeiten sind problematisch für viele Lieferungen. In einer Bachelorarbeit wurden Gemischt-Ganzzahlige Modelle (MILP) entwickelt, die sich mit Standard-Software wesentlich schneller lösen lassen. Allerdings offenbaren Testrechnungen, dass das Optimierungspotenzial wegen des starren Ansatzes nicht so groß ist wie gewünscht.

    Aufgabe dieser Bachelorarbeit ist es, die starren Regeln des originalen Kooperationsansatzes an geeigneten Stellen zu flexibilisieren. Die größte Flexibilisierung entsteht dadurch, dass die einzelnen Transporte nicht notwendig entlang kürzester Routen laufen müssen. Es kann besser sein, die Routen genau so zu planen, dass der Nutzen der Kooperation am größten wird. Hierfür soll ein integriertes MILP entwickelt werden und anhand von Beispieldaten getestet werden.

    Abgabe: 28.02.2017

  • Bachelorarbeit: Wie geht man am besten über die Landesgartenschau - eine Anwendung des Orienteering-Problems mit Erweiterungen.

    In der Literatur finden sich Ansätze, wie touristische Touren optimiert werden können. Dabei geht es nicht in erster Linie um kürzeste Wege sondern auch um schönste. Ein Modellansatz stützt sich auf das Orienteering-Problem (OP).

    Aufgabe dieser Bachelorarbeit ist es, die Modelle zum OP auf Basis Gemischt-Ganzzahliger Linearer Programmierung (MILP) zu erklären, mathematische Standard-Methoden zu ihrer Lösung zu skizzieren und die Modelle beispielhaft auf Spaziergänge über die Landesgartenschau Bayreuth anzuwenden.

    Abgabe: 15.12.2016

  • Bachelorarbeit: Das Ressourcen-beschränkte-Kürzeste-Wege-Problem: Algorithmen und Anwendungen.

    Das Kürzeste-Wege-Problem mit Ressourcenbeschränkungen (engl.: Shortest-Path Problem with Resource Constraints, SPPRC) fragt nach einem kürzesten Weg unter der Nebenbedingung, dass auf dem Weg der Resourcenverbrauch einer oder mehrerer Resourcen ein gegebenes Budget jeweils nicht übersteigt. Das SPPRC ist bekanntermaßen NP-schwer, kann aber mit einem pseudopolynomialen Dynamic-Programming-Algorithmus gelöst werden. In einer klassischen Arbeit hat Hassin ein polynomiales Approximationsschema (PTAS) vorgestellt: Für jede konstant vorgebene Optimalitätslücke existiert ein Algorithmus, der in Polynomialzeit das SPPRC innerhalb dieser Lücke löst.

    In dieser Arbeit soll der Hintergrund des SPPTW und das PTAS von Hassin erklärt werden und eine Anwendung des SPPRC im Bereich der touristischen Routenplanung (z. B. Radfahren, Landesgartenschau) diskutiert werden.

    Abgabe: 31.10.2016

  • Bachelorarbeit: Optimierung von Patiententransporten im Krankenhaus.

    Patiententransporte in Krankenhäusern erfordern eine sorgfältige Planung, damit Wartezeiten sowohl für Patienten als auch für Behandelnde möglichst vermieden werden. Hierzu gibt es auch Ansätze auf Basis mathematischer Optimierung. Oftmals werden heuristische Ansätze den exakten Methoden vorgezogen, da es sehr schwierig ist, sich auf Modelle zu verständigen, die die Wünsche der Agierenden in einem Krankenhaus genau abbilden. Ein solcher, auf Meta-Heuristiken basierender Ansatz wurde in der Literatur entwickelt und implementiert. Es stellt sich die interessante Frage, ob die verwendete Heuristik in bestimmten Fällen zu stark suboptimalen Lösungen führen kann, oder ob „in aller Regel“ die Optimalitätslücke klein ist.

    Aufgabe dieser Bachelorarbeit ist es, für das Modell in der Literatur auf ausgewählten Beispielinstanzen die heuristische Lösungsqualität mit dem exaktem Optimalwert zu vergleichen.

    Abgabe: 30.09.2016

  • Bachelorarbeit: Optimale Kooperation in Speditionsnetzen.

    Beim Gütertransport auf der Straße unterscheidet man zwischen Aufträgen mit Full-Truckload (jede Lieferung nimmt einen ganzen LKW in Anspruch, wie zum Beispiel bei Umzugsunternehmen) und Less-Than-A-Truckload (eine Lieferung wird im LKW mit anderen zusammengepackt, wie zum Beispiel bei Paketdiensten). Wird der ganze LKW für nur eine Lieferung verwendet und geht die Fahrt sehr weit, so muss der Fahrer seine Ruhezeiten unterwegs einschieben. Das (teure) Fahrzeug ist in der Zeit unproduktiv. Daher wird im ILAN-Projekt der FH Erfurt untersucht, wie eine Gruppe von Kleinspediteuren Lieferungen kooperativ transportieren können, so dass möglichst viele Fahrer jeden Abend wieder zu Hause sind. Das geht zum Beispiel dadurch, dass sich die Spediteure die Ladungen auf gemeinschaftlich genutzten Trailern übergeben, so dass die Zugmaschinen jedes Spediteurs nur eine halbe Tagesfahrt entfernt vom eigenen Depot unterwegs sind.

    In der Literatur wurde dazu ein Modell entwickelt: Möglichst viele Lieferungen sollen kooperativ transportiert werden, ohne dass Leerfahrten entstehen. Das ist ein Matching-Problem mit einer Set-Covering-Bedingung. Im Artikel wird das Problem mit einem ad-hoc-Algorithmus gelöst. Die Rechenzeiten sind in vielen Fällen problematisch für viele Lieferungen.

    Aufgabe dieser Bachelorarbeit ist es, die Aufgabe mit einem geeigneten Gemischt-Ganzzahligen Programm (MILP) zu modellieren und mit einem Standard-Löser (z. B. SCIP) zu lösen. Die Lösungen und die Rechenzeiten sollen mit dem Verfahren aus der Originalarbeit verglichen werden. Erweiterungen des MILP auf Kapazitäten und anderen Nebenbedingungen und Zielfunktionen sollen diskutiert werden.

    Abgabe: 30.09.2016

  • Bachelorarbeit: Grundlagen kollektiver Entscheidungsfindung - Arrows Unmöglichkeitstheorem.

    Abgabe: 31.08.2016

  • Bachelorarbeit: Kooperative Spieltheorie - Der Satz von Pick und die Anzahl vollständiger einfacher Wahlspiele.

    Abgabe: 31.07.2016

  • Bachelorarbeit: Performance-Potential-Metamodell.

    Das Performance-Potential-Metamodell modelliert die Wechselwirkung zwischen Belastung und Leistung unterschiedlichster Systeme in der Sportphysiologie. Es wurde ursprünglich von Jürgen Perl entwickelt und wird aktuell in den Sportwissenschaften angewandt und weiterentwickelt. Die Systemdynamik des ursprünglichen Modells besitzt Nichtlinearitäten, weshalb im bisherigen Lösungsansatz heuristische Verfahren verwendet werden.

    Aufgabe dieser Bachelorarbeit ist es, das Modell mit den Methoden der ganzzahligen linearen Optimierung zu analysieren. Dabei soll die Systemdynamik des Performance-Potential-Metamodells als ganzzahliges lineares Programm modelliert werden oder begründet werden warum dies nicht möglich ist. Gefundene Optimallösungen von Beispielinstanzen sollen mit Ergebnissen der heuristischen Verfahren verglichen werden. Die Unterschiede zwischen den beiden Ansätzen sollen deutlich werden.

    Abgabe: 31.07.2016

  • Bachelorarbeit: Optimale Haltepunktplanung für den Bahnverkehr.

    Nach der Einrichtung einer Bahnlinie müssen die Haltepunkte festgelegt werden. Gerade im ländlichen Raum ist es aber gar nicht offensichtlich, wo die besten Stellen dafür sind. In der Literatur gibt es Mathematische Modelle, deren Optimallösungen Vorschläge für die Festlegung solcher Haltepunkte gemäß verschiedenen Kriterien generieren.

    Aufgabe dieser Bachelor-Arbeit ist es, diese Ansätze zu sammeln und einen ausgewählten Ansatz auf ein selbst definiertes Haltepunktplanungsproblem der Region Bayreuth anzuwenden. Beispielsweise können die tatsächlichen Haltepunkte an einer existierenden Bahnstrecke mal auf ihre Qualität in einem der mathematischen Modelle geprüft werden.

    Abgabe: 31.07.2016

  • Bachelorarbeit: Optimale Planung von Turnieren mit wechselnden Spielstätten.

    Die optimierte Planung von nationalen Sportligen (DFL, DBL) wird heutzutage mit modernen mathematischen Methoden durchgeführt. Ein interessantes verwandtes Problem ist die Planung von Turnieren mit mehreren Austragungsorten (z. B. Beachvolleyball-Felder auf einer Urlaubsinsel). Auch diese Problemstellung kann man mit graphentheoretischen Methoden und diskreter Optimierung angreifen.

    Aufgabe dieser Bachelorarbeit ist es, die mathematische Modellierung und Optimierung eines Turniers mit mehreren Austragungsorten zu erklären und auf ein von den Bayreuther Sportwissenschaftlern im Sommer 2016 veranstaltetes Beachvolleyball-Turnier anzuwenden.

    Abgabe: 31.07.2016

  • Bachelorarbeit): Optimale robuste Mountainbike-Touren.

    Um eine Mountainbike-Route automatisch zu berechnen, müssen viel mehr Aspekte berücksichtigt werden als beim Navigieren mit Autos auf Straßen. Nicht die schnellste/kürzeste Strecke ist gesucht, sondern die genussreichste. Ferner ist bei besonders attraktiven Single-Trails aus Wanderkarten die Befahrbarkeit zum Tourzeitpunkt oft nicht bekannt. Nutzt eine geplante Tour so einen Trail, so kann die Gesamttour wegen Schiebe-/Tragepassagen viel unattraktiver sein als gedacht.

    Aufgabe dieser Bachelorarbeit ist es, möglichst einfache robuste und/oder stochastische Optimierungs-Modelle für die Berechnung einer besten Mountainbike-Route von A nach B zu entwickeln, die mit alltäglichen Anforderungen logisch kompatibel sind. Dabei sollen Erkenntnisse aus dem Bereich der robusten und/oder stochastischen Optimierung beachtet und bewertet werden. Die Unterschiede zur Kfz-Navigation sollen deutlich werden.

    Abgabe: 31.12.2015

  • Bachelorarbeit: Robuste Markovsche Entscheidungsprobleme für Sportspiele.

    Markovsche Entscheidungsprobleme (MDP) modellieren optimale Handlungsstrategien für sequentielles Entscheiden unter Unsicherheit. Manchmal ist eine vollständige Information über alle Übergangswahrscheinlichkeiten nicht verfügbar oder entsprechende statistische Schätzungen sind sehr unzuverlässig. Man ist also damit konfrontiert, dass eine berechnete Politik unter anderen als den Modellbedingungen zum Einsatz kommt. Um zu erreichen, dass die angewendete Politik in einer Situation mit veränderten Wahrscheinlichkeiten nicht zu schlecht abschneidet, kann man Konzepte der robusten Optimierung auf die Berechnung optimaler Politiken für MDPs anwenden.

    Im Bereich der Sportspielforschung können Übergangswahrscheinlichkeiten für MDP-Modelle tatsächlich nur grob geschätzt werden. Aufgabe dieser Bachelorarbeit ist es daher, für ein einfaches Sportspiel-MDP eine robuste Politik zu berechnen und ihre erwartete Performance mit einer nicht robusten optimalen Politik numerisch zu vergleichen.

    Abgabe: 30.09.2015

  • Bachelorarbeit: Optimale Agrarplanung unter Unsicherheit.

    Eine wesentliche Teilaufgabe in der Agrarplanung ist die Folgende: Welche Nutzpflanze soll auf welchem Teil der verfügbaren Ackerfläche angebaut werden? In einfachen Modellen der Linearen Programmierung (LP) wird angenommen, dass der Ertrag pro Fläche für jede Pflanze im Voraus bekannt ist. In der Realität schwankt dieser Flächenertrag aber. Eine Methode, damit umzugehen, ist die Stochastische Lineare Programmierung (SLP).

    Ziel dieser Arbeit ist es, für eine Fallstudie das Verbesserungspotenzial von SLP gegenüber LP in Anbetracht unsicherer Ertragsdaten zu ermitteln.

    Abgabe: 31.07.2015

  • Bachelorarbeit: Online-Algorithmen für Webcaching.

    Das Webcaching-Problem fragt nach der besten Vorschrift, wie ein Webbrowser heruntergeladene Dokumente in einem Cache zwischenspeichern soll, um zukünftige Anforderungen mit weniger Wartezeit bedienen zu können. Man unterscheidet dabei, ob der Webserver für die angeforderten Dokumente genau in der Reihenfolge der Anfragen die Cache-Entscheidung (Cachen: ja/nein, wenn ja, welches Dokument ersetzen) treffen soll oder ob eine Umsortierung (Pipelining) in gewissem Rahmen möglich ist (Webcaching mit Umsortierung, kurz WCRP: the webcaching-with-reordering problem). Ferner ist wichtig, ob ein Zugriff stets über den Cache erfolgen muss (wie bei der Speicherverwaltung eines Betriebssystems) oder ob ein Dokument auch unter Umgehung des Cache (bypassing) angezeigt werden kann.

    Ziel dieser Bachelorarbeit ist es, die Resultate der Literatur zur kompetitiven Analyse vorzustellen und mit eigenen Überlegungen zu erweitern. Zum Beispiel: Was bringt Lookahead im Vergleich zum Standard-Paging? Wie wirkt sich Bypassing auf die bekannten Standard-Paging-Resultate der kompetitiven Analyse aus?

    Abgabe: 31.07.2015

  • Bachelorarbeit: Markovsche Entscheidungsprobleme zur bestimmung optimaler Tennis-Spielstrategien.

    In der Literatur wird ein Markovsches Entscheidungsproblem (MDP) definiert, das die strategischen Entscheidungen während eines Tennis-Ballwechsels modelliert. Zur Lösung wird ein statistisches Lernverfahren (Monte-Carlo-Baumsuche) angewendet, weil Übergangswahrscheinlichkeiten schwer zu bestimmen sind. Damit erhält man Politiken und Schätzungen für die Gewinnwahrscheinlichkeit. Allerdings ist das MDP nicht so groß, dass es ausgeschlossen wäre, zunächst alle Wahrscheinlichkeiten zu schätzen und dann eine optimale Politik zu bestimmen.

    Aufgabe dieser Bachelorarbeit ist es, das in der Literatur angegebene MDP bei gegebenen Wahrscheinlichkeiten direkt mit den üblichen mathematischen Verfahren zu lösen oder präzise zu beschreiben, warum das nicht geht.

    Abgabe: 31.07.2015

  • Bachelorarbeit: Über robustes Lot-Type-Design in der Warenverteilung eines Textil-Discounters.

    Modeartikel werden manchmal im Herstellungsland bereits als Sortimente mit unterschiedlichen Konfektionsgrößen vorverpackt. Ein Lot-Typ bestimmt dabei, wieviele Teile in welcher Größe sich in so einem Paket (= Lot) befinden. Das Lot-Type-Design-Problem (LDP) fragt nach der besten Auswahl von Lot-Typen zur Belieferung von Filialen mit gegebener erwarteter Nachfrage nach Größen. Nun sind im Liefer- und Abverkaufsprozess Unsicherheiten zu erwarten. Zum Beispiel sind die erwarteten Nachfragen nur Schätzungen, und die tatsächliche Lieferung des Herstellers stimmt manchmal nicht genau mit der Bestellung beim Hersteller überein.

    Ziel dieser Bachelorarbeit ist es, das LDP zu robustifizieren bzgl. geeigneter Datenunsicherheitsmengen und die Ergebnisse zu diskutieren.

    Abgabe: 31.07.2015

  • Bachelorarbeit: Tanzpaarzuordnung bei unvorhesehbaren Stimmungsschwankungen - eine Anwendung von Stochastischem Matching.

    Angenommen, für einen Tanzball sollen gemischte Tanzpaare zusammengestellt werden. Es ist durch nicht-negative Gewichte (= Spaßfaktoren) bekannt, wieviel Spaß es den möglichen Paaren machen würde, miteinander zu tanzen. Dann kann man durch ein gewichtsmaximales Matching eine "gesamtspaßmaximale" Zusammenstellung von Tanzpaaren für den Ball berechnen. Nun ist nicht jeder Mensch an jedem Tag gleichgut "drauf". Dies äußert sich beim Tanzpaar-Problem darin, dass die Spaßfaktoren stochastisch sind. So kann ein Tanzpaar an einem Tag eine Menge gute Laune versprühen und an einem anderen sich nur zanken. Man kann also die Spaßfaktoren als stochastisch ansehen. Das Ziel besteht darin, eine Tanzpaarzusammenstellung zu finden mit dem maximalen erwarteten Gesamtspaß. Dies ist ein einstufiges stochastisches bipartites Matching-Problem (SBMP). Nehmen wir nun an, es ist erlaubt, einige Tanzpaare erst am Ball-Abend zusammenzustellen, wenn die Stimmungslage bereits bekannt ist. Für die Vorab-Zuordnung bekommt man einen deterministischen Spaßfaktor abhängig vom Paar. Nach der Zuordnung am Ball-Abend gibt es die dann realisierten stochastischen Spaßfaktoren hinzu, weil nun klar ist, wer in welcher Stimmung ist und wer in nun aufgebrezelter Form wem wie gut gefällt. Dies führt auf ein zweistufiges stochastisches bipartites Matching-Problem mit Kompensation (SBMP2).

    Ziel dieser Arbeit ist es, für das SBMP zu klären, ob der Wert der stochastischen Lösung (VSS) Null ist (Erwartungswert-Äquivalenz). Ferner sollen Beispielinstanzen des SBMP und des SBMP2 bei endlichen Verteilungen mit Hilfe von Szenario-Sampling und Szenario-Reduktion gelöst werden. Hierbei soll eine fundierte Szenario-Reduktion in Bezug auf die Lösungsqualität verglichen werden mit dem willkürlichen Weglassen von Szenarien.

    Abgabe: 31.07.2015

  • Bachelorarbeit: Spieltheoretische Überlegungen zur Bounded-Confidence-Dynamik.

    In der Philosophie und in den Sozialwissenschaften untersucht man künstliche Gesellschaften. In solchen künstlichen Gesellschaften gibt es absichtlich stark vereinfachte Interaktionsmodelle, die man mit Mathematik und/oder Computer-Experimenten untersuchen kann. Entstehen dabei nicht-triviale Effekte, so hat man damit sehr grundsätzliche Strukturen identifiziert, die solche Effekte hervorrufen können. Findet man die Effekte auch in einer realen Gesellschaft vor, so ist dies ein Hinweis darauf, dass die einfache Struktur eine substantielle Rolle in der realen Gesellschaft spielen könnte. Ein seit einigen Jahren vielfach betrachtetes Modell für die dynamische Entwicklung von Meinungen ist die sogenannte Bounded-Confidence-Dynamik (BC). In der einfachsten Variante besteht der Meinungsraum aus dem reellen Einheitsintervall. Nach einer (diskreten) Runde Meinungsaustausch bilden sich die neuen Meinungen durch Durschschnittsbildung mit allen anderen Meinungen, die nicht weiter als ε ∈ [0, 1] (der Konfidenzradius) entfernt sind. Durch kontrollierte Meinungsäußerungen kann man die dynamische Entwicklung in eine gewünschte Richtung bewegen. Mathematisch wurde dieses Konzept für BC erstmals als Optimalsteuerungsproblem in der grundlegendsten Form präsentiert. Hier ging man davon aus, dass ein globaler Planer die Meinungsäußerungen von einem oder mehreren Agenten steuert. Gibt es zwei oder mehr Spieler, die jeweils einen oder mehrere Agenten unabhängig voneinander, und mit eigenen Zielen, steuern können, so verlässt man das Gebiet der Optimalsteuerung und landet in der Spieltheorie.

    Aufgabe dieser Bachelorarbeit ist es, erste spieltheoretische Untersuchungen zur Bounded-Confidence-Dynamik anzustellen. Das allgemeine Problem wurde bereits in der Literatur kurz beschrieben. Für Spezialfälle und kleine Anzahlen an Agenten bzw. Runden sollten sich theoretische und computerunterstützte Ergebnisse finden lassen.

    Abgabe: 31.07.2015

  • Bachelorarbeit: Optimierte Arbeitsplatzgestaltung.

    Wie soll ein Regal mit 40 Komponenten-Behältern auf 4 Ebenen eingerichtet werden, damit eine Montagekraft bei den erwarteten Montagearbeiten am ergonomischsten und schnellsten arbeiten kann? Aufgabe dieser Bachelorarbeit ist es, diese Frage in Zusammenarbeit mit der Firma Wibond Informationssysteme mit Hilfe mathematischer Optimierungsverfahren zu lösen. Details der Aufgabenstellung finden sich im Anhang des Kooperationspartners.

    Ziel der Bachelorarbeit ist es, geeignete mathematische Modelle und Verfahren zu identifizieren, die zu einer besseren Regal-Einrichtung in der Praxis führen. Gütegarantien für Lösungsvorschläge sind erwünscht.

    Abgabe: 30.06.2015

  • Bachelorarbeit: Optimierung von Kurierdiensten unter Unsicherheit. Die Optimierung der Auslieferfahrten von Kurierdiensten kann man im weiteren Sinne als Vehicle Routing Problem (VRP) modellieren. Eine deterministische Modellierung findet aber oft Lösungen, die bei einer Änderung/Ergänzung der Daten gar nicht mehr gut sein müssen. Eine mathematische Modellierungsmöglichkeit ist die Stochastische Ganzzahlige Lineare Optimierung mit Kompensation (SILP). Aufgabe dieser Bachelorarbeit ist es, das Modell aus [2] zu erläutern und mit Beispielen das Verhalten in Bezug auf Störungen zu illustrieren. 
    Abgabe: 31.08.2014
  • Bachelorarbeit: Branch-and-Cut für Universitätskurs-Stunden- und Raumplanung. Universitätskurs-Stunden- und Raumplanung (UCT) kann mit Hilfe Ganzzahliger Linearer Programmierung (ILP) modelliert werden. An der Universität Bayreuth ist dieser Ansatz in einem von der Oberfrankenstiftung geförderten Forschungsprojekt (AZuR) verfolgt worden. Die Lösung der entstehenden ILPs für realistische Problemgrößen erfordert fortgeschrittene Techniken. Während in AZuR hauptsächlich dynamische Spaltengenerierung verfolgt wurde, ist es das Ziel dieser Bachelor-Arbeit, Schnittebenen-Methoden und ihre Integration in einen Branch-and-Bound-Algorithmus, also Branch-and-Cut-Verfahren (B&C) zu beleuchten. Hierbei werden schwierig zu behandelnde Klassen von Nebenbedingungen oder implizierte Restriktionen nicht vollständig zum Modell hinzugefügt, sondern nach und nach separiert. 
    Abgabe: 31.07.2014
  • Bachelorarbeit: Effiziente Minimierung der Bestrahlungsdauer in der Krebstherapie mit Linearer Programmierung. Um bei der Bestrahlung von Tumoren möglichst wenig gesundes Gewebe zu beeinträchtigen, werden in Bestrahlungsgeräten Blenden eingesetzt. Die Planung der Bestrahlung besteht dann aus einem therapeutisch gewünschten Blendenmuster und einer Abfolge von durch das Gerät realisierbaren Blendenmustern, die sich zum gewünschten zusammensetzen. Je nachdem, wie man ein gewünschtes Muster zusammensetzt, wird der Patient unterschiedlich lange der Bestrahlung ausgesetzt. Das Optimierungsproblem, unter allen Zusammensetzungen die mit der geringsten Gesamtbestrahlungsdauer zu finden, kann man als Lineares Programmn (LP) mit sehr vielen Variablen modellieren. Aufgabe dieser Bachelorarbeit ist es, zu erklären, auf welche Weise diese Lineare Programm in Polynomialzeit zu lösen ist, und zu untersuchen, ob es nicht auch ein Lineares Programm mit polynomiell vielen Variablen gibt. 
    Abgabe: 31.07.2014
  • Bachelorarbeit: Lot-Type-Design: Kompakte versus extensive Modellierung. Das Lot-Type-Design-Problem (LDP) fragt nach der besten Auswahl einer kleinen Menge von Vorverpackungstypen für verschiedene Größen eines Mode-Artikels (Lot-Typ) zur Belieferung einer großen Anzahl von Filialen. Ein Lot-Typ ist gegeben durch eine Anzahl für jede Konfektionsgröße. Die Bedeutung: Ein Lot dieses Typs ist eine Folientasche, die die im Lot-Typ angegebene Anzahl von Artikeln in jeder Größe enthält. Die Belieferung jeder Filiale erfolgt über eine Anzahl von Lots eines der ausgewählten Lot-Typen. Die Bewertung eines Lot-Designs erfolgt über den Abstand der resultierenden Stückzahlen in den Filialen mit ihren vorgegebenen, deterministischen Nachfragen. Diese Aufgabe trat auf im Rahmen des von der Bayerischen Forschungsstiftung geförderten Projekts DISPO in Zusammenarbeit mit einem Textildiscounter vom LS Wirtschaftsmathematik in Kooperation mit dem LS BWL V (Prof. Dr. J. Schlüchtermann). Um das LDP als Ganzzahliges Lineares Programm (ILP) zu formulieren, kann man entweder eine Anzahl-Variable für jede Größenposition eines Lot-Typen (kompaktes Modell) oder eine Auswahlvariable für jeden Lot-Typen (extensives Modell) ansetzen. Aufgabe dieser Bachelor-Arbeit ist es, die beiden Modellierungsansätze in Bezug auf Modellgröße, Ganzzahligkeitslücke und mögliche Lösungsverfahren zu vergleichen. 
    Abgabe: 31.07.2014
  • Bachelorarbeit: Approximationsalgorithmen für das Handlungsreisendenproblem. Das Handlungsreisendenproblem (TSP) fragt nach der kürzesten Rundreise durch eine endliche Menge von Städten. Das das Problem einerseits NP-schwer ist und andererseits als Modell auf viele Anwendungen passt, sind effiziente Approximationsalgorithmen mit garantierter Lösungsqualität interessant. Berühmt ist der Christofides-Algorithmus für das metrische TSP, der stets eine Tour mit einer Länge von höchstens 3/2 mal der optimalen Tourlänge in Polynomialzeit ermittelt. Aufgabe der Bachelorarbeit ist es, die neueren Entwicklungen bei Approximationsalgorithmen für das TSP zu beleuchten und ein ausgewähltes Ergebnis dabei detaillierter zu studieren. 
    Abgabe: 31.07.2014
  • Bachelorarbeit: Heuristiken, Schranken und exakte Algorithmen für Graphenfärbung. Graphenfärbung gehört zu den klassischen NP-schweren kombinatorischen Optimierungsproblemen. Jedem Knoten eines ungerichteten Graphen muss dabei so eine Farbe zugeordnet werden, so dass die Endknoten jeder Kante stets unterschiedliche Farben haben. Ziel ist die Minimierung der Anzahl benötigter Farben. Es gibt in der Literatur sowohl exakte Modelle der Ganzzahligen Linearen Optimierung (ILP) als auch verschiedenste Heuristiken. Aufgabe dieser Bachelorarbeit ist es, einen Überblick über die verschiedenen Ansätze zu verfassen mit dem Fokus auf einer selbst gewählten Methode, die etwas detaillierter beschrieben werden soll. 
    Abgabe: 31.07.2014
  • Bachelorarbeit: Losgrößenoptimierung mit Gemischt-Ganzzahliger Programmierung. Das Ziel der Losgrößenoptimierung ist die Bestimmung von bestmöglichen Bestellmengen zu festen Zeitpunkten bis zu einem festgelegten Zeithorizont. Im deterministischen Fall sind die Nachfragemengen und Lieferzeiten vorgegeben. Meistens sollen die Gesamtkosten bestehend aus Bestellkosten, Lagerhaltungskosten, Lieferverzögerungskosten minimiert werden. Verschiedene Nebenbedingungen sind denkbar wie Kapazitätsrestriktionen für Produktionseinheiten oder Lieferanten.
    In dieser Bachelor-Arbeit sollen Methoden für Losgrößenbestimmung dargestellt werden, mit besonderem Augenmerk auf Gemischt-Ganzzahligen Optimierungs-Modellen (MILP). Hier soll insbesondere die Frage untersucht werden, inwieweit durch Auftreten anderer als der vorhegesagten Nachfragen die Entscheidungsvorschläge des MILP-Modells zu schlechtem Gesamtverhalten führen können.
    Mathematische Strategien, um das Problem mit volatiler Nachfrage zu lösen, sollen kurz skizziert und diskutiert werden. 
    Abgabe: 31.12.2013
  • Bachelorarbeit: Entwurf und Analyse von Spaltengeneratoren für das Universitätskursstundenplanungsproblem. In einer Veröffentlichung von 2005 schlagen Qualizza und Serafini einen Ansatz zur Lösung des Universitätskursstundenplanungsproblems vor, der auf dynamischer Spaltengenerierung basiert.
    Gegenstand dieser Bachelorarbeit ist es, die in [1] erwähnten Methoden zur Generierung einzelner Spalten zu untersuchen und weitere zu entwerfen. 
    Abgabe: 28.02.2013
  • Bachelorarbeit: Approximation des Laserschweißproblems.

    Beim Laserschweißproblem mit festen Touren (LSP-T) in der angegebenen Literatur teilen sich Industrieroboter gewisse Ressourcen. Beispiele hierfür sind gemeinsam genutzte Laserquellen für die Bearbeitung von Schweißnähten oder Ressourcen zur Kollisionsvermeidung. Wenn zwei Roboter gleichzeitig mit derselben Laserquelle schweißen wollen oder gleichzeitig in einen kritischen Bereich fahren, in dem es zu einer Kollision zwischen Ihnen kommen kann, so liegt ein Ressourcenkonflikt vor. Das Ziel des LSP-T besteht darin, die Roboter so zu synchronisieren, dass keine Ressourcenkonflikte auftreten und der Makespan minimal ist.

    Das LSP-T ist ein wichtiges Subproblem in einem Branch-and-Bound Algorithmus zur Lösung des kompletten LSP, bei dem zusätzlich noch die Robotertouren bestimmt werden müssen. In der aktuellen Implementierung wird dazu ein gemischt ganzzahliges Modell verwendet. Während die meisten Instanzen innerhalb einer Sekunde gelöst werden können, gibt es auch welche, bei denen CPLEX auch nach Tagen noch keinen Optimalitätstest führen kann.

    In der angegebenen Literatur wurde gezeigt, dass das LSP-T NP-schwer ab 3 Roboter ist. Hierfür wurde jedoch ein pseudo-polynomialer Algorithmus sowie darauf aufbauend ein fully polynomial approximation scheme (FPTAS) angegeben. Dies wurde bisher jedoch nie implementiert oder getestet.

    In dieser Bachelorarbeit soll versucht werden, die schwierigen LSP-T Instanzen optimal bzw. approximativ zu lösen.

    Abgabe: 31.09.2012

  • Bachelorarbeit: k-Fence Ungleichungen für das Laserschweißproblem. Beim Laserschweißproblem mit festen Touren (LSP-T) [4, 5] teilen sich Industrieroboter gewisse Ressourcen. Beispiele hierfür sind gemeinsam genutzte Laserquellen für die Bearbeitung von Schweißnähten oder Ressourcen zur Kollisionsvermeidung. Wenn zwei Roboter gleichzeitig mit derselben Laserquelle schweißen wollen oder gleichzeitig in einen kritischen Bereich fahren, in dem es zu einer Kollision zwischen ihnen kommen kann, so liegt ein Ressourcenkonflikt vor. Das Ziel des LSP-T besteht darin, die Roboter so zu synchronisieren, dass keine Ressourcenkonflikte auftreten und der Makespan minimal ist. 
    Abgabe: 31.09.2012
  • Bachelorarbeit: Das Stacker Crane Problem mit Kapazitäten. Das Stacker Crane Problem (SCP) fragt nach einer Sortierung von Ein- und Auslageraufträgen eines Regalbediengeräts (RBG) der Kapazität C = 1 mit minimaler Gesamtleerfahrtstrecke.
    Thema dieser Bachelor-Arbeit ist es, das SCP mit Kapazitäten C > 1 und in Anbetracht geeigneter Regeln für die Abfolgen von Ein- und Auslagerungen algorithmisch zu untersuchen. RBG mit C > 1 gibt es für Kartons, während die RBG mit C = 1 meist für Euro-Paletten gedacht sind. Zusätzliche Regeln können sein: Alle zur Einlagerung aufgenommenen Kartons müssen eingelagert sein, bevor die erste auszulagernde Palette aufgenommen wird. Ferner ist die Be- und Entladung dieser RBG üblicherweise nicht in beliebiger Reihenfolge möglich. 
    Abgabe: 31.08.2012
  • Bachelorarbeit: Heuristiken für das Asymmetrische Traveling Salesman Problem. Das Traveling Salesman Problem (TSP) fragt nach einer kürzesten Rundreise durch n Städte. Das TSP gehört zur Klasse der NP-schweren Probleme. Daher sind auch Heuristiken und Approximationsalgorithmen von Interesse. Für das metrische TSP gibt es den 3/2 -Approximationsalgorithmus von Christofides. Für das symmetrische TSP ist die Lin-Kernighan-Heuristik eine in der Praxis bewährte Methode.
    Thema dieser Bachelor-Arbeit ist es, ähnliche Heuristiken und/oder Approximationsalgorithmenfür das asymmetrische TSP zusammenzustellen und auf Beispiel-Instanzen zu testen. 
    Abgabe: 31.08.2012
  • Bachelorarbeit: Dimensionsreduktion für ökologische Daten mit linearer und quadratischer ganzzahliger Programmierung. Im Verfahren Isomap des Lehrstuhls für ökologische Modellbildung werden Umweltdaten durch Einbettung in einen diskreten metrischen Raum und nachfolgender Dimensionsreduktion analysiert. (Siehe Anlage.) 
    Aufgabe der Bachelor-Arbeit ist Beschreibung und der Test verschiedener mathematischer Modelle für Metriken und Optimalität der Dimensionsreduktion und entsprechender Rechenverfahren. Insbesondere sollen die Optimallösungen bzgl. verschiedener Normen (euklisisch, Betragssummennorm) im Hinblick auf Robustheit gegenüber Daten-Ausreißern untersucht werden. 
    Abgabe: 31.07.2012
  • Bachelorarbeit: Varianten des Assignment-Problems mit Anwendungen in der Universitäts-Raumplanung. In einem von der Oberfrankenstiftung geförderten Forschungsprojekt (AZuR) soll u. a. ein Optimierungsverfahren entwickelt werden, dass Veranstaltungssitzungen Zeiten und Räume so zuweist, dass bestimmte Nebenbedingungen erfüllt sind (keine Überschneidungen, Doppelstunden aufeinanderfolgend u. v. a. m.). Ein Teilproblem ist die Zuweisung von Räumen für Veranstaltungen. In der einfachsten Form (alle Veranstaltungen sind nur eine Zeiteinheit lang; keine weitere Nebenbedingungen) kann das Raumzuweisungsproblem als ein Assignment-Problem formuliert werden.
    Da das aktuelle Gesamt-Modell auf einem Stundenraster arbeitet, aber die meisten Veranstaltungen Doppelstunden benutzen, sollte bei der Raumzuweisung für eine Doppelstunde kein Raumwechsel vorgenommen werden. Das lässt sich nicht (zumindestens nicht ohne Tricks) als ein elementares Assignment-Problem modellieren.
    Aufgabe der Bachelor-Arbeit ist es, Vorschläge für graphentheoretische Raumzuweisungsmodelle zu machen, die das Doppelstunden-Raumwechselverbot und evtl. ähnliche Praxisbedingungen mit einbezieht. Ferner soll untersucht werden, inwiefern sich Standard-Assignment-Algorithmen auf die neuen Modelle verallgemeinern lassen. Insbesondere ist der Komplexitätsstatus der verallgemeinerten Assignment-Probleme von Interesse. 
    Abgabe: 31.07.2012
  • Bachelorarbeit: Gewichtete Mediane -- Wieviel Einfluss hat der einzelne Bürger? In der Praxis werden recht häufig zweistufige Abstimmungsverfahren benutzt, d.h. die breite Bevölkerungsmasse bestimmt in einer ersten Stufe zunächst Repräsentaten. Dies geschieht in der Regel in grösseren Zeitabständen. Das regelmässige Tagesgeschäft wird dann von den Repräsentanten in der zweiten Stufe entschieden. Den Einfluß den der einzelne Bürger auf die Wahl seines Repräsentanten hat, wird gewöhnlich mit Hilfe der Wahrscheinlichkeit, der Medianwähler zu sein, gemessen. In der zweiten Stufe werden oft Gewichte für die einzelnen Repräsentanten verwendet, so dass der Einfluss eines Repräsentanten als Wahrscheinlichkeit der gewichtete Median der zweiten Stufe zu sein, gemessen werden kann. Das Verständnis von Zusammenhängen, die diese Einflüsse, sowohl die direkten innerhalb einer Stufe, als auch die indirekten über beide Stufen hinweg, beeinflussen, ist z.B. wichtig für das Design von fairen Abstimmungsverfahren. 
    Abgabe: 31.07.2012
  • Bachelorarbeit: Das inverse Machtindexproblem für den Nucleolus Wenn ein neues Land der Europäischen Union oder einem anderen Verbund beitritt, kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Über den Zusammenhang zwischen Bevölkerungsgröße und einem angemessenen Machtanteil ist man sich mehr oder weniger einig und sieht eine Machtzuteilung, die proportional zur Quadratwurzel der Bevölkerung ist, als "fair" an. Aber dass Macht nicht proportional zum Stimmgewicht ist, sieht man an folgendem kleinen Beispiel. Wir betrachten drei Länder A, B und C mit Stimmgewichten 6, 3 und 2. Obwohl Land B immerhin noch die Hälfte der Stimmen von Land A hat, haben bei einer 50%-Mehrheitsregelung die Länder B und C keinerlei Macht. Land A kann alle Entscheidungen alleine treffen. Für verwickeltere Situationen gibt es mehrere sogenannte Machtindizes, mit denen man eine reelle Zahl als Maß für die Macht eines Landes ausrechnen kann. Hat man sich einmal auf einen geeigneten Machtindex geeinigt, so kann man die offensichtliche Frage nach einer gerechten Verteilung der Stimmgewichte als mathematisches Optimierungsproblem formulieren. Im Rahmen dieser Bachelorarbeit soll der Stand der Dinge des inversen Machtindexproblems für den Penrose-Banzhafindex (PBI) beschrieben und für den Nucleolus als weiteres, robusteres, Machtmass übertragen werden.
    Abgabe: 16.07.2012
  • Bachelorarbeit: Dispositionsoptimierung bei einem Internetbuchhändler Ein Online-Händler verkauft einen großen Artikelkatalog in mehreren Online Shops. Das Lagern der Artikel und Versenden der Bestellungen wird von verschiedenen Fullfillment Dienstleistern durchgeführt. Bei der Zuordnung von Bestllungen zu den einzelnen Dienstleistern sind einige Restriktionen zu beachten. Nicht jeder Artikel wird von jedem Dienstleister angeboten bzw. ist nicht aktuell verfügbar; wobei die Verfügbarkeitsinformationen von unterschiedlicher Güte sind. Für bestimmte Artikel gibt es Rabattverträge, die an monatliche Mindestabnahmemengen gekoppelt sind. Wie kann man unter diesen Nebenbedingungen bzw. Unsicherheiten eine erlösmaximale Aufteilung von Bestellungen auf die verschiedenen Dienstleister bestimmen?
    Abgabe: 30.06.2012
  • Bachelorarbeit: Bender-Zerlegung des Universitätskursplanungsproblems. Im Universitätskursplanungsproblem geht es darum, Veranstaltungen Startzeiten und Räume zuzuweisen, derart, dass niemals zwei Veranstaltungen zur gleichen Zeit den selben Raum belegen und außerdem bestimmte Veranstaltungen nicht zeitgleich stattfinden. Aufgabe der Bachelor-Thesis ist es deshalb zu untersuchen, inwieweit sich dieses Problem durch Anwendung der Bender-Methode in ein Master- und ein Subproblem zerlegen lässt, um so auch realistische Instanzen lösen zu können. Abgabe: 31.07.2010
  • Bachelorarbeit: Konvergenz und Endlichkeit von Innere-Punkte-Verfahren für Lineare Programmierung. Bestimmte Innere-Punkte-Verfahren für die Lineare Programmierung sind sowohl theoretisch effizient als auch praxistauglich. Meistens werden diese Methoden in Bachelor-Vorlesungen nur in ihrer prinzipiellen Funktionsweise vorgestellt. Nachweise der Konvergenz oder Laufzeitkomplexitätsabschätzungen müssen dort ausgelassen werden. Aufgabe dieser Bachelorarbeit ist die Darstellung von primal-dualen Inneren-Punkte-Methoden zusammen mit dem Nachweis der superlinearen Konvergenz und der Endlichkeit (je nach Variante des Verfahrens). Abgabe: 31.07.2010
  •  "Lotgrößenoptimierung bei einem Textildiscounter"
    In einem Projekt zum Revenue-Management im Saisonwareneinzelhandel wurden Techniken entwickelt für die fast 1 200 Filialen des Textildiscounters NKD Vetriebs GmbH größen- und filialgenauen Nachfragebedarf anhand historicher Daten zu schätzen. Die Belieferung der Filialen geschieht in Lots mit den Restriktionen, dass es insgesamt nur wenig verschiedene Lottypen geben darf, und dass eine einzelne Filiale sehr wenig verschiedene Lottypen bei einer Belieferung erhalten darf. Im Rahmen dieser Bachelorarbeit sollen exakte und heuristische Verfahren für die folgenden zwei Probleme untersucht und implementiert werden:
    (1) Optimale Bestellpolitik von Lots bei gegebener Gesamtmenge und Bedarfsschätzung für die Filialen.
    (2) Optimale Verteilpolitik von Lots bei gegebenen Lots und gegebener Nachfrageschätzung für die Filialen.
    Bearbeitungszeitraum: 05.06.2007–04.08.2007

Abgeschlossene Masterarbeiten

  • Masterarbeit: Kompetitive Auktionen.

    Zusammenfassung: Auktionen werden verwendet, um beim Verkauf von Gütern Preise zu erzielen, die die Bezahlbereitschaft ("wahrer Preis") möglicher Kaufender voll ausnutzen. Hierbei muss beachtet werden, dass ein Mechanismus zum Einsatz kommt, bei dem es für die Interessierten gut ist, ihren wahren Preis zu offenbaren. Beim Verkauf von Rechten an digitalen Gütern sind die Reproduktionskosten des Gutes nahe Null. Auf der anderen Seite ist eine A-Priori-Verteilung der wahren Preise nicht immer zuverlässig zu schätzen. Solche braucht man aber für sogenannte Bayes’sche Auktionen. Eine Alternative wurde daher von Goldberg, Hartline, Karlin, Saks und Wright in der Literatur mit dem Konstrukt der Kompetitiven Auktionen eingeführt.

    Aufgabe dieser Masterarbeit ist es, das Konzept und die Theorie der kompetitiven Auktionen zu erklären und mit den Bayes’schen Auktionen zu vergleichen. Ferner soll ein beliebiger, möglichst realitätsnaher Anwendungsfall diskutiert werden, in dem Vorteile der kompetitiven Auktionen zum Tragen kommen könnten. Dies soll durch Simulationsrechnungen untermauert werden.

    Abgabe: 30.04.2020

  • Masterarbeit: Approximationsschemata für das Maximum-Scatter TSP auf Gittern.

    Zusammenfassung: Das Maximum-Scatter Traveling Salesman Problem (MSTSP) in der Literatur fragt nach einer Rundreise, die alle Knoten eines Graphs jeweils genau einmal besucht und deren kürzeste Kante möglichst lang ist. Motiviert ist das Problem z. B. aus der Fertigungstechnik, wenn direkt aufeinander folgende Arbeitsschritte an einem Werkstück nicht zu nah beieinander ausgeführt werden sollen. Wegen dieser Motivation sind besonders euklidische Instanzen von Interesse. In einer aktuellen Arbeit in der Literatur wurden für sogenannte doubling metrics in beliebiger Dimension (diese verallgemeinern die euklidische Metrik) effiziente (aber nach Aussage der Autoren unpraktikable) Approximationsschemata gefunden. Auf der anderen Seite konnten in der Literatur für vollständige Graphen auf regulären Gitterpunkten (Gitter-MSTSP) in Dimension zwei und drei optimale und beinahe optimale Touren identifizert werden. Aufgabe dieser Masterarbeit ist es, zu untersuchen, ob die unpraktikablen Approximationsschemata von Kozma und Mömke in der Literatur für Gitter doch umsetzbar sind und ob sie ähnliche Touren liefern wie die von Hoffmann, Kurz und Rambau in der Literatur.

    Abgabe: 29.02.2020

  • Masterarbeit: Lagerbestandsoptimierung in der High-Tech-Zulieferindustrie.

    Zusammenfassung: Jeder Industriezweig hat seine eigenen Anforderungen an eine Lagernetzbestandsplanung (engl.: Multi-Echelon Inventory Control, MEIC). Charakteristika für die High-Tech-Zulieferindustrie sind lange Lieferzeiten für eine große Anzahl an Rohstoffen und mächtige Kunden (z. B. Automobilkonzerne) mit hohen Anforderungen an kurze Lieferzeiten. Das bedeutet, dass im vom Zulieferer kontrollierten Teil der Supply-Chain die Lieferzeiten von groß nach klein "transformiert" werden müssen mit den entsprechenden Konsequenzen für die Lagerbestandsplanung. Häufig anzutreffen sind Lagerplanungssysteme basierend auf "Enterprise Resource Planning"-Software (ERP). Diese verwenden zwar die Netzstruktur des Gesamtsystems im Detail, berücksichtigen aber nicht direkt die Unsicherheit der Nachfrage. Der andere Extremfall in der Praxis ist die verteilte Verwendung von stochastischer Lagermanagement-Optimierung für jedes Lager einzeln.

    Aufgabe dieser Masterarbeit ist es, auf Basis der Literatur zu MEIC ein für diesen Industriezweig passendes Modellierungskonzept zu identifizieren und am Beispiel eines konkreten Lagernetzes umzusetzen. Um die Relevanz verschiedener Einflussfaktoren besser einzuschätzen, soll das Testnetz strukturell einem echten solchen Netz möglichst ähnlich sein. Hierfür steht Dr. Cornelius Schwarz von der Frenzelit GmbH (Bad Berneck) als Gesprächspartner zur Verfügung. Besonders interessant ist es, in wie weit ein Ansatz auf Basis von stochastischer Optimierung sich in einen bestehenden ERP-Kontext integrieren lässt (z. B. Formate von Input-Daten und Output-Daten) und welche Probleme damit überwunden werden können.

    Ziel ist es unter anderem, mit verschiedenen Modellrechnungen und Beispielbetrachtungen zu ermitteln, ob sich die modell-optimale Positionierung von Sicherheitsbeständen im Netz für bestimmte Parameterbereiche auch durch einfache Handlungsregeln (näherungsweise) umsetzen ließe. Ferner ist es interessant, das Optimierungspotenzial gegenüber einer nicht vernetzten Lagerbestandsoptimierung oder einfachen Geschäftsregeln abhängig von Modellparametern zu quantifizieren.

    Als erster Ansatz soll ein Modell auf Basis des Guaranteed-Service-Modells (GSM) oder einer Erweiterung davon, z. B. des Stochastic GSM (SGSM), entwickelt werden, die sich als Stochastisches Mixed Integer Linear Program (SMILP) formulieren lassen. Eine Literatur-Recherche soll Alternativen identifizieren, die ggf. anstelle des (S)GSM-Ansatzes verfolgt werden können.

    Abgabe: 31.08.2019

  • Masterarbeit: Heuristiken auf Basis Gemischt-Ganzzahliger Optimierung für Optimale Diplomatie.

    Optimale Diplomatie in einem Kommittee bezeichnet die Präsentation einer Meinung, repräsentiert durch eine Zahl im Einheitsintervall, in einer gegebenen Anzahl von Sitzungen, so dass in der Hegselmann-Krause-Dynamik der Meinungen der Kommittee-Mitglieder am Ende möglichst viele Kommittee-Mitglieder Meinungen in einem vorgebenen Meinungsintervall haben. Das statische Optimierungsproblem der optimalen Diplomatie ist selbst für kleine Instanzen sehr schwer zu lösen. In vielen Fällen des Kampagnen-Problems, einer Benchmark-Instanz aus der Literatur, liefert die sogenannte „Strongest-Guy“-Heuristik aber sehr gute Lösungen. Die augenblickliche Umsetzung durch eine Spezialimplementierung ist nicht sehr flexibel und braucht für große Instanzen viel Rechenzeit. Es wäre daher interessant, die Strongest-Guy-Heuristik mit einem gemischt-ganzzahligen linearen Modell (MILP) zu lösen, da sie sich dann leichter mit Variablenfixierungen, anderen Nebenbedingungen und Kostenmodellen kombinieren ließe.

    Abgabe: 28.02.2019

  • Masterarbeit: Schätzung der Ähnlichkeit von Prozessmodellen mittels Ganzzahliger Optimierung.

    Zusammenfassung: Mit Hilfe von Prozessmodellen können wiederkehrende Abläufe in Unternehmen und Behörden systematisch dokumentiert werden. Hat man zwei Prozessmodelle, z. B. für den Immatrikulationsprozess zweier Universitäten, so ist es interessant, inwiefern die tatsächlichen Prozesse ähnlich sind. Dazu versucht man die Aktivitäten des einen Modells möglichst passgenau auf die Aktivitäten des anderen Modells bijektiv abzubilden. Während bis vor kurzem hauptsächlich Bijektionen zwischen einzelnen Aktivitäten untersucht wurden, hat Baumann in der Literatur nun zum ersten Mal einen Ansatz ausgearbeitet, in dem Bijektionen von beliebigen Teilmengen einzelner Aktivitäten als Grundlage verwendet werden. Damit ist es möglich, auch die Ähnlichkeit von Prozessen aufzudecken, in deren Modellen das Vorgehen in unterschiedlicher Weise in Aktivitäten aufgeteilt worden ist. Um die passgenaueste Abbildung zwischen Teilmengen zu finden, wurde ein Ganzzahliges Lineares Programm (ILP) genutzt, dessen Lösung aber für große Prozessmodelle sehr schwierig ist.

    Aufgabe dieser Masterarbeit ist es, mit ILP-Standard-Methoden die (approximative) Lösung des Prozess-Modell-Matching-ILP zu beschleunigen bzw. für große Modelle erst zu ermöglichen.

    Abgabe: 31.01.2019

  • Masterarbeit: Fehlerschranken für Stochastische Kürzeste-Wege-Probleme.

    In der Standard-Literatur zu Markovschen Entscheidungsproblemen(MDP) (Bertsekas 2000; Puterman 1994) werden numerische Verfahren für die Berechnung der Optimalkostenfunktion (OKF) eines stationären MDP mit unendlichem Horizont und endlichen Zustands- und Kontrollräumen besprochen. Bei einem dieser Verfahren, der Wertiteration (WI), kann man nicht in endlicher Zeit erwarten, die exakte OKF zu erhalten. Die Iterierten konvergieren aber gegen die OKF, und so kann man nur mit Hilfe von Fehlerschranken, die während der Ausführung der WI berechnet werden können, sinnvoll entscheiden, wann man die WI abbricht. Für diskontierte Probleme gibt es solche Fehlerschranken, für stochastische Kürzeste-Wege-Probleme (SSP) sind die Fehlerschranken der Lehrbuchliteratur kaum sinnvoll berechenbar.

    In einer recht aktuellen Arbeit von Hansen (2017) werden nun solche Fehlerschranken für das SSP angegeben. Aufgabe dieser Masterarbeit ist es, diese neuen Fehlerschranken zu erklären und mit denen in der Lehrbuchliteratur zu vergleichen. Ferner sollen das gesamte WI-Verfahren dann verglichen werden mit dem Verfahren der Linearen Programmierung (LP). Gibt es Instanzen/Klassen von Instanzen, in denen WI der LP-Methode überlegen ist oder umgekehrt?

    Abgabe: 31.10.2018

  • Masterarbeit: Capacity Expansion Models for Robust Migration Planning.

    Die Kapazitätsplanung von großen Produktionsstätten muss auf Basis von unsicheren Zukunftsinformationen erfolgen. Gewünscht ist eine "robuste" strategische Planung der Kapazitäten für die nächsten Jahre, d. h. eine Planung, die für möglichst viele Szenarien handhabbare operative Produktionsplanung ermöglicht. In der angegebenen Literatur wurde dazu ein Konzept entwickelt, dass robuste Migrationspfade auf Basis von Markovschen Entscheidungsproblemen und nachgelagerten statistischen Schätzungen indentifiziert.

    Aufgabe dieser Masterarbeit ist zu prüfen, in wie weit das Ausgangsproblem vollständig als Mathematisches Programm modelliert werden kann. Ansätze aus der Kapazitätserweiterungsplanung mit mehrstufigen stochastischen Programmen sollen hierzu als Ansatz dienen.

    Abgabe: 31.07.2018

  • Masterarbeit: Strategieoptimierung im Tennis mit Markovschen Entscheidungsproblemen.

    Markovsche Entscheidungsprobleme (MDP) werden im Gegensatz zu Markov-Ketten im Sport seltener angewendet. Für Tennis und für Beach-Volleyball gibt es jedoch erste Ansätze. Der Beach-Volleyball-Ansatz ist dahingehend neu, dass zwei MDP zur Modellierung genutzt werden: Ein grobes zur Modellierung einer wichtigen Strategiefrage, das strategische MDP (s-MDP), und ein feines, das gameplay-MDP (g-MDP) zur Simulation der Übergangswahrscheinlichkeiten des s-MDP.

    Aufgabe dieser Masterarbeit ist es, das Konzept aus der angegebenen Literatur auf Tennis anzuwenden, zu testen und zu diskutieren, welche Vor- und Nachteile es gegenüber der Methode aus der angegebenen Literatur hat.

    Abgabe: 31.01.2018

  • Masterarbeit: Vergleich von Modellierungsansätzen für Joint-Market-Modelle.

    Energienetzbetreiber müssen auf verschiedene Einspeise- und Lastszenarien (im Folgenden kurz Szenarien) vorbereitet sein. Die Szenarien entstehen durch die Entscheidungen der Energieerzeuger und -konsumenten, die Energie in das Netz einspeisen und aus dem Netz entnehmen. Vor allem die Einspeisungen aus regenerativen Quellen unterliegen großen Schwankungen, die schlecht vorhersehbar sind, da z. B. das Wetter eine Rolle spielt. Die Endnachfrage lässt sich demgegenüber ganz gut prognostizieren. Es wird angenommen, dass die Steuerung aller aktiven Netzkomponenten so geschehen soll, dass ein Gesamtsystemoptimum erreicht wird. Der optimale Betrieb von Kraftwerken und Speicheranlagen bei gegebener Endkunden-Nachfrage wird dabei durch Varianten des Unit-Commitment-Problems (UCP) modelliert. Ein Joint-Market-Modell (JMM) fasst die UCPs aller Erzeuger eines gesamten Netzes zusammen. Die Einspeisungen und Entnahmen und die davon abhängigen, für das Gesamtsystem optimalen Aktionen der großen Energieerzeuger induzieren schließlich ein Energietransport-Szenario, dem das Netz gewachsen sein muss. Letztendlich würde man gern viele Szenarien generieren, um erstens systemrelevante Komponenten zu identifizieren und zweitens das Netz für viele mögliche Situationen fit zu machen. Das Ziel dieser Arbeit ist es zu untersuchen, ob schärfere Modellierungen von einzelnen UCP-Restriktionsgruppen helfen können, die beim Anwendungspartner TenneT vorhandenen JMM-Modelle (TenneT-JMM) auf Basis Gemischt-Ganzzahliger Optimierung (MILP) schneller zu lösen.

    Abgabe: 31.01.2018

  • Masterarbeit: Fußballstrategieoptimierung.

    Seit der Dissertation von Pfeiffer werden immer mehr Abläufe in Sportspielen mit Hilfe von Markov-Ketten simuliert. Man will damit die Sensitivität von Erfolg in Bezug auf Übergangswahrscheinlichkeiten (Pass kommt an oder nicht, Schuss kommt auf das Tor oder nicht, ...) abschätzen. Allerdings kann man damit nicht direkt optimale Spielstrategien charakterisieren. Neuer ist die Verwendung von Markovschen Entscheidungsproblemen (MDP) zur Bestimmung von optimalen Strategien. In dieser Arbeit soll ein Ansatz aus der Literatur für eine interessante strategische Frage im Fußball umgesetzt werden. Da bereits eine Master-Arbeit für die Frage ”Tikitaka oder Kick-and-Run“ vergeben wurde, soll durch Absprache mit der anderen Kandidatin eine Dopplung vermieden werden. Eine mögliche Frage, die hier untersucht werden soll, ist: Wann und wen sollte man in welcher Spielsituation für wen einwechseln? Ziel ist es, unter der Annahme, dass notwendige Daten erhoben werden können, fundierte Strategieempfehlungen zu geben.

    Abgabe: 31.12.2017

  • Masterarbeit: Das Stochastic Guaranteed Service Model in vielstufigen Lagernetzen.

    Das Stochastic Guaranteed Service Model (SGSM) ist ein zweistufiges stochastisches ganzzahliges lineares Programm mit Kompensation (SILP) zur Opimierung der Sicherheitsbestände in mehrstufigen Lagernetzen. Es erweitert das Guaranteed Service Model (GSM), das beschränkte Nachfrage und feste Transportzeiten voraussetzt. Das SGSM erlaubt beliebige Nachfragen und stochastische Transportzeiten. Zusätzliche Handlungsoptionen zur Kompensation von hoher Nachfrage und verzögerter Lieferung sind Outsourcing und/oder beschleunigte Lieferung, wofür Extra-Kosten angerechnet werden.

    Das SGSM ist in einem Punkt mathematisch nur eine Approximation: Die Nachfrage in vorgeschalteten Lagern hängt in Wahrheit von den Entscheidungen der nachgeschalteten Lager ab. Nutzt ein nachgeschaltetes Lager Outsourcing, so kommt dieser Teil der Nachfrage bei den vorgeschalteten Lagern nie an. Daher wird die tatsächlich exogene Endkundennachfrage nicht einfach propagiert. Im SGSM werden für alle Lager exogene Nachfrageverteilungen angesetzt. Dies ist eine Approximation. Die Approximation funktionierte in einer Fallstudie mit zwei Stufen sehr gut. Wie sieht es aber bei mehreren Stufen aus?

    Aufgabe dieser Masterarbeit ist es, für vielstufige Lagernetzen herauszufinden, welchen Effekt im SGSM die Ersetzung der tatsächlich endogenen Nachfragen durch exogene Nachfrageverteilungen in vorgeschalteten Lagern hat und wie man das SGSM ggf. modifizieren kann, um den Effekt zu kontrollieren.

    Abgabe: 31.10.2016

  • Masterarbeit: Optimale Diplomatie in Anbetracht unsicherer Konfidenzradien.

    In der Philosophie und in den Sozialwissenschaften untersucht man künstliche Gesellschaften. In solchen künstlichen Gesellschaften gibt es absichtlich stark vereinfachte Interaktionsmodelle, die man mit Mathematik und/oder Computer-Experimenten untersuchen kann. Entstehen dabei nicht-triviale Effekte, so hat man damit sehr grundsätzliche Strukturen identifiziert, die solche Effekte hervorrufen können. Findet man die Effekte auch in einer realen Gesellschaft vor, so ist das ein Hinweis darauf, dass die einfache Struktur eine substantielle Rolle in der realen Gesellschaft spielen könnte.Zum Beispiel werden seit vielen Jahren Modelle für die dynamische Entwicklung von Meinungen untersucht. Ein Modell für Meinungen in einem metrischen Raum (z. B. das reelle Einheitsintervall) ist die Bounded-Confidence-Dynamik (BC). Nach einer Runde Meinungsaustausch bilden sich die neuen Meinungen durch Durchschnittsbildung mit allen anderen Meinungen, die nicht weiter als ε ≥ 0 (der Konfidenzradius) entfernt sind. Diplomatie entsteht dadurch, dass man durch kontrollierte Meinungsäußerung die Entwicklung von Meinungen in eine gewünschte Richtung befördern kann. Mathematisch wurde dieses Konzept für BC erstmals als Optimalsteuerungsproblem in der grundlegensten Form präsentiert. Ein entsprechendes Benchmark-Kampagnen-Problem zeigt die Schwierigkeit auf, optimale Steuerungen zu finden.

    Aufgabe dieser Masterarbeit ist es, eigene Überlegungen anzustellen zu folgenden Erweiterungen des Optimalsteuerungsproblems in der Literatur: Was ändert sich, wenn ε dem Diplomaten unbekannt ist? Wie schlecht kann eine Kampagne werden, wenn sie optimal für ein ε ist, in der Realität sich ε' ≠ ε als zutreffend herausstellt? Ist es schlimmer, wenn ε kleiner ist als erwartet, oder ist es umgekehrt schlimmer? Wird es schlimmer, wenn alle ein individuelles ε haben?

    Abgabe: 31.01.2016

  • Masterarbeit: Das Primality-Problem für Baumsprachen.

    Das Thema dieser Masterarbeit stammt aus der theoretischen Informatik aus dem Gebiet der formalen Sprachen. In der Theorie der formalen Sprachen spielt die Operation der Konkatenation L.L' zweier Sprachen L und L' (aneinanderhängen) eine ähnliche Rolle wie die Multiplikation für natürliche Zahlen. Für eine Sprache A kann man analog zu natürlichen Zahlen die Frage nach einer nicht-trivialen Faktorisierung stellen: Ist A die Konkatenation zweier nicht-trivialer Sprachen? (Eine triviale Faktorisierung ist immer A.ε, wobei ε die leere Sprache bezeichnet, genau wie p = 1 · p immer eine triviale Faktorisierung einer natürlichen Zahl ist.) Dieses Faktorisierungsproblem ist also eine Art "Primzahltest" für formale Sprachen und wird als Primality Problem (PP) bezeichnet. Die Sprache A wird als deterministischer endlicher Automat gegeben. Nachdem in der Literatur gezeigt wurde, dass das PP PSPACE-vollständig ist, kann man dieselbe Frage auch für spezielle Sprachenklassen stellen, z. B. für die Klasse der Baumsprachen. Man vermutet, dass PP für Baumsprachen EXPTIME-vollständig ist.

    Aufgabe dieser Masterarbeit ist es auszuarbeiten, ob und wenn ja wie die Beweismethode in in der Literatur erweitert werden kann, so dass die Komplexität des PP für Baumsprachen geklärt werden kann.

    Abgabe: 29.01.2016

  • Masterarbeit: Approximation von Machtverteilungen durch gewichtete Abstimmungsregeln.

    Wenn ein neues Land der Europäischen Union oder einem anderen Verbund beitritt, kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Über den Zusammenhang zwischen Bevölkerungsgröße und einem angemessenen Machtanteil ist man sich mehr oder weniger einig und sieht eine Machtzuteilung, die proportional zur Quadratwurzel der Bevölkerung ist, als „fair“ an. Aber dass Macht nicht proportional zum Stimmgewicht ist, sieht man an folgendem kleinen Beispiel. Wir betrachten drei Länder A, B und C mit Stimmgewichten 6, 3 und 2. Obwohl Land B immerhin noch die Hälfte der Stimmen von Land A hat, haben bei einer 50 %-Mehrheitsregelung die Länder B und C keinerlei Macht. Land A kann alle Entscheidungen alleine treffen. Für verwickeltere Situationen gibt es mehrere sogenannte Machtindizes, mit denen man eine reelle Zahl als Maß für die Macht eines Landes ausrechnen kann. Hat man sich einmal auf einen geeigneten Machtindex geeinigt, so kann man die offensichtliche Frage nach einer gerechten Verteilung der Stimmgewichte als mathematisches Optimierungsproblem formulieren. Es gilt, die Abweichung zwischen dem sich aus der Bevölkerungsanzahl ergebenden, gerechten Machtanteil und der sich aus den Stimmgewichten ergebenden, tatsächlichen Macht zu minimieren. Für den Penrose-Banzhaf Index (PBI) wurde die Approximierbarkeit von Machtverteilungen durch gewichtete Abstimmungsregeln beispielsweise in der Literatur untersucht. Im Rahmen dieser Masterarbeit sollen die verwendeten Methoden auf andere Machtindizes, wie beispielsweise dem Shapley-Shubik Index oder dem Nucleolus, übertragen werden.

    Abgabe: 15.09.2015

  • Masterarbeit: Berechnung von Hammingabständen mit ganzzahliger linearer Optimierung.

    In vielen Produkten sind informationsverarbeitende Systeme integriert. Die enorme Steigerung der Performanz und Flexibilität dieser Systeme begünstigt dabei den Anstieg der Komplexität. So werden durch Steuerungen letzlich auch Aktionen durchgeführt, welche Personen in der Umgebung potentiell Schaden zufügen können. Das Themengebiet der Sicherheit beschäftigt sich mit der Fragestellung, welche Maßnahmen getroffen werden müssen, damit aus einem unerwarteten Verhalten des betrachteten Systems keine Gefahrensituation entstehen kann. Diese sogenannten Sicherheitsfunktionen werden i.d.R. durch sichere Messaufnehmer, Kommunikationseinrichtungen, Steuerungen bzw. Aktoren realisiert. Häufig kommen hier kostenintensive redundante Hardware-Strukturen zum Einsatz. Moderne Steuerungen verwenden arithmetische Codes zur Fehleraufdeckung. Als deterministische Kriterien zur Bewertung der Fehleraufdeckung werden beispielsweise die arithmetische Distanz und die minimale Hamming Distanz betrachtet. In Sicherheitsnachweisen müssen die entsprechende Werte gegenüber unabhängigen Gutachtern (TÜV, IFA, ...) nachgewiesen werden.

    Im Rahmen dieser Masterarbeit soll untersucht werden, wie die Bestimmung der Hamming Distanz bei arithmetischen Codes als ganzzahliges lineares Programm formuliert und mit den zugehörigen Methoden gelöst werden kann.

    Abgabe: 31.07.2015

  • Masterarbeit: Optimale Terminvereinbarung unter Unsicherheit: Ein Vergleich verschiedener mathematischer Modellierungsansätze. Motiviert durch die Fragestellung, wie man am besten die Kunden-Termine für Service-Techniker vereinbart, um trotz ungewisser zukünftiger Nachfragen Service-Qualität hoch und Kosten niedrig zu halten, wurde in [5] als allgemeiner Rahmen das stilisierte mathematische Optimierungsproblem Online Target Date Assignment (OnlineTDAP) eingeführt und mit Hilfe kompetitiver Analyse untersucht. Diese Art der Analyse ist nur ein möglicher Zugang zur fundierten Entscheidungsfindung unter unsicheren Informationen. Ansätze der stochastischen oder robusten Optimierung sowie eine Modellierung als stochastisches dynamisches Entscheidungsproblem kommen genauso in Frage. Sehr selten nur werden diese Modellierungs-Paradigmen anhand eines gemeinsamen Beispiels verglichen.
    Aufgabe dieser Masterarbeit ist es, geeignete Varianten des Online Target Date Assignment Problems mit stochastischer/robuster/dynamischer Optimierung zu modellieren und daraus resultierende Handlungsempfehlungen zu vergleichen. 
    Abgabe: 30.09.2014
  • Masterarbeit: Probabilistische Nebenbedingungen und zweistufige stochastischen Optimierungsproblemen mit Kompensation zur Optimierung mehrstufiger Lagernetze. In vielen aktuellen Texten wird das Stochastic Guaranteed Service Model (SGSM) zur Berechnung von Sicherheitsbeständen in mehrstufigen Lagernetzen vorgestellt. Es ist eine Erweiterung des klassischen Guaranteed Service Model (GSM) um eine stochastische Komponente und eine Kompensationsstufe (SLP). Unter anderem wird ein Vergleich der möglichen Optimallösungen vorgenommen. Da das GSM interpretiert werden kann als ein deterministisches Äquivalent zu einem Optimierungsproblem mit probabilistischen Nebenbedingungen (PNB), liefert dieser Vergleich auch einen Zusammenhang von zweistufigen SLPs mit PNBs. In einem Standardwerk zur stochastischen linearen Programmierung wird beleuchtet, wie man deterministische äquivalente Formulierungen für PNBs erhalten kann. Unter anderem wird ein klassischer Zusammenhang mit SLPs dargestellt.
    Ziel dieser Masterarbeit ist es, die Interpretation des GSM als PNB handwerklich sauber aufzuarbeiten. Ferner soll geklärt werden, in welcher Allgemeinheit die speziellen Zusammenhänge für den Vergleich von PNB mit SLPs gelten.
    Abgabe: 30.09.2014
  • Masterarbeit: Netzwerkcodes. Netzwerkcodes stellen ein Verfahren zur Verfügung, Daten mit der Möglichkeit, Übertragungsfehler zu korrigieren, zu kodieren. In dieser Arbeit sollen sogenannte constant dimension codes, eine Form dieser Netzwerkcodes, mit Techniken der ganzzahligen linearen Optimierung untersucht werden. Ziel ist es möglichst große Codes zu finden. Diese sind wichtig, da größere Codes weniger zusätzliche Daten erfordern, um die gleiche Anzahl an Ausgangsdaten zu kodieren. 
    Abgabe: 19.07.2014
  • Masterarbeit: Optimierte Strategien für Sportspiele auf Basis Markovscher Entscheidungsprobleme. In Zusammenarbeit mit dem Institut für Sportwissenschaft (IfS) der Universität Bayreuth soll die Evaluierung und Optimierung von Strategien in Sportspielen auf Basis Markovscher Entscheidungsprobleme untersucht werden. 
    Abgabe: 28.02.2014
  • Masterarbeit: CHAMP - Control of Heat in Automatic Model Production - Sequencing
    Abgabe: 06.03.2013
  • Masterarbeit: Die Integer-L-Shaped-Methode. Die L-Shaped-Methode ist eine spezielle Form der iterativen Lösung der Benders-Zerlegung eines stochastischen linearen Programms in extensiver Form. Dieses Verfahren überträgt sich nicht unmittelbar auf den Fall ganzzahliger linearer Programme. In modifizierter Form erhält man allerdings eine Methode für den Fall vollständiger Kompensation. Thema dieser Masterarbeit ist Entwurf und Implementierung einer solchen L-Shaped-Methode für stochastische ganzzahlige lineare Programme mit vollständiger Kompensation sowie Testrechnungen auf verschiedenen Beispielanwendungen. Abgabe: 30.09.2011

Abgeschlossene Zulassungsarbeiten

  • Zulassungsarbeit: Multiplikation von Zahlen und Polynomen. Das schriftliche Multiplizieren von Zahlen lernt man bereits in der Grundschule. Auch in vielen anspruchsvolleren mathematischen Algorithmen sind Langzahlmultiplikationen ein essentieller Bestandteil. Die Berechnung der Kreiszahl π auf fünf Billionen Ziffern wäre ohne effiziente Multiplikationsalgorithmen nicht möglich. Die Multiplikation von Polynomen lässt sich konzeptionell etwas einfacher beschreiben, weil man sich hier nicht um Überträge kümmern muss. Ein Maß für die Effizienz von Algorithmen liefert die sogenannte Komplexitätstheorie. In dieser Sprechweise kann man sagen, dass die Schulmultiplikationsmethode einen quadratischen Aufwand benötigt. Durch die Verwendung mathematischer Resultate lassen sich effizientere Multiplikationsalgorithmen entwickeln. Dies soll im Rahmen dieser Zulassungsarbeit ausführlich dargestellt werden. Die zugrunde liegenden notwendigen mathematischen Begriffsbildungen sollen zwar auf der einen Seite präzise und exakt definiert, auf der anderen Seite aber auch anschaulich erklärt werden. 
    Bearbeitungszeitraum: 01.03.2015–31.08.2015
  • Zulassungsarbeit:Kombinatorik, Wahrscheinlichkeitsrechnung und Spieltheorie in der gymnasialen Mittelstufe anhand von Poker. Das Kartenspiel Poker erfreut sich seit einiger Zeit einer immer stärkeren Beliebtheit. Mittlerweile gibt es eine Reihe von Leuten, die von Siegprämien bei Pokertunieren leben können. Offensichtlich kann man Poker mehr oder weniger geschickt spielen. Dass Poker trotz Glücks- und Zufallskomponenten ein sehr strategisches Spiel ist, kann man u.a. daran sehen, wie viele Schachspieler sich mittlerweile, und sei es auch nur nebenbei, mit Poker beschäftigen. Der Schachgroß meister Matthias Wahls betreibt beispielsweise die Internetseite www.pokerstrategy.de
    Abgabe: 01.04.2010
  •  Strukturisomere der Alkane. Chemische Verbindungen, welche die gleiche Summenformel aber unterschiedliche Verknüpfungen besitzen, werden Strukturisomere genannt. Eine Andersartigkeit in der Anordnung bzw. Verknüpfung führt teilweise zu abweichenden chemischen, physikalischen oder biologischen Eigenschaften. Ein Beispiel für eine Klasse chemischer Verbindungen sind die sogenannten Alkane (früher Paraffine). Dies sind gesättigte Kohlenwasserstoffe mit Summenformel CnH2n+2.
    In vielen Chemiebüchern findet man Tabellen über die Anzahl der Strukturisomere von Alkanen aus n C-Atomen, siehe ggf. diese ausführliche Tabelle für bis zu 100 C-Atomen. Wie man auf diese Zahlen kommt wird dagegen nicht erwähnt.
    Da die Verbindung der C-Atome bei Alkanen eine Baumstruktur besitzt, ist es hier noch relativ einfach die Anzahl der Strukturisomere zu berechnen bzw. die Strukturisomere computergeneriert zu erzeugen. Im Rahmen dieser Zulassungsarbeit sollten die notwendigen mathematischen und algorithmischen Grundlagen dargestellt werden. 
    Bearbeitungszeitraum: 22.06.2009–29.09.2009
  • Spieltheorie – Eine anschauliche Einführung mit anwendungsbezogenen Beispielen aus Ökonomie und Alltag
    Die Methoden der Spieltheorie können bei vielen praktischen Problemen auftreten. Sie gibt Antworten auf Fragen wie, "Warum ist es bei der Verkehrsplanung nicht immer besser, zusätzliche Straßen zu bauen?" oder "Warum nähern sich die großen politischen Parteien mit ihren Konzepten so stark an?". Im Rahmen einer Zulassungsarbeit soll anhand einer zu entwickelnden anschaulichen Einführung in die Spieltheorie aufgezeigt werden, dass dieses Thema auch für den Schulunterricht geeignet ist. Folgerungen aus der Anschaung heraus sollen das sonst häufig vertretene Satz-Beweis-Prinzip ersetzen. Abgerundet wird die Arbeit durch Darstellungen von Problemen aus der Praxis.
    Abgabe: 20. Oktober 2006
  • Lineare Optimierung in der Schule
    Die Lineare Optierung ist aus der betriebswirtschaftlichen Praxis nicht mehr wegzudenken. Im Rahmen einer Zulassungsarbeit soll anhand einer zu entwickelnden anschaulichen Einführung in die Lineare Optimierung aufgezeigt werden, dass dieses Thema auch für den Schulunterricht geeignet ist. Folgerungen aus der Anschaung heraus sollen das sonst häufig vertretene Satz-Beweis-Prinzip ersetzen. Abgerundet wird die Arbeit durch Darstellungen von Optimierungsproblemen aus der Praxis.
    Bearbeitungszeitraum: ?–?

Abgeschlossene Diplomarbeiten

  • Diplomarbeit: Algorithmik und Komplexität von Universitätskurs-Raumzuweisungs-Problemen.

    In einem von der Oberfrankenstiftung geförderten Forschungsprojekt wurden Methoden für die Universitätskursstunden- und -raumplanung (UCTP) entwickelt. Die Aufgabe der Raumzuweisung bei gegebener Terminplanung ist schon für sich allein genommen unter praktischen Nebenbedingungen nicht unbedingt einfach zu bewältigen, da es sich wegen der Restriktionen nicht immer um ein klassisches Assignment Problem (AP) handelt. Hierbei müssen den bereits mit Terminen versehenen wöchentlichen Sitzungen der Kurse Räume zugewiesen werden, so dass einem Raum zu jeder Zeit maximal eine Sitzung zugewiesen wird und so dass die Anforderungen der Sitzungen an den Raum erfüllt werden. Ferner kann es noch Restriktionen zu Entfernungen o. ä. geben. Interessante Einblicke bzgl. praxisrelevanter Restriktionen geben die Regeln und Instanzen der International Timetabling Competition in der angegebenen Literatur.

    Ziel der Diplomarbeit ist es, herauszufinden, welche Varianten des AP in einer praxisrelevanten Raumplanung eine Rolle spielen und welchen Komplexitätsstatus die entsprechenden Modelle haben.

    Abgabe: 08.07.2014

  • Diplomarbeit: Überblick über Methoden zur Lösung des Universitätskursstundenplanungsproblems Im Universitätskursplanungsproblem geht es darum, Veranstaltungen Startzeiten und Räume so zuzuweisen, dass niemals zwei Veranstaltungen zur gleichen Zeit den selben Raum belegen und außerdem bestimmte Veranstaltungen nicht zeitgleich stattfinden. Praktische Probleminstanzen hiervon lassen sich jedoch nicht durch direktes Anwenden von Standardlösern bewältigen. In der Literatur findet sich deshalb eine Vielzahl von Techniken, die im Stande sind dieses Problem auch für realistische Daten zu lösen. In dieser Diplomarbeit soll ein Überblick über exakte mathematische Verfahren zur Lösung des Universitätskursstundenplanungsproblems erstellt werden. 
    Abgabe: 31.03.2013
  • Diplomarbeit: Lokale Politik-Evaluierung für Paging. Die Berechnung optimaler Politiken für diskontierte Markovsche Entscheidungsprobleme mit unendlichem Horizont ist für interessante Problem oft nicht möglich wegen zu großer Zustandsräume. In [5] wird ein Verfahren beschrieben, wie man mit der LP-Methode und dynamischer Spaltengenerierung trotzdem noch rigorose Informationen über die Qualität von gegebenen Politiken in Bezug auf eine unbekannte optimale Politik gewinnen kann. Auf der anderen Seite gibt es Online-Probleme, für die kompetitive Analyse nur ein schwaches Entscheidungskriterium für die Auswahl von Politiken liefert.
    Aufgabe dieser Diplomarbeit ist es, dieses Verfahren auf das typische Online-Problem ”Paging“ und die gängigen Politiken anzuwenden. 
    Abgabe: 31.10.2012
  • Diplomarbeit: Symmetrische ganzzahlige lineare Programme mit Anwendungen in der Kodierungstheorie Bei vielen kombinatorischen motivierten Modellierungen in der Sprache der ganzzahlig-linearen Programmierung gibt es vielfältige Symmetrien in der Formulierung. Das heißt, dass es zu jeder zulässigen Lösung eine ganze Menge an äquivalenten zulässigen Lösungen mit demselben Zielfunktionswert gibt. Diese Eigenschaft ist für die Standard-ILP-Löser wie beispielsweise CPLEX oder Gurobi sehr schlecht, weil sie immer wieder dieselben Schranken berechnen.
    Der optimale Ausweg wäre sich die Symmetrie beim Branch-and-Bound-Baum zu Nutze zu machen. Zu eben diesem Thema gibt es ein paar Arbeiten, die im Rahmen dieser Diplomarbeit anhand zweier spezifischer Anwendungsprobleme aus der Kodierungstheorie beschrieben und implementiert werden sollen.  Abgabe: 30.06.2012
  • Diplomarbeit: Gültige Ungleichungen des Linear Ordering Polytopes für das Laserschweißproblems Beim Laserschweißproblem mit festen Touren (LSP-T) teilen sich Industrieroboter gewisse Ressourcen. Beispiele hierfür sind gemeinsam genutzte Laserquellen für die Bearbeitung von Schweißnähten oder Ressourcen zur Kollisionsvermeidung. Wenn zwei Roboter gleichzeitig mit derselben Laserquelle schweißen wollen oder gleichzeitig in einen kritischen Bereich fahren, in dem es zu einer Kollision zwischen ihnen kommen kann, so liegt ein Ressourcenkonflikt vor. Das Ziel des LSP-T besteht darin, die Roboter so zu synchronisieren, dass keine Ressourcenkonflikte auftreten und der Makespan minimal ist.
    Aufgabe der Diplomarbeit ist zu untersuchen, ob sich für das Linear Ordering Polytope gültige Ungleichungen zur Lösung des Laserschweißproblems verwenden lassen. Abgabe: 31.12.2011
  • Diplomarbeit: Windenergieprognosen -- Potenzial stochastischer Optimierung. An der European Energy Exchange (EEX) Energiebörse mit Sitz in Leipzig werden tagtäglich Preise für Energie ausgehandelt. Durch das Erneuerbare-Energien-Gesetz besitzen Windkraft und andere erneuerbare Energien gegenüber fossilen Brennstoffen und Kernkraft eine Vorrangstellung. In Folge dessen hängt der Strompreis an der EEX sehr stark von der aktuellen Leistung von Kraftwerken erneuerbarer Energien wie Windkraftwerken ab. Eine möglichst genaue Prognose der zukünftig produzierten Leistung ist somit u.a. für Stromnetzbetreiber essentiell. Hat man mehrere Prognosen zur Verfügung, so stellt sich die Frage, wie man aufgrund dessen optimal (z.B. über Ankaufs- und Verkaufsmengen) entscheiden soll. Eine Möglichkeit ist es, die Prognosen zu einer einzigen (z.B. als gewichtete Summe) Prognose zusammenzufassen und anschließend optimal zu entscheiden. Anhand historischer Daten kann man versuchen die vorhandenen Freiheitsgrade möglichst effektiv zu nutzen. Ein anderer Ansatz mit dieser mehrdeutigen Information umzugehen, ist die unsichere Information in die Optimierung mit einzubeziehen anstatt sie vorab zu eliminieren -- sogennante stochastische Optimierung. Abgabe: 12.12.2011
  • Diplomarbeit: Logistische Regression zur Schätzung von Verkäufen bei einem TextildiscounterAn der Universität Bayreuth läuft seit 2007 ein von der Bayerischen Forschungsstiftung gefördertes Praxisprojekt zur Entwicklung eines Integrierten Systems zur Größen- und Preisoptimierung bei einem Textildiscounter (DISPO). Grundlage ist ein stochastisches gemischt-ganzzahliges Programm für die Warenverteilung, in dem Preisreduzierungen als Kompensationsentscheidung für Fehlbelieferungen dienen. Entscheidungen erfolgen auf Grundlage geschätzter Verkäufe pro Filiale und Größe abhäangig von Verkaufswoche, Preis und Szenario. Wegen geringer Verkaufszahlen pro Filiale schlagen klassische lineare Regressionsverfahren fehl. Momentan ist daher eine im Rahmen des Projekts entwickelte empirische Nachfrageschätzung im Einsatz. Verglichen soll diese nun mit einer nichtlinearen klassischen Methode zur Nachfrageschätzung bei binären bzw. ordinalen abhängigen Variablen, der logistischen Regression. Aufgabe der Diplomarbeit ist nun die Entwicklung, die Analyse, die Implementierung und die experimentelle Untersuchung einer Schätzung der Verkäufe durch logistische Regression anhand realer Daten. Abgabe: 30.11.2011
  • Diplomarbeit: Optimalsteuerung von Meinungsbildungsdynamiken. Viele Prozesse unserer Welt unterliegen einer Meinungsdynamik. Dies bedeutet, dass jedes einzelne Individuum eine Meinung zu einem gegebenen Thema hat, sich diese aber durch Kommunikation mit anderen Individuen im Laufe der Zeit ändert. Ein theoretisches Modell Meinungsbildungsdynamiken zu beschreiben ist das sogennannte Bounded Confidence-Modell. Hierbei wird die eigene Meinung nur von anderen Meinungen beeinflusst, die nicht zu stark hiervon abweichen. Anhand dieses Modells lassen sich schon ein paar Phänomene von Meinungsbildungsdynamiken analysieren. Richtig spannend wird es allerdings, wenn man versucht die Meinungsbildungsdynamik zu beeinflussen. Abgabe: 07.10.2011
  • Diplomarbeit: Das Inverse Machtindexproblem. Tritt neues Land der Europäischen Union oder einem anderen Verbund bei, so kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Allgemein anerkannt ist, dass bevölkerungsreiche Länder mehr Macht haben sollen als bevölkerungsarme Länder. Auch über den Zusammenhang zwischen Bevölkerungsgröße und einem angemessenen Machtanteil ist man sich mehr oder weniger einig und sieht eine Machtzuteilung, die proportional zur Quadratwurzel der Bevölkerung ist, als fair an.
    Um Machtanteile zu messen gibt es mehrere sogenannte Machtindizes. Hat man sich einmal auf einen geeigneten Machtindex geeinigt, so kann man die offensichtliche Frage nach einer gerechten Verteilung der Stimmgewichte als mathematisches Optimierungsproblem formulieren. Es gilt, die Abweichung zwischen dem sich aus der Bevölkerungsanzahl ergebenden, gerechten Machtanteil und der sich aus den Stimmgewichten ergebenden, tatsächlichen Macht zu minimieren.
    Im Rahmen dieser Diplomarbeit sollen fortgeschrittene Methoden der Ganzzahligen Linearen Optimierung auf eine ILP-Formulierung des Problems angewendet werden, mit dem Ziel beispielhaft eine faire (inkl. Gütegarantien) Stimmgewichtsverteilung der EU27 zu berechnen bzw. die aktuellen Rechengrenzen weiter zu verschieben. Abgabe: 31.07.2011
  • Diplomarbeit: Effizientes Lernen monotoner boolscher Funktionen. In komplexen Systemen (mit Ressourcenbeschränkungen) und vielen Einzelkomponenten kann es zu Fehlern kommen, wenn bestimmte Kombinationen von Einzelkomponenten gleichzeit aktiv sind. Als anschauliches Beispiel kann man sich einen Computer vorstellen, auf dem unterschiedliche Programme ausgeführt werden können, beispielsweise ein Textverarbeitsprogramm, ein Internetbrowser, ein Tabellenkalkulationsprogramm und ein Graphikprogramm. Nehmen wir einmal an, dass der Computer abstürzt, wenn alle vier Programme gleichzeitig ausgeführt werden, so sind wir daran interessiert herauszufinden, bei welchen Kombinationen der Computer abstürzt und bei welchen er stabil weiter läuft.
    Bei N verschiedenen Programmen gibt es theoretisch 2N Kombinationen, in denen der Computer entweder abstürzen oder stabil weiter laufen kann. Es ist aber nicht unrealistisch eine gewisse Monotonieanzunehmen: Läuft der Computer bei gleichzeitiger Ausführung der Textverarbeitung und der Tabellenkalkulation weiter, so ist davon auszugehen, dass er auch bei alleiniger Ausführung eines der beiden Programme stabil weiter läuft. Führen dagegen bereits die Programme Textverarbeitung, Tabellenkalkulation und der Internetbrowser zu einem Absturz, so wird das System auch bei gleichzeitiger Verwendung aller vier Programm abstürzen. Mathematisch lässt sich das Fehlerverhalten eines solchen Systems als monotone boolsche Funktion beschreiben.
    Ziel ist es, die monotone boolsche Funktion eines Systems durch Auswertungen an Stützpunkten vollständig zu bestimmen. Hier kann man sich vorstellen, dass man beispielsweise ein Experiment durchführt (die Programme in der gewählten Kombination auf dem Rechner laufen lassen und beobachten, was passiert) oder Experten befragt. Da eine solche Auswertung in der Regel teuer ist, soll die Anzahl der notwendigen Auswertungen minimiert werden. Abgabe: 30.06.2011
  • Diplomarbeit: Methoden der Benders-Zerlegung für das Universitätskursplanungsproblem. An der Universität Bayreuth läuft seit 2010 ein von der Oberfrankenstiftung gefördertes Projekt zur automatischen Unterstützung der Zeit- und Raumplanung für Lehrveranstaltungen. Die Planungsaufgabe ist in der mathematischen Literatur bekannt als das Universitätskursplanungsproblem. Ein Modellierungsansatz von Lach und Lübbecke hat sich als ein Spezialfall der Generierung von Benders-Schnitten herausgestellt. Daher wird diese Technik nun genauer untersucht. Aufgabe der Diplomarbeit ist der Entwurf, die Analyse, die Implementierung und die experimentelle Untersuchung verschiedener Verfahren zur Auswahl von Benders-Schnitten für das Universiätskursplanungsproblem. Abgabe: 31.03.2011
  • Diplomarbeit: Mechanismus-Design. Aufgabe ist eine Übersicht über Mechanismus-Design, die zugrundeliegenden mathematischen Strukturen und beispielhafte Anwendungen. Zusammenhänge zu Markovschen Entscheidungsproblemen (MDP) sollen hergestellt werden. Eine mögliche weiterführende Aufgabe ist folgende: Für das Universitätskursstundenplanungsproblem sollen mögliche Einflussfaktoren des Mechanismus-Design erläutert werden, die aus dem Zusammenspiel von vielen Akteuren mit individuellen Interessen entstehen und Einfluss z. B. auf die Korrektheit von dezentral eingegebenen Daten haben können. Abgabe: 30.11.2010
  • Diplomarbeit: Scanstrategien beim Strahlschmelzen. Um kundenindividuelle Produkte mit hoher Komplexität in immer kürzer werdenden Entwicklungs- und Produktionszyklen aus unterschiedlichen metallischen Werkstoffen zu fertigen, werden sogenannte Strahlschmelzverfahren eingesetzt. Das Grundprinzip verschiedener Technologien ist dabei das selektive Verfestigen einkomponentiger Pulverwerkstoffe mittels einer Laserstrahlquelle. Durch Aufbringen mehrer Pulverschichten können dreidimensionale Objekte aus unterschiedlichen metallischen Werkstoffen gefertigt werden. Die durch den Laser lokal eingebrachte hohe Energie kann zu Verzügen und Eigenspannungen führen (Stichwort Temperature-Gradient-Mechanism – TGM). Die Reihenfolge (auch Scanstrategie genannt), in der die Pulverwerkstoffe verfestigt werden, spielt somit eine große Rolle. Eine Möglichkeit, Verzügunge und Eigenspannungen zu vermeiden, könnte sein, Scanstrategien zu verwenden, welche einen möglichst großen Abstand zwischen zwei zeitlich aufeinander folgenden Verfestigungen besitzen. Mathematisch führt diese Überlegung beispielsweise zum Maximum Scatter TSP Problem. Im Rahmen der Diplomarbeit soll das Anwendungsproblem und die zugrunde liegende Physik beschrieben werden (Stichwort: instationäre Wärmeleitungsgleichung). Durch Vereinfachen der Problemstellung (Diskretisierung, Linearisierung, zweidimensionale Sichtweise, ...) sollen diskrete Optimierungsprobleme extrahiert werden, die beispielsweise mit Methoden der ganzzahligen linearen Optimierung gelöst werden können. Die Betrachtung stark vereinfachter aber charakteristischer Teilprobleme kann zum Entwickeln geeigneter Heuristiken verwendet werden. Abgabe: 31.10.2010
  • Diplomarbeit: Approximationsalgorithmen für das Lottyp-Designproblem Viele praktisch bedeutsame Optimierungsprobleme sind NP-schwer. Dies bedeutet für die Praxis, dass es, zumindest falls P!=NP gilt, keine Lösungsalgorithmen mit polynomialer Laufzeit in der Eingabegröße für sie geben kann. Ein pragmatischer Ausweg sind sogenannte Approximationsalgorithmen.
    Eine Klasse von Optimierungsproblemen sind die sogenannten Facility Location- und K-Median-Probleme, welche bei einem aktuellen Industrieprojekt des Lehrstuhls in der Praxis auftreten. Konkret geht es um einen Textildiscounter mit über tausend Filialen in Deutschland und Österreich. Um die Logistikkosten gering zu halten, finden Einmalbelieferungen der Filialen in Lotpaketen statt. Jede Filiale bekommt ggf. mehrere Pakete eines Lottyps geliefert. Um Komplexität in der Logistik zu vermeiden, ist die Anzahl der insgesamt verwendeten Lottypen bei einer Artikellieferung durch eine kleine Zahl, wie z.B. 4 beschränkt.
    Bei gegebenen größen- und filialgenauen Bedarfen stellt sich nun die Frage, wie man mithilfe von Lotpaketen den Bedarf bestmöglich approximiert. Da dieses Optimierungsproblem im Allgemeinen NP-schwer ist, müssen hier Heuristiken und Approximationsalgorithmen in Anschlag gebracht werden.
    Bearbeitungszeitraum: 01.03.2010–31.10.2010
  • Diplomarbeit: Robuste Ganzzahlige Lineare Optimierung. Optimierung basiert in der Praxis auf Daten, die häufig nur geschätzt werden können. Beispiel: Kundennachfrage. Daher liefern deterministische Optimierungsmodelle oft Handlungsempfehlungen, die für die dann tatsächlich eintretenden Daten nicht unbedingt optimal sein müssen. Hat man keine Informationen über die stochastische Verteilung der Daten, so kann man mit Hilfe der robusten Optimierung dennoch eine im schlechtesten Fall optimale Lösung generieren. Aufgabe der Arbeit ist es, die Theorie der Robustifizierung von Optimierungsmodellen zu erläutern und diese in einem realen Fallbeispiel (optimierte Warenverteilung für einen Textildiscounter) anzuwenden. Dies beinhaltet Robustifizierung eines Modells, Datenerhebung, Implementierung und Testrechnungen sowie eine Diskussion der Ergebnisse im Vergleich zu szenariobasierter stochastischer Optimierung. Abgabe: 31.03.2010
  • Graphen mit Einheitsabständen. In der geometrischen Graphentheorie beschäftigt man sich mit Einbettungen von Graphen in die euklidische Ebene mit vorgegebenen Kantenlängen. Ein Spezialfall hiervon ist, dass alle Kanten Länge 1 besitzen. Anschulich können diese Graphen auch mit Streichhölzern gelegt werden. Im Rahmen dieser Diplomarbeit sollen z.B. Methoden entwickelt werden, mit denen man in vielen Fällen algorithmisch schnell zeigen kann, dass es für einen gegebenen Graphen keine Einbettung in die euklidische Ebene mit Einheitsabständen geben kann. Eine recht spezielle Frage ist, ob der sogennante Harborth-Graph der kleinste vierreguläre planare Graph mit Einheitskanten ist.
    Bearbeitungszeitraum: 01.01.2009–31.07.2009
  • Diplomarbeit: Approximationsalgorithmen für Facility Location und K-Median Viele praktisch bedeutsame Optimierungsprobleme sind NP-schwer. Dies bedeutet für die Praxis, dass es, zumindest falls P!=NP gilt, keine Lösungsalgorithmen mit polynomialer Laufzeit in der Eingabegröße für sie geben kann. Ein pragmatischer Ausweg sind sogenannte Approximationsalgorithmen.
    Eine Klasse von Optimierungsproblemen sind die sogenannten Facility Location- und K-Median-Probleme, welche bei einem aktuellen Industrieprojekt des Lehrstuhls in der Praxis auftreten. Konkret geht es um einen Textildiscounter. Um die Logistikkosten gering zu halten, finden Einmalbelieferungen der Filialen in Lotpaketen statt. Jede Filiale bekommt ggf. mehrere Pakete eines Lottyps geliefert. Um Komplexität in der Logistik zu vermeiden, ist die Anzahl der insgesamt verwendeten Lottypen bei einer Artikellieferung durch eine kleine Zahl beschränkt.
    Bei gegebenen größen- und filialgenauen Bedarfen stellt sich nun die Frage, wie man mithilfe von Lotpaketen den Bedarf bestmöglich approximiert. Da dieses Optimierungsproblem im Allgemeinen NP-schwer ist, müssen hier Heuristiken und Approximationsalgorithmen in Anschlag gebracht werden.
    Bearbeitungszeitraum: 01.02.2009–31.07.2009
  •  Ein Branch & Price-Verfahren zur optimierten Einsatzplanung von Winterdienstfahrzeugen. In einer vorangegangenen Arbeit, konnte ein Modell entwickelt werden, welches ermöglichte, die Gegebenheiten des Winterdienstes der Stadt Bayreuth abzubilden. Unter anderem ist dabei verlangt, dass bestimmte Straßen aufgrund einer gegebenen Priorität früher als andere geräumt werden müssen. Die Komplexität des resultierenden Modells macht es nötig, Verfahren anzuwenden, die über Standardlöser hinausgehen.
    Aufgabe dieser Diplomarbeit ist es, das mathematische Modell für die Winderdiensteinsatzplanung aus der Vorläufer-Diplomarbeit in ein Branch & Price-Verfahren umzusetzen, zu analysieren, zu implementieren, auf realen Daten des Winterdienstes der Stadt Bayreuth zu testen und ggf. anzupassen.
    Bearbeitungszeitraum: 01.10.2008–31.03.2009
  • Diplomarbeit: Ganzzahlige Polynomiale Programmierung auf Basis algebraischer Strukturen. Nicht-standard-Ansätze in der Ganzzahligen Optimierung auf Basis algebraischer Strukturen sind trotz ihres beweisbar effizienten Laufzeitverhaltens in fester Dimension im industriellen Umfeld bislang noch nicht konkurrenzfähig. In Einzelfällen sind sie aber besser geeignet als die Standard-Branch- and-Bound-Verfahren. Vor allem bieten sie aber mehr Möglichkeiten der Verallgemeinerung auf nicht-lineare Probleme. Ein erstes Resultat in dieser Richtung wurde vor kurzem in [2] vorgestellt: Ein voll-polynomiales Approximationsschema für polynomiale gemischt-ganzzahlige Programmierung in fester Dimension.
    In dieser Arbeit sollen die Hintergründe, Ideen und Strukturen, die zu diesem Resultat geführt haben, erläutert werden. Ferner soll das tatsächliche Verhalten durch Implementierung und Testrechnung untersucht werden.
    Bearbeitungszeitraum: 24.06.2008–23.12.2008
  • Enumeration einfacher Spiele mit Anwendungen in der Stimmgewichtsverteilung, Mit Hilfe von sogenannten einfachen Spielen kann man Machtverhältnisse bei Abstimmungen mit Stimmgewichten beschreiben. Dass Macht nicht proportional zum Stimmgewicht ist, sieht man an folgendem kleinen Beispiel. Wir betrachten drei Länder A, B und C mit Stimmgewichten 6, 3 und 2. Obwohl Land B immerhin noch die Hälfte der Stimmen von Land A hat, haben bei einer 50\%-Mehrheitsregelung die Länder B und C keinerlei Macht. Land A kann alle Entscheidungen alleine treffen. Die zugrunde liegende diskrete Struktur sind sogenannte Antiketten bzw. monotone boolsche Funktionen.
    Aufgabe dieser Diplomarbeit ist es Verfahren weiter zu entwickeln, um einfache Spiele bis auf Isomorphie vollständig zu enumerieren.
    Bearbeitungszeitraum: 01.04.2008–30.09.2008
  • Machtindizes - Optimierung von Stimmgewichten, Wenn ein neues Land der Europäischen Union oder einem anderen Verbund beitritt, kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Sind die Stimmgewichte gegeben, so kann man den Machtanteil der einzelnen Länder über sogenannte Machtindizes ausrechnen. In der politikwissenschaftlichen Literatur lassen sich Analysen finden, wieviel Macht man einem Land in Abhängigkeit seiner Bevölkerungsgröße geben sollte, so dass kein Bewohner eines Landes übervorteilt wird. Diese Optimalverteilung gilt es mit ganzzahligen Stimmgewichten zu approximieren.
    Aufgabe dieser Diplomarbeit ist es Verfahren zu entwickeln un zu implementieren, mit denen man dieses Optimierungsproblem in angemessener Zeit optimal oder inklusive einer Gütegarantie lösen kann.
    Bearbeitungszeitraum: 01.04.2008–30.09.2008
  • Optimierung von Patientenrouting und Ressourcen-Allokation in Krankenhäusern, Im Planungsprozess eines Krankenhauses sollen Optimierungspotentiale aufgespürt werden, die mit Methoden der Mathematischen Programmierung gehoben werden können. Allgemein sollen bei einer gegebenen Reihenfolge von Behandlungsschritten für einen Patienten mit einer bestimmten Einlieferungsdiagnose oder Terminbehandlung diese Schritte terminiert werden und sichergestellt werden, dass die für den jeweiligen Behandlungsschritt notwendigen Ressourcen pünktlich an Ort und Stelle sind (vereinfachter Spezialfall der Einbettung eines Patientenpfades in das Ressourcennetz des Krankenhauses, denn Patientenpfade können im Allgemeinen ganze Szenariobäume sein).
    Aufgabe dieser Diplomarbeit ist die mathematische Modellierung dieser Patienten-Ressourcen-Termin-Zuordnung, die Entwicklung und Implementierung von Algorithmen zur Lösung der Modelle sowie Testrechnungen, möglichst auf Anwenderdaten.
    Bearbeitungszeitraum: 01.12.2007–31.05.2008
  • Optimierte Einsatzplanung von Winterdienstfahrzeugen, Der Winterdienst der Stadt Bayreuth hat die Aufgabe, die wichtigsten Straßen in Bayreuth jeden Tag bis zu einer bestimmten, von der Priorität der Straße abhängigen Uhrzeit zu räumen und zu streuen. Das bedeutet, dass für die verfügbaren Räum- und Streufahrzeuge Touren geplant werden müssen, so dass alle Straßen einer jeden Prioritätsstufe jeweils rechtzeitig frei sind. Momentan werden diese Planungen vor der Winterzeit manuell durchgeführt.
    Aufgabe dieser Diplomarbeit ist die mathematische Modellierung der Winterdiensteinsatzplanung, die Entwicklung und Implementierung von Algorithmen zur Lösung der Modelle sowie Testrechnungen auf Anwenderdaten. Letzteres erfordert auch die Mitwirkung bei der Datenerfassung des Praxispartners, denn wegen der Handplanung liegen nicht alle relevanten Daten in elektronisch verwertbarer Form vor.
    Bearbeitungszeitraum: 01.12.2007–31.05.2008
  • Optimierte Warenverteilung für Textildiscounter, In einem Kooperationsprojekt mit dem Textildiscounter NKD Vertriebs GmbH stellt sich die folgende Aufgabe der optimalen Warenverteilung:
    Gegeben sei eine Gesamteinkaufsmenge für einen Artikel; ferner gebe es Schätzungen für die fraktionale Nachfrage nach einem Artikel, und zwar für jede Konfektionsgröße und für jede der über Filialen; weiterhin sei noch eine Menge von erlaubten Lottypen gegeben; das sind Pakettypen, die angeben, wieviele Stück des Artikels von welcher Größe in ein Paket verpackt werden sollen; schließlich sei eine Höchstanzahl von verwendeten Lottypen für die Belieferung einer Filiale gegeben.
    Gesucht ist nun für jeden erlaubten Lottyp die Anzahl der zu bestellenden Lots und für jede Filiale die Anzahl der zu liefernden Lots, so dass die Liefermenge möglichst wenig von der gegebenen frakionalen Nachfrage abweicht.
    Aufgabe der Diplomarbeit ist es, mathematische Modelle und Algorithmen zu ihrer Lösung für die optimale Warenverteilung zu entwickeln, zu implementieren sowie theoretisch und experimentell zu analysieren.
    Bearbeitungszeitraum: 01.11.2007–30.04.2008
  • Lagerhaltungsstrategie für mehrstufige Lagerhaltung in der Automobilindustrie, Die Ersatzteilversorgung von Automobilwerkstätten muss schnelle Lieferzeiten garantieren und trotzdem wenig kosten. Um Lieferzeiten kurz zu halten, werden dezentrale Lager zur Belieferung der Werkstätten unterhalten, die ihrerseits von Zentrallägern beliefert werden. Momentan werden die Lagerhaltungspolitiken für alle Läger in dieser Hierarchie separat optimiert. Die vernetzte Lagerbestandskontrolle würde aber eine integrierte Optimierung der Lagerhaltungsstrategien aller Läger im Prinzip gestatten.
    Aufgabe ist Modellierung, algorithmische Analyse, Implementierung und Test von Lagerhaltungsstrategien für mehrstufige Lagerhaltung.
    Die Diplomarbeit wird in Zusammenarbeit mit der Volkswagen AG bearbeitet, für die die genannte Aufgabe wichtig ist.
    Bearbeitungszeitraum: 01.11.2007–30.04.2008
  • Diplomarbeit:Dynamic Pricing for a Fashion Retailer, In einem Projekt zum Revenue-Management im Saisonwareneinzelhandel sollen für die fast 1 200 Filialen des Textildiscounters NKDVetriebs GmbH die dynamische Preisfestsetzung und die Belieferung der Filialen mit Konfektionsgrößen optimiert werden. Im Rahmen dieses Projektes müssen zunächst bekannte Verfahren der dynamischen Preisfestsetzung und der damit zusammenhängenden Modellierung des Nachfrageprozesses auf ihre Eignung im Projekt untersucht werden.
    Bearbeitungszeitraum: 01.02.2007–31.07.2007
  • i>Nachtlinienplanung im ÖPNV unter Berücksichtigung von Fußwegen, Die Bayreuther Verkehrs- und Bäder-GmbH (BVB) erwägt eine Neuplanung der Nachtlinien für den Bayreuther ÖPNV mit dem Ziel, die Service-Qualität zu verbessern. Gute Service-Qualität für einen Passagier wird in der Literatur im Wesentlichen interpretiert als eine kleine Anzahl notwendiger Buswechsel und eine kurze Reisezeit.
    In einem kleinen Verkehrsbetrieb wie dem BVB ist es unmöglich, mit dem Nachtliniennetz alle möglichen Haltestellen abzudecken. Daher werden für die meisten Fahrtwünsche Fußwege relevant.
    Ziel dieser Diplomarbeit ist es, eine optimierte Linienplanung für die Nachtlinien der BVB auf Basis Ganzzahliger Linearer Optimierung (ILP) zu berechnen, die für die Fahrgastströme die Fußwege mit berücksichtigt.
    Bearbeitungszeitraum: 01.01.2007–30.06.2007
  • Diplomarbeit:Optimierung der Preisreduzierungsstrategie eines Textildiscounters, In einem weiteren Projekt zum Revenue-Management im Saisonwareneinzelhandel sollen für die fast 1 200 Filialen des Textildiscounters NKD Vetriebs GmbH die dynamische Preisfestsetzung und die Belieferung der Filialen mit Konfektionsgrößen optimiert werden. Im Rahmen dieses Projektes müssen diskrete Verfahren zur optimalen Preisfestsetzung untersucht werden, da Preisreduzierungen nur zu festen Zeiten und auf feste Preisstufen möglich sind.
    Bearbeitungszeitraum: 01.11.2006–30.04.2007
  • Optimale Mischung von Sanden unter unsicherer Lagerinformation
    Die Firma LivingLogic optimiert derzeit die Mischung von Sanden nach Kundenwunsch für die Firma Strobel Quarzsand GmbH (mehr). Die dabei zu lösende Aufgabe lautet: eine durch den Kundenwunsch gegebene Körnungsverteilung (inklusive Toleranzen und Gewichtungen) soll durch Mischung von Sanden aus 30 Silos mit bekannten Körnungsverteilungen möglichst gut approximiert werden. In dieser Diplomarbeit soll untersucht werden, ob mit Methoden der Stochastischen Dynamischen Programmierung oder der Online-Optimierung ein bzgl. unvorhergesehener Ereignisse robusteres Verfahren geschaffen werden kann bzw. mathematische Gütekriterien angegeben werden können.
    Bearbeitungszeitraum: 30.03.2006–29.09.2006
  • Subgradientenmethoden zur dynamischen Spaltengenerierung für die echzeitfähige Einsatzplanung von Pannenhilfefahrzeugen
    In einem Projekt zur Einsatzplanung von Pannenhilfefahrzeugen des ADAC ist am ZIB ein echtzeichfähiger Reoptimierungsalgorithmus auf Basis ganzzahlige Programmierung entwickelt worden. Dieser beruht auf dynamischer Spaltengenerierung zur Erzeugung von möglichst wenig chancenreichen Tourvariablen. Thema der Diplomarbeit ist bestehende Iteration eines linearen Programms zur Spaltengenerierung mit einem Verfahren aus der nicht-differenzierbaren Optimierung zu vergleichen.
    Bearbeitungszeitraum: 01.01.2006–30.06.2006
  • Diplomarbeit:Optimierte Auslastung von Laserquellen im Automobilkarosseriebau
    Laserschweißen hat sich während der letzten 10 Jahre zu einer Schlüsseltechnologie im Karosseriebau entwickelt. Hierbei werden mehrere Schweißroboter von einer gemeinsamen externen Laserquelle versorgt. Ziel eines gemeinsamen Projekts mit dem ZIB ist es, die bestmögliche Auslastung der teuersten Resource, der Laserquellen, zu erreichen. Thema der Arbeit ist die Modellierung sowie der Entwurf und die Analyse von Algorithmen für ein abgeleitetes Scheduling-Problem.
    Bearbeitungszeitraum: 01.11.2005–30.04.2006
  • Diplomarbeit:Iteriertes Assignment vs. Reoptimierung zur Fahrzeugeinsatzplanung
    Die Einsatzplanung der Hilfefahrzeuge des ADAC geschieht bereits in vier Hilfezentralen mit Hilfe einer Echtzeit-Reoptimierung auf Basis Ganzzahliger Linearer Programmierung. Als konkurrierender heuristischer Ansatz wird häufig die Methode des iterierten Assignments verwendet, um den Aufwand der exakten Reoptimierung zu vermeiden. Ziel dieser Arbeit ist der Vergleich der existierenden Reoptimierung mit dem iterierten Assignment sowohl auf konstruierten Beispielinstanzen als auch auf realen Daten des ADAC.
    Bearbeitungszeitraum: 28.10.2005–28.04.2006

Universität Bayreuth -