Integer programming approach for schedulability of sporadic real-time systems

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations

Author(s)

  • Jing-Hao Sun
  • Jing-Chang Sun
  • Nan Guan
  • Qing-Xu Deng

Detail(s)

Original languageEnglish
Pages (from-to)411-428
Journal / PublicationRuan Jian Xue Bao/Journal of Software
Volume28
Issue number2
Publication statusPublished - 1 Feb 2017
Externally publishedYes

Abstract

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 104 smaller than the traditional ones.

Research Area(s)

  • Earliest deadline first, Integer programming, Linear relaxation, Polyhedral analysis, Schedulability

Bibliographic Note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to lbscholars@cityu.edu.hk.

Citation Format(s)

Integer programming approach for schedulability of sporadic real-time systems. / Sun, Jing-Hao; Sun, Jing-Chang; Guan, Nan; Deng, Qing-Xu.

In: Ruan Jian Xue Bao/Journal of Software, Vol. 28, No. 2, 01.02.2017, p. 411-428.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review