Inhalt des Dokuments
Es gibt keine deutsche Übersetzung dieser Webseite.
Welcome at the homepage of the Emmy Noether Junior Research Group "Scheduling under Uncertainty". This is an independent research group funded by the German Research Foundation (DFG) . It is associated with the the group "Combinatorial Optimization and Graph Algorithms (COGA) ".
Models, algorithms and complexity for scheduling under uncertainty: On the tradeoffs between performance and adaptivity
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 solu- tions. We study fundamental theoretical questions on practically relevant algorithms for problems from stochastic, online, and real-time scheduling.