Trilemma in Optimization for Time-critical Cyber-Physical Systems: Balancing Optimality, Generality, and Scalability

The increasing complexity of time-critical Cyber-Physical Systems (CPS) presents significant challenges in designing optimization algorithms that balance generality, scalability, and performance. Traditional approaches often compromise one or more of these properties: general metaheuristic algorithms lack scalability and performance guarantees, while problem-specific methods sacrifice generality for improved efficiency or optimality. However, due to the NP-hard nature of many real-time scheduling and optimization problems, it is highly unlikely to design optimization algorithms that are simultaneously general, scalable, and optimal. Therefore, this dissertation addresses these challenges by developing novel optimization frameworks tailored for time-critical CPS and try to improve the trade-off among the three factors. The first contribution focuses on general and scalable optimization techniques, introducing frameworks such as NORTH, which operates with black-box schedulability constraints while achieving very good scalability and reasonably good performance. Additionally, another optimization framework targets at general robotic working environments by performing dynamic resource allocation. It demonstrates 20–50% improvements in safety-performance metrics with low computational overhead. The second contribution advances domain-specific optimization techniques by relaxing the general requirements. For instance, flexible Logical Execution Time (LET) optimization achieves significant improvements in end-to-end latency, time disparity, and jitter by leveraging symbolic operations and efficient exploration of solution spaces. Similarly, a novel scheduling approach for DAG-based task models minimizes worst-case end-to-end latency and time disparity through 1-opt solutions with polynomial runtime complexity, achieving up to 40% performance gains over existing methods. These contributions push the boundaries of generality, scalability, and optimality in real-time systems optimization, providing practical solutions to complex scheduling and resource allocation problems. The proposed frameworks are validated through extensive experimental studies, demonstrating their applicability and impact across a range of real-world scenarios.