The digraph real-time task model with timing constraints: Schedulability analysis revisited

Jing Hao Sun, Nan Guan, Qing Xu Deng

Research output: Journal article publicationJournal articleAcademic researchpeer-review


All right reserved. The digraph real-time task with timing constraints (TCDRT) is one of the most expressiveness models in real-time community, but its corresponding schedulability analysis (SA) is strongly NP-hard problem. Present researchers focus on a tractable TCDRT model where the number of constraints is bounded by a constant K, and the only known method for the TCDRT model uses a transformation into an equivalent DRT model, which leads to a high complexity that is exponential in the width of the constraints. This work analyzes the schedulability of the TCDRT model directly in order to achieve a much lower complexity. First, we propose a dynamic program to deal with the demand bound computation problem for the K-bounded TCDRT case and refine the complexity result to a better bound that has no relation with the width of constraints. Second, we prove that the schedulability of bound T can be computed within a pseudo-polynomial time, and the corresponding computation complexity is drastically linear in K instead of being exponential. Furthermore, our approach also indicates another tractable TCDRT model that is not necessary to postulate the K-bounded constraints.
Original languageEnglish
Pages (from-to)2481-2493
Number of pages13
JournalJisuanji Xuebao/Chinese Journal of Computers
Issue number12
Publication statusPublished - 1 Dec 2016
Externally publishedYes


  • Demand bound function
  • Digraph real-time tasks
  • Dynamic programming
  • Schedulability analysis
  • Timing constraints

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications
  • Computer Graphics and Computer-Aided Design

Cite this