Fundamental Bounds in Real-Time Scheduling Theory

This project will address foundational open problems in real-time scheduling theory and explore new areas concerning the online nature of scheduling.

It is mathematically-driven theoretical basic research.A schedulability problem is a decision problem asking whether a given system will meet all its timing constraints under all possible runtime scenarios. These problems are of central importance to real-time systems. This project aims to find the computational complexity bounds of such problems in the most important settings.

I have previously (with co-authors) settled several such long-standing problems, but there are still many core schedulability problems for which complexity is poorly understood, especially in multiprocessor scheduling.Real-time scheduling is an online problem where the concrete behavior of the system is only successively revealed at runtime.

Another related aim of this project is to better understand the online nature of scheduling.

One of the goals here is to understand what inherent limitations and bounds that are in place for optimal scheduling in terms of the runtime overheads from the scheduler: number of preemptions, the size and running time of the scheduling algorithm itself, etc.

In several important settings all known optimal deterministic scheduling algorithms are prohibitively complicated, a goal of this project is to establish whether efficient randomized scheduling algorithms can improve upon these while retaining strong statistical bounds.