Stochastic, Utility Accrual Real-Time Scheduling with Task-Level and System-Level Timeliness Assurances
Peng Li, Hyeonjoong Cho, Binoy Ravindran, E. Douglas Jensen · 2005
Heuristic algorithms have enjoyed increasing interests and success in the context of utility accrual (UA) scheduling. However, few analytical results, such as bounds on task-level and system-level accrued utilities are known. In this paper, we propose the S-UA algorithm that can provide probabilistic bounds on task-level accrued utilities. Lower bound on system-level accrued utility ratio (AUR) is also derived and maximized by S-UA.