CIF:Small:Deadline Scheduling and Sensor Fusion

最后期限调度问题，在其最一般的设置，是调度不同的工作量，成本/回报，和完成的最后期限的工作。 今天，计算机化的最后期限调度渗透到所有类型的应用中，从计算机架构到网络物理系统，从通信网络到物联网。可以毫不夸张地说，截止期调度是真实的时间系统理论和应用的基础。 然而，很多是未知的，和最先进的福尔斯状态远远低于解决不断扩大的范围内的实时最后期限调度问题。 特别是缺乏对复杂性和性能之间的权衡的基本理解，为非常大的问题提供接近最佳解决方案的算法，以及能够处理模型，数据和操作不确定性的技术。本计画旨在透过解决这些缺失的元素来提升最新的技术水平。本研究在三个方向上提升即时系统的理论与实务。首先，它追求一种新的排序为基础的调度方法，打破了灾难的尺寸调度复杂性，同时保证渐近最优性能的高维截止日期调度问题。其次，本研究通过开发一种分散式调度解决方案，用于收集具有不同优先级和紧急程度的信息，推进了传感器融合实时监测和控制的前沿。第三，这项研究开发了在线学习技术，以科普未知的系统动态和工作到达统计。这个奖项反映了NSF的法定使命，并已被认为是值得支持的，通过评估使用基金会的智力价值和更广泛的影响审查标准。

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.