Tracking dynamic deadlines in switched max-plus linear systems with uncontrollable workloads

Abstract Modern safety-critical cyber-physical systems such as medical imaging equipment or autonomous vehicles need to respect strict deadlines on received data-processing workloads. These deadlines and workloads are dynamic and uncontrollable and the systems typically have only a limited discrete number of system configurations to respond to dynamic changes. The number and types of processors allocated to a data-processing task, their operating voltage and frequency, and the resolution and frequency of sensing (e.g., images) are examples of controllable configuration parameters. Guaranteeing dynamically changing deadlines under uncontrollable workloads with a limited discrete number of response options can be phrased as a multi-objective tracking problem for a switched max-plus linear system. This results in a combined scheduling and control problem. We propose an integrated state-feedback and model-predictive control solution that minimizes the number of deadline misses and the cost of implementation (e.g., energy consumption). We demonstrate the effectiveness of our approach through simulation.