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 [1] 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.