Utility Accrual Real-Time Scheduling with Probabilistically-Assured Timeliness Performance
Peng Li, Binoy Ravindran, E. Douglas Jensen · 2004
We present time/utility function (TUF) algorithms that provide probabilistic assurance on timeliness behavior. A TUF, which is a generalization of the classical deadline constraint, specifies the utility of completing an application activity as a function of that activity’s completion time. The algorithms consider a stochastic model where activity execution times and arrivals are probabilistically described. Further, activity time constraints are specified using TUFs. We consider the dual optimization objective of probabilistically satisfying applicationspecified lower bounds on individual activity utility, and maximizing system-wide total utilities. We present algorithms that achieve this dual objective. 1