Approximation algorithms for power minimization of earliest deadline first and rate monotonic schedules

We address power minimization of earliest deadline first and rate monotonic schedules by voltage and frequency scaling. We prove that the problems are NP-hard, and present (1+ϵ) fully polynomial time approximation techniques that generate solutions which are guaranteed to be within a specified quality bound (QB= ϵ) (say within 1% of the optimal). We demonstrate that our techniques can match optimal solutions when QB is set at 1%, out perform existing approaches even when QB is set at 10%, generate solutions that are quite close to optimal (<; 5%) even when QB is set at higher values (25%), and execute in a fraction of a second (with QB > 5%) for large 100 node task sets.