Approximating Real-Time Scheduling on Identical Machines

We study the problem of assigning n tasks to m identical parallel machines in the real-time scheduling setting, where each task recurrently releases jobs that must be completed by their deadlines. The goal is to find a partition of the task set over the machines such that each job that is released by a task can meet its deadline. Since this problem is co-NP-hard, the focus is on finding α-approximation algorithms in the resource augmentation setting, i.e., finding a feasible partition on machines running at speed α ≥ 1, if some feasible partition exists on unit-speed machines.