The Power of Duality: Response Time Analysis meets Integer Programming

We study a mutually enriching connection between response time analysis in real-time systems and the mixing set problem. Thereby generalizing over known results we present a new approach to the computation of response times in fixed-priority uniprocessor real-time scheduling. We even allow that the tasks are delayed by some period-constrained release jitter. By studying a dual problem formulation of the decision problem as an integer linear program we show that worst-case response times can be computed by algorithmically exploiting a conditional reduction to an instance of the mixing set problem. In the important case of harmonic periods our new technique admits a near-quadratic algorithm to the exact computation of worst-case response times. We show that generally, a smaller utilization leads to more efficient algorithms even in fixed-priority scheduling. Worst-case response times can be understood as least fixed points to non-trivial fixed point equations and as such, our approach may also be used to solve suitable fixed point problems. Furthermore, we show that our technique can be reversed to solve the mixing set problem by computing worst-case response times to associated real-time scheduling task systems. Finally, we also apply our optimization technique to solve 4-block integer programs with simple objective functions.