25.11.2016 Talk “Resource Allocation under Uncertainty – Online Scheduling with Hard Deadlines”
Prof. Dr. Nicole Megow, University of Bremen, had the above mentioned talk at our Seminar SFB/TRR 89 “InvasIC”.
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.