A Dual intepretation of Standard Constraints in Parametric Scheduling

Thumbnail Image
Files
CS-TR-4112.ps(197.53 KB)
No. of downloads: 229
CS-TR-4112.pdf(216.83 KB)
No. of downloads: 616
Publication or External Link
Date
2000-03-07
Authors
Subramani, K.
Agrawala, A.
Advisor
Citation
DRUM DOI
Abstract
The problem of parametric scheduling in hard real-time systems, ( in the presence of linear relative constraints between the start and execution times of tasks ) was posed in the litreature. In an earlier paper, a polynomial time algorithm is presented for the case when the constraints are restricted to be standard ( defined in paper ) and the execution time vectors belong to an axis-parallel hyper-rectangle. In this paper, we extend their results in two directions. We first present a polynomial time algorithm for the case when the execution time vectors belong to arbitrary convex domains. We then show that the set of standard constraints can be extended to include arbitrary network constraints. Our insights into the problem occur primarily as a result of studying the dual polytope of the constraint system. (Also cross-refernced as UMIACS-TR-2000-11)
Notes
Rights