Models, algorithms and complexity for scheduling under uncertainty: On the tradeoffs between performance and adaptivity

• Antragstellerin: Professorin Dr. Nicole Megow
• Fachliche Zuordnung: Theoretische Informatik ; Mathematik
• Förderung: Förderung von 2012 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 201423354

The vast majority of scheduling research assumes complete information about the problem instance. In most real-world applications, however, uncertain input that is gradually revealed during schedule execution is an omnipresent issue. Unlike its deterministic counterpart, the diverse field of scheduling under uncertainty is not well understood from an algorithmic point of view. Moreover, most current approaches on algorithm’s design assume arbitrary algorithmic flexibility and neglect practice-driven limitations on adaptivity. In this project we design algorithmic and analytic tools for solving important scheduling problems with uncertain input, such as unreliable machines, stochastic job processing times, or unknown job arrival times. Our major goal is to study thoroughly the tradeoff between the performance of an algorithm and the amount of adaptivity it requires. On the one hand, we aim for best possible algorithms which are potentially highly dynamic, i.e., scheduling decisions may adapt arbitrarily to the instantiated problem data. On the other hand, we are interested in good but simple algorithms that respect practice-driven adaptivity restrictions. We analyze what kind and what amount of adaptivity an algorithm needs to achieve a certain performance guarantee. Our main tools come from approximation algorithms, combinatorial optimization, mathematical programming, and probability theory, and our investigations integrate the concepts of universal and robust solutions. We study fundamental theoretical questions on practically relevant algorithms for problems from stochastic, online, and real-time scheduling.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen