Optimal Control of Discrete Event Systems with Weakly Hard Real-Time Constraints

We consider Discrete Event Systems that can dynamically allocate resources in order to process tasks with real-time constraints. In the case of "weakly hard" constraints, a fraction of tasks is allowed to violate them, as long as m out of any k consecutive tasks meet their respective constraints. This is a generalization of a system with purely hard real-time constraints where m = k = 1. For non-preemptive and aperiodic tasks, we formulate an optimization problem where task processing times are controlled so as to minimize a cost function while guaranteeing that a "weakly hard" criterion is satisfied. We establish a number of structural properties of the solution to this problem which lead to an efficient algorithm that does not require any explicit nonlinear programming problem solver. The low complexity of this algorithm makes it suitable for on-line applications. Simulation examples illustrate the performance improvements in such optimally controlled systems compared to ad hoc schemes.