中文摘要：

带时间约束的实时任务图（TCDRT）模型具有接近于时间自动机的丰富表达性,但是其关联的可调度性分析（SA）问题却是强NP困难的.目前的研究仅关注一类约束个数为常数K的易解模型：K-TCDRT,且局限于SA问题的图转换求解方法.这种间接求法使得问题的计算复杂度随约束宽度呈指数倍增长.该文研究TCDRT模型上可调度性分析问题的直接求解方法,为两个核心子问题给出新的理论结果：第一,针对需求上界函数（DBF）的计算问题,提出了考虑时间约束的路径需求结构,并据此设计了新的动态规划算法,其时间复杂度与约束宽度无关;第二,对于可调度分析上界T的限定问题,从理论上证明了该问题是伪多项式时间可解的,且计算复杂度不再与K指数相关,这使得文中算法性能较已有结果有指数级提升.更进一步地,该文方法还蕴含着一类新的TCDRT易解模型.该类模型突破了约束个数必须为常数的局限,其分析难度也较K-TCDRT有指数倍地下降.

英文摘要：

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.