TWO CONP-COMPLETE SCHEDULE ANALYSIS PROBLEMS

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, multipro...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2001-10, Vol.12 (5), p.565-580
Main Authors: Rhodes, David L., Wolf, Wayne
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054101000667