Show simple item record

dc.contributor.authorSubrmani, K.en_US
dc.contributor.authorAgrawala, A.en_US
dc.date.accessioned2004-05-31T23:02:46Z
dc.date.available2004-05-31T23:02:46Z
dc.date.created2000-03en_US
dc.date.issued2000-03-23en_US
dc.identifier.urihttp://hdl.handle.net/1903/1062
dc.description.abstractAn 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.extent168712 bytes
dc.format.mimetypeapplication/postscript
dc.language.isoen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4119en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-2000-16en_US
dc.titleThe Parametric Polytope and its applications to a Scheduling Problemen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record