Journal
SIAM JOURNAL ON COMPUTING
Volume 39, Issue 8, Pages 3571-3615Publisher
SIAM PUBLICATIONS
DOI: 10.1137/080736491
Keywords
scheduling; approximation algorithms; parallel tasks; malleable tasks
Funding
- DAAD [315/ab D/05/50457]
- EU [015964]
Ask authors/readers for more resources
In this paper we study variants of the nonpreemptive parallel job scheduling problem in which the number of machines is polynomially bounded in the number of jobs. For this problem we show that a schedule with length at most (1 + epsilon) OPT can be calculated in polynomial time. Unless P = NP, this is the best possible result (in the sense of approximation ratio), since the problem is strongly NP-hard. For the case where all jobs must be allotted to a subset of consecutive machines, a schedule with length at most (1.5 + epsilon) OPT can be calculated in polynomial time. The previously best known results are algorithms with absolute approximation ratio 2. Furthermore, we extend both algorithms to the case of malleable jobs with the same approximation ratios.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available