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.identifier.uri http://hdl.handle.net/1903/1062 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.language.iso 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 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
﻿