Approximating the throughput of multiple machines in real-time 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 w ith a release time, a deadline, a weight, and a processing time on each of the machines. The goal is to nda nonpreemptive schedule that maximizes the weight of jobs that meet their respective deadlines. We give constant facto r approximation algorithms for four variants of the problem, depending on t he type of the machines ( identical vs. unrelated) and the weight of the jo bs ( identical vs. arbitrary). All these variants are known to be NP-hard, and the two variants involving unrelated machines are also MAX-SNP hard. Th e specific results obtained are as follows: For identical job weights and unrelated machines: a greedy 2-approximation algorithm. For identical job weights and k identical machines: the same greedy algorit hm achieves a tight (1+1/k)(k)/(1+1/k)(k)-1 approximation factor. For arbitrary job weights and a single machine: an LP formulation achieves a 2-approximation for polynomially bounded integral input and a 3-approxima tion for arbitrary input. For unrelated machines, the factors are 3 and 4, respectively. For arbitrary job weights and k identical machines: the LP-based algorithm applied repeatedly achieves a (1+1/k)(k)(1+1/k)(k)-1 approximation factor f or polynomially bounded integral input and a (1+1/2k)(k)/(1+1/2k)(k)-1 appr oximation factor for arbitrary input. For arbitrary job weights and unrelated machines: a combinatorial ( 3+2 roo t2 approximate to 5.828)- approximation algorithm.