Integer programming approach for schedulability of sporadic real-time systems

Schedulability test for EDF (earliest deadline first) systems is one of the classical NP-hard problems in the study of real-time system. Current researches mainly focus on the synchronous systems with the utilization U strictly less than 1, which can be decided exactly in pseudo-polynomial time. However, these results cannot be easily extended to the synchronous systems with U≤1 or to the asynchronous systems even with U<1. In this paper, a unified integer programming formulation, where the associated scale is independent of utilization U, is proposed for the EDF schedulability problems in both of the synchronous and asynchronous systems. The polyhedral structure of the formulation is investigated and a kind of facet inequalities is derived, resulting in a linear relaxation approach with polynomial-time complexity. Numerical results on a large scale randomly generated asynchronous and synchronous instances show that the proposed method can obtain a tight gap (0.78% and 1.27% respectively on average) between the relaxation and the optimal integer solutions. Furthermore, the comparison with the QPA exhibits that the new method is available for 70% synchronous instances and exponentially reduces the calculation time especially in situations when U>0.99. Finally, experiments on asynchronous systems find that nearly 96% instances can be exactly solved by the method, which is 29.27% lesser than the traditional method. For the rest of the instances, the upper bound of the schedulability test can be sharply reduced. For most instances, the new bound is 10⁴ smaller than the traditional ones.