Abstract
Reward-based scheduling provides graceful degradation for real-time systems such as multimedia applications and iterative-refinement numerical algorithms. A reward-based task is composed of a mandatory part and an optional part which only executes after completion of the mandatory part. Traditional reward-based scheduling algorithms address on maximizing the total reward in a system. Such an algorithm may result in an unbalanced system where some tasks receive results of superior quality while other tasks only receive minimal acceptable results. In this paper, we present an optimal balanced-reward algorithm such that each task receives the same quality ratio. We first discuss the case where each reward function is strictly increasing and invertible. A mathematical approach is presented to determine the optimal quality ratio. We next develop an efficient generic solution for general cases where some reward functions are not invertible. We conducted experiments to compare our algorithm with a set of other reward-based algorithms to demonstrate its effectiveness. The experimental results show that our algorithm effectively and efficiently develops an optimal balanced-reward schedule.