Scalable optimization algorithms for discrete event systems with real-time constraints: An overview of recent developments

Discrete event systems with real-time constraints involve tasks that must be completed within specified hard deadlines. Guaranteeing such constraints requires a control effort measured through a cost function, giving rise to a class of nonlinear optimization problems. We overview recent developments aimed at solving such problems in an efficient scalable fashion suitable for on-line applications with limited computational resources. We describe how structural properties of the optimal state trajectory in such problems can be exploited and present a critical task decomposition algorithm (CTDA) when tasks are processed by a single-stage system. When tasks are processed over multiple stages and are subject to end-to-end real-time constraints, a different set of structural properties is exploited leading to a virtual deadline algorithm (VDA).