25.11.2016 Vortrag „Resource Allocation under Uncertainty – Online Scheduling with Hard Deadlines“

Bild von Prof. Megow beim Vortrag
Prof. Megow

Prof. Dr. Nicole Megow, Universität Bremen, hielt im Rahmen unseres Seminars SFB/TRR 89 „InvasIC“ den o.g. Vortrag.

Bild von Prof. Megow (l) mit Prof. Teich vor der Wand der Bilder von abgeschlossenen Promotionen
Prof. Megow (l) mit Prof. Teich

Abstract:
Uncertainty in the input data is an omnipresent issue when solving real-world optimization problems: jobs may take more or less time than originally estimated, resources may become unavailable, jobs/information arrive late, etc. Uncertain data is often modeled through stochastic parameters or as online information that is incrementally revealed. The task is to design algorithms that „perform well“ even under uncertainty. Provable performance guarantee are crucial in many applications, e.g., when operating safety-critical systems.
In this talk, we discuss different types of performance guarantees and focus on worst-case guarantees. The main part is devoted to an online scheduling model in which jobs with hard deadlines arrive online over time. The task ist to find a feasible schedule on a minimum number of machines. We design and analyze online algorithms and we mathematically derive performance guarantees. We also discuss the power of job migration and give somewhat surprising bounds.