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.