TWO CONP-COMPLETE SCHEDULE ANALYSIS PROBLEMS
David L. Rhodes, Wayne H. Wolf · International Journal of Foundations of Computer Science · 2001
While many forms of schedule decision problems are known to be NP-complete, two forms of schedule analysis problems are shown to be coNP-complete in the strong sense. Each of these involve guaranteeing that all deadlines are met for a set of task-graphs in statically-mapped, priority-based, multiprocessor schedules given particular variabilities. Specifically, the first of these allows run-times which axe bracketed, where the actual run-time of some tasks can take on any value within a given range. The second deals with task-graphs which arrive asynchronously, that is where the release-time for each task-graphs may take either any or a bracketed value. These variations correspond to task-graphs with either release-time or run-time jitter. The results are robust in the sense that they apply when schedules are either preemptive or non-preemptive as well as for several other problem variations.