Approximating the Throughput of Real Time Multiple Machines Scheduling

We consider the following fundamental scheduling problem. The input to the problem consists of n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight, and an execution time on each of the machines. The goal is to find a schedule that maximizes the weight of jobs that meet their deadline. We solve four variants of the problem depending on the type of machines (identical vs unrelated) and weight of jobs (identical vs arbitrary). All these variants are known to be NP-Hard, and we give constant factor approximation algorithms for all of them. To the best of our knowledge these are the first approximation algorithms for such problems (in the non-preemptive off-line setting).