Integer programming approach for schedulability of sporadic real-time systems

Jing Hao Sun, Jing Chang Sun, Nan Guan, Qing Xu Deng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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 104smaller than the traditional ones.
Original languageEnglish
Pages (from-to)411-428
Number of pages18
JournalRuan Jian Xue Bao/Journal of Software
Volume28
Issue number2
DOIs
Publication statusPublished - 1 Feb 2017
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Software

Cite this