A Dual intepretation of Standard Constraints in Parametric Scheduling
A Dual intepretation of Standard Constraints in Parametric Scheduling
Files
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)