Robust optimization and variants of the scheduling problem

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.