Skip to main content


Go Search
Department of Computer Science & Engineering
About the Department
Graduate Programs
Undergraduate Programs
Student Services
Wustl Engineering
Department of Computer Science & Engineering > Research > Technical Reports > Scalable Scheduling Policy Design for Open Soft Real-Time Systems  

Technical Reports: Scalable Scheduling Policy Design for Open Soft Real-Time Systems


Scalable Scheduling Policy Design for Open Soft Real-Time Systems 

File Date



Open soft real-time systems, such as mobile robots, must respond adaptively to varying operating conditions, while balancing the need to perform multiple mission specific tasks against the requirement that those tasks complete in a timely manner.  Setting and enforcing a utilization target for shared resources is a key mechanism for achieving this behavior.  However, because of the uncertainty and non-preemptability of some tasks, key assumptions of classical scheduling approaches do not hold. In previous work we presented foundational methods for generating task scheduling policies to enforce proportional resource utilization for open soft real-time systems with these properties. However, these methods scale exponentially in the number of tasks, limiting their practical applicability.

In this paper, we present a novel parameterized scheduling policy that scales our technique to a much wider range of systems. These policies can represent geometric features of the scheduling policies produced by our earlier methods, but only require a number of parameters that is quadratic in the number of tasks. We provide empirical evidence that the best of these policies are competitive with exact solution methods in small problems, and significantly outperform heuristic methods in larger ones.


Robert Glaubius, Terry Tidwell
Braden Sidoti, David Pilla, Justin Meden
Christopher Gill, William D. Smart





Web Page


Type of Report

Approval Status Approved 
Content Type: Item
Created at 10/12/2009 5:00 PM  by Terry Tidwell 
Last modified at 11/3/2009 2:47 PM  by Hawkins, Madeline