The Parametric Polytope and its applications to a Scheduling Problem
| dc.contributor.author | Subrmani, K. | en_US |
| dc.contributor.author | Agrawala, A. | en_US |
| dc.date.accessioned | 2004-05-31T23:02:46Z | |
| dc.date.available | 2004-05-31T23:02:46Z | |
| dc.date.created | 2000-03 | en_US |
| dc.date.issued | 2000-03-23 | en_US |
| dc.description.abstract | An important feature in Real-time systems is {\em parameter impreciseness} i.e. the inability to accurately determine certain parameter values. The most common such parameter is {\em task execution time}. A second feature is the presence of complex relationships between tasks that constrain their execution. Traditional models do not accomodate either feature completely: (a) Variable execution times are modeled through a fixed value ( {\em worst-case} ), and (b) Relationships are limited to those that can be represented by precedence graphs. We present a task model that effectively captures {\em variable task execution time}, while simultaneously permitting arbitrary linear relationships between tasks. Our model finds applications in diverse areas such as real-time task scheduling, compiler scheduling, real-time database scheduling and machine control. This paper focuses primarily on the computational complexity of answering queries posed in our model; in particular we demonstrate the existence of constraint classes that make the scheduling problem {\em hard.} (Also cross-referenced as UMIACS-TR-2000-16) | en_US |
| dc.format.extent | 168712 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/1062 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-4119 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-2000-16 | en_US |
| dc.title | The Parametric Polytope and its applications to a Scheduling Problem | en_US |
| dc.type | Technical Report | en_US |