Robust optimization and variants of the scheduling problem

Segschneider, Jenny; Koster, Arie Marinus; Büsing, Christina Maria Katharina; Scheidweiler, Robert

doi:10.18154/RWTH-2026-01999

Robust optimization and variants of the scheduling problem = Robuste Optimierung und Varianten des Planungsproblems

Segschneider, Jenny^RWTH*

2026

Verantwortlichkeitsangabevorgelegt von Jenny Segschneider, M. Sc.

ImpressumAachen : RWTH Aachen University 2026

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2026

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Koster, Arie Marinus (Thesis advisor)^RWTH* ; Büsing, Christina Maria Katharina (Thesis advisor)^RWTH* ; Scheidweiler, Robert (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2026-01-28

Online
DOI: 10.18154/RWTH-2026-01999
URL: https://publications.rwth-aachen.de/record/1028968/files/1028968.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
robust b-matching (frei) ; robust optimization (frei) ; scheduling problem (frei) ; two-dose problem (frei)

Thematische Einordnung (Klassifikation)
DDC: 510

Kurzfassung
Planungsprobleme werden durch den Umfang moderner Projekte und der Notwendigkeit robuster Entscheidungen unter Unsicherheit immer größer und komplexer. Viele reale Anwendungen umfassen voneinander abhängige Teilprobleme, die sich gegenseitig beeinflussen. Beispielsweise muss bei der Umstellung von Benzin- auf Elektrobusflotten die Batteriekapazität bei der Fahrzeugplanung berücksichtigt werden, die wiederum von den zugrunde liegenden Fahrplänen beeinflusst wird. Beide können während der Umstellung angepasst werden. Ähnlich verhält es sich bei Großprojekten wie dem Bau neuer Infrastrukturen oder der Koordination der Impfstoffeinführung für die COVID-19-Pandemie, die mit Unsicherheiten behaftet sind und eine flexible, aber zuverlässige Planung erfordern. Solche mathematischen Optimierungsprobleme sind im Allgemeinen schwer zu lösen. Standard Techniken auf realistischen Instanzen benötigen meist sehr viel Zeit, um gute Lösungen zu bestimmen, was in der Praxis nicht immer möglich ist. Um dieses Problem zu umgehen, untersuchen wir drei schwere Planungsprobleme und stellen jeweils auf diese angepasste Algorithmen vor. Der Hauptteil dieser Arbeit befasst sich mit dem Directed Robust Two-Dose Problem und seiner Verallgemeinerung, dem Directed Robust b-Matching Problem. Das Problembetrachtet Impfstoffe mit eingeschränkter Verfügbarkeit, von denen jeder Patientenzwei Dosen bekommen muss. Es fragt nach einer geeigneten Planung, welche Dosen als erste Impfung und welche als zweite Impfung verwendet werden. Wir formulieren die deterministische Variante dieses Problems als b-Matching und zeigen, dass das Problemmit drei oder mehr Impfdosen pro Patient NP-schwer wird. Um Unsicherheiten in den Lieferungen mit einzubeziehen, führen wir zwei robuste Formulierungen ein, betrachten ihre Komplexität und untersuchen eine der beiden in einer Rechenstudie. Darauf aufbauend führen wir das Directed Robust b-Matching Problem ein, eine Verallgemeinerung, welche die Unsicherheit bei den Matching-Kapazitäten berücksichtigt. Wir untersuchen ihre rechnerische Komplexität für verschiedene Graphklassen und Problemvarianten. Trotz der allgemeinen Komplexität des Problems identifizieren wir strukturelle Eigenschaften, die eine polynomielle Lösbarkeit ermöglichen. Um die schwer lösbaren Fälle dieses Problems anzugehen, passen wir die Benders-Zerlegung und gängige Beschleunigungstechniken an das Directed Robust Perfect b-Matching Problem an und leiten gültige Ungleichungen zur Verbesserung des Basismodells her. Anschließend testen wir diesen Ansatz in einer Rechenstudie. Im nächsten Teil untersuchen wir die Projektplanung unter unsicheren Bearbeitungszeiten. Wir schlagen zwei Formulierungen vor: das Γ-robuste einstufige Projektplanungsproblem, das mit einer Erweiterung der kritischen Pfade Methode gelöst wird, und das Γ-robuste zweistufige Projektplanungsproblem. Wir zeigen, dass bereits die zweite Stufe des zweistufigen Problems stark NP-schwer ist. Zusätzlich zu einem Benders-ähnlichen Algorithmus führen wir mehrere Heuristiken ein, die wir in einer Rechenstudie anhand von Benchmark-Instanzen evaluieren. Im letzten Teil dieser Arbeit untersuchen wir ein integriertes Planungsproblem bestehend aus periodischer Fahrplanerstellung und der Elektrofahrzeug-Planung. Für die Elektrofahrzeug-Planung leiten wir theoretische Approximationsschranken für gängige Heuristiken her. Darauf aufbauend stellen wir einen iterativen Rahmen vor, um das integrierte Problem zu lösen, und validieren den Ansatz anhand von Daten aus Aachen.

Planning problems are becoming increasingly large and complex, driven by the scale of modern projects and the demand for robust decision-making under uncertainty. Many real-world applications involve interdependent subproblems influencing each other. For instance, in the transition from gasoline to electric bus fleets, vehicle scheduling must account for battery constraints, which in turn are influenced by the underlying timetables—both of which may be adapted during the transition. Similarly, large-scale projects like the construction of new infrastructure like airports or the coordination of vaccine roll-outs for the COVID-19 pandemic are subject to uncertainties and require flexible yet reliable planning. This leads to mathematical optimization problems that are very hard to solve. Using standard optimization techniques on realistic instances results in long computation times, which is often not feasible in practice. To counteract this, we analyze three hard planning problems and propose tailored algorithms to solve them. The main part of this thesis addresses the Directed Robust Two-Dose Problem and its generalization, the Directed Robust b-Matching Problem. For a given vaccine with limited supply that requires two doses per patient, the Two-Dose Problem involves scheduling first and second doses. We demonstrate that the deterministic variant can be formulated as a b-matching problem and show that it becomes NP-hard if three or more doses are required per patient. To include uncertainty in vaccine availability, we introduce two novel robust formulations, prove their computational complexity and evaluate one of them in a computational study. Building on this, we introduce the Directed Robust b-Matching Problem, a generalization that incorporates uncertainty in the matching capacities. We examine its computational complexity across various graph classes and problem variants. Despite the overall hardness of the problem, we identify structural properties that enable tractability. As our main result, we show that the Directed Robust Perfect b-Matching Problem can be solved in polynomial time on graphs without direction-alternating cycles. To address the intractable cases of this problem in practice, we adapt Benders decomposition and common speed-up techniques to the Directed Robust Perfect b-Matching Problem, and derive valid inequalities to improve the base model. We evaluate the performance of these methods in a computational study and demonstrate their practical viability. In the next part of this thesis, we examine the project scheduling problem under uncertain processing times. We propose two formulations, the Γ-robust Single-Stage Project Scheduling Problem, which is solved via an extended critical path method, and the Γ-robust Two-Stage Project Scheduling Problem. We show that even the second stage of the Two-Stage Problem is strongly NP-hard. We introduce a Benders-like algorithm that solves the problem to optimality, as well as several heuristics. These are evaluated on benchmark instances in a computational study. In the final part of this thesis, we study an integrated periodic timetabling and electric vehicle scheduling problem. For the electric vehicle scheduling problem, we derive theoretical approximation guarantees for some commonly used heuristics. Based on these heuristics, we propose an iterative framework to solve the integrated planning problem and validate the approach in a case study using data from Aachen.

OpenAccess:
PDF
(additional files)