An Efficient Partial-Order Characterization of Admissible Actions for Real-Time Scheduling of Sporadic Tasks

In many scheduling problems involving tasks with multiple deadlines, there is typically a large degree of flexibility in determining which tasks to serve at each time step. Given a cost function it is often possible to cast a scheduling problem as an optimization problem to obtain the most suitable schedule. However, in several applications, especially when the schedule has to be computed in-line or periodically adjusted, the cost function may not be completely known a priori but only partially. For example, in some applications only the cost of the current allocation of resources to the tasks could be available. Under this scenario, a sensible approach is to optimally allocate resources without compromising the schedulability of the tasks. This work follows this approach by introducing a notion of partial ordering on the set of feasible schedules. This partial ordering is particularly useful to characterize which allocations of resources at the current time preserve the feasibility of the problem in the future. This enables the realization of fast algorithms for real-time scheduling. The model and algorithm presented can be utilized in different applications such as electric vehicle charging, cloud computing and advertising on websites. [1