Profit-Driven Uniprocessor Scheduling with Energy and Timing Constraints

摘要

Energy-aware scheduling has received much attention in recent years, especially for systems with serious considerations on energy consumption. While most previous work focuses on the minimization of energy consumption, this paper exploits the maximization of the entire system profit under energy and timing constraints. We propose a greedy approximation algorithm with a 2-approximation ratio. A fully polynomial time approximation scheme (FPTAS) is also proposed, which is an optimal approximation algorithm unless P = NP. For each specified amount of error tolerant to users, the approximation algorithm could provide trade-offs among the specified error, the running time, the approximation ratio, and the memory space complexity. It provides ways for system engineers to trade performance with implementation constraints.