Voltage-scaling scheduling for periodic real-time tasks in reward maximization

This paper is interested in reward maximization of periodic real-time tasks under a given energy constraint, where the reward received depends on how much computation a task runs before its deadline. When voltage scaling could be done at any time, and tasks share the same power consumption function, we propose a greedy algorithm which derives a solution with at least a half of the optimal reward for any input instance. A fully polynomial-time approximation scheme is also proposed by applying the dynamic programming approach so that the ratio of the reward of the derived solution to that of an optimal solution is at least 1 - /spl epsiv/ under polynomial-time complexity in 1//spl epsiv/ for any 0 < /spl epsiv/ < 1, where /spl epsiv/ denotes a user-specified tolerable error to the derived solutions. When voltage scaling could be done only when a task instance arrives or terminates, or tasks might have different power consumption functions, we develop an approximation algorithm based on linear programming, which guarantees to derive a solution with at least 1/3 optimal reward for any input instance. A series of experiments was conducted to show the capability of the proposed algorithms in reward maximization.