DIMACS TR: 99-52
Improvements in Throughput Maximization for Real-Time Scheduling
Authors: Piotr Berman and Bhaskar DasGupta
ABSTRACT
We consider the problem of off-line throughput maximization for job scheduling
on one or more machines, where each job has a release time, a deadline and a
profit. Most of the versions of the problem discussed here
were already treated by Bar-Noy et al.(Proc. 31st ACM STOC, 622-631, 1999).
Our main contribution is to provide algorithms that do not use linear
programming, are simple
and much faster than the corresponding ones proposed in Bar-Noy et al.,
while either having the same quality of approximation or improving it.
More precisely, compared to the results of in Bar-Noy et al.,
our pseudo-polynomial algorithm for multiple
unrelated machines and all of our strongly-polynomial algorithms
have better performance ratios, all of our algorithms run much faster,
are combinatorial in nature and avoid linear programming.
Finally, we show that algorithms with better
performance ratios than 2 are possible if the stretch factors of
the jobs are bounded.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-52.ps.gz
DIMACS Home Page