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 alpha-approximation algorithms in the resource augmentation setting, i.e., finding a feasible partition on machines running at speed alpha >= 1, if some feasible partition exists on unit-speed machines. Recently, Chen and Chakraborty gave a polynomial-time approximation scheme if the ratio of the largest to the smallest relative deadline of the tasks, lambda, is bounded by a constant. However, their algorithm has a super-exponential dependence on lambda and hence does not extend to larger values of lambda. Our main contribution is to design an approximation scheme with a substantially improved running-time dependence on lambda. In particular, our algorithm depends exponentially on log lambda and hence has quasi-polynomial running time even if lambda is polynomially bounded. This improvement is based on exploiting various structural properties of approximate demand bound functions in different ways, which might be of independent interest.