AAAI Publications, Sixth European Conference on Planning

Font Size: 
Modeling Clairvoyance and Constraints in Real-Time Scheduling
K. Subramani

Last modified: 2014-05-21

Abstract


Scheduling in Real-time systems differs from scheduling in conventional models in two principal ways: (a) Parameter variability, (b) Existence of complex constraints between jobs. Our work focusses on variable execution times. Whereas traditional models assume fixed values for job execution time, we model execution times of jobs through convex sets. The second feature unique to real-time systems, is the presence of temporal relationships that constrain job execution. Consider for instance the requirement that job 1 should conclude 10 units before job 2. This can be modeled through a simple, linear relationship, between the start and execution times of jobs 1 and 2.  In real-time scheduling, it is important to guarantee a priori, the scheduling feasibility of the system. Depending upon the nature of the application involved, there are different schedulability specifications viz. Static, Co-Static and Parametric. Each specification comes with its own set of flexibility issues. In this paper, we present a  framework that enables the specification of real-time scheduling problems and discuss the relationship between flexibility and complexity in the proposed model. We motivate each aspect of our model through examples from real-world applications.

Keywords


Real-Time, embedded systems, constraints, clairvoyance

Full Text: PDF