A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

We present a polynomial time approximation scheme for the real-time scheduling problem with fixed priorities when resource augmentation is allowed. For a fixed ε > 0, our algorithmcomputes an assignment using atmost (1+ε)·OPT +1 processors in polynomial time, which is feasible if the processors have speed 1+ε. We also show that, unless P = NP, there does not exist an asymptotic FPTAS for this problem