Approximation algorithms for power minimization of earliest deadline first and rate monotonic schedules
Sushu Zhang, Karam S. Chatha, Goran Konjevod · 2007
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%) for large 100 node task sets.