A dual interpretation of “standard constraints” in parametric scheduling
| Title | A dual interpretation of “standard constraints” in parametric scheduling |
| Publication Type | Conference Papers |
| Year of Publication | 2000 |
| Authors | Subramani K, Agrawala AK |
| Conference Name | Formal Techniques in Real-Time and Fault-Tolerant Systems |
| Date Published | 2000/// |
| Abstract | Parametric scheduling in real-time systems, in the presence of linear relative constraints between the start and execution times of tasks, is a well-studied problem. Prior research established the existence of polynomial time algorithms for the case when the constraints are restricted to be standard and the execution time vectors belong to an axis-parallel hyper-rectangle. In this paper we present a polynomial time algorithm for the case when the execution time vectors belong to arbitrary convex domains. Our insights into the problem occur primarily as a result of studying the dual polytope of the constraint system. |