Profit-driven uniprocessor scheduling with energy and timing constraints.
Journal
Proceedings of the 2004 ACM Symposium on Applied Computing (SAC), Nicosia, Cyprus, March 14-17, 2004
Pages
834-840
Date Issued
2004
Author(s)
Abstract
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.
SDGs
Other Subjects
Computational complexity; Embedded systems; Energy utilization; Information analysis; Linear programming; Optimization; Polynomial approximation; Problem solving; Real time systems; Energy-aware scheduling; Power management; Real-time process scheduling; Computer science
Type
conference paper