Uniprocessor Scheduling Under Precedence Constraints

In this paper we present a novel approach to the constrained scheduling problem, while addressing a more general class of constraints that arise from the timing requirements on real-time embedded controllers and from the implementation of mixed data-flow/event-driven real-time systems. We provide general necessary and sufficient conditions for scheduling under precedence constraints and derive sufficient conditions for two well-known scheduling policies. We define mathematical problems that provide optimum priority and deadline assignments, while ensuring both precedence constraints and system’s schedulability.We show how these problems can be relaxed to corresponding ILP formulations leveraging on available solvers.