Scalable Utility Aware Scheduling Heuristics for Real-time Tasks with Stochastic Non-preemptive Execution Intervals

Terry Tidwell1,  Carter Bass1,  Eli Lasker1,  Micah Wylde2,  Christopher D. Gill1,  William D. Smart1
1Washington University in St Louis, 2Wesleyan University


Time utility functions can describe the complex timing constraints of real-time and cyber-physical systems. However, utility aware scheduling policy design is an open research problem. Previously we solved a Markov Decision Process formulation of the scheduling problem to derive value-optimal scheduling policies for systems with periodic real-time task sets and stochastic non-preemptive execution intervals. However, the complexity of computing solutions and their policy storage requirements necessitate the exploration of scalable solutions. In this paper we generalize the Utility Accrual Packet Scheduling Algorithm. We compare several heuristics to Markov Decision Process policy evaluation under soft and hard real-time conditions, different load conditions, and different classes of time utility functions. Based on these evaluations we present guidelines for which heuristics are best suited to particular scheduling criteria.