Path-constrained relaxed schedulability analysis

The schedulability analysis problem for many realistic task models is known to be hard (NP or coNP). As this severely restricts the application of these task models, recently there has been a considerable amount of interest in relaxed or approximate notions of schedulability, with the hope that they can be checked more efficiently. In this paper we introduce yet another natural notion of relaxed schedulability, which is parameterized in terms of the number of paths in a task set. In the model we consider, each task is represented by a directed acyclic graph where the nodes of such a graph are annotated with execution times and deadlines. Our proposed notion of schedulability allows a certain number of paths from each task graph to be non-schedulable. For describing the relaxed schedulability analysis, we formally define a measure called pseudo-K-schedulability, which corresponds to the situation when the task set has exactly K schedulable paths. At one extreme is the classical notion of schedulability analysis, where the problem is NP hard in our and many other task models. At the other extreme of this spectrum we have the trivial notion of schedidability analysis, where no path needs to be schedulable. Problems in between allow for a flexible notion of schedulability. This paper studies the relaxed schedulability because not all paths in a code are executed. This paper shows a fundamental result, namely the membership of the pseudoschedulability problem to the class of #P-hard problems.