The deadline scheduling problem, in its most generic setting, is the scheduling of jobs with different workloads, costs/rewards, and deadlines for completion. Today, computerized deadline scheduling permeates in all types of applications, from computer architecture to cyber-physical systems, from communication networks to the Internet of Things. It is not an overstatement that deadline scheduling is at the foundation of real time system theory and applications. Yet, much is unknown, and the state of the art falls far short of solving an expanding range of real-time deadline scheduling problems. Missing in particular are a fundamental understanding of the tradeoff between complexity and performance, algorithms that deliver near optimal solutions for very large problems, and techniques capable of dealing with model, data and operational uncertainties. This project seeks to advance the state of the art by addressing these missing elements.
This research advances the real-time system theory and practice in three directions. First, it pursues a novel ranking-based scheduling methodology that breaks the curse of dimension of scheduling complexity while guaranteeing asymptotically optimal performance for high dimensional deadline scheduling problems. Second, this research advances the frontier of sensor fusion for real-time monitoring and control by developing a decentralize scheduling solution for collecting information with varying degrees of priority and urgency. Third, this research develops online learning techniques to cope with unknown system dynamics and job arrival statistics.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
