Paper Info
Title
Scheduling parallel tasks with individual deadlines
Abstract
In this paper, we consider the problem of scheduling independent parallel tasks with individual deadlines so as to maximize the total work performed by the tasks which complete their executions before deadlines. We propose two polynomial-time approximation algorithms for non-malleable parallel tasks and malleable tasks with linear speedup. For non-malleable tasks, the first algorithm guarantees an approximation factor of 5 + epsilon for any positive constant epsilon, while, for malleable tasks with linear speedup, the second algorithm guarantees an approximation factor of 4.5. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
Year
DOI
Venue
1999
10.1016/S0304-3975(97)00178-3
ISAAC
Keywords
DocType
Volume
polynomial time,heuristic algorithm
Journal
215
Issue
ISSN
Citations 
1-2
0304-3975
13
PageRank 
References 
Authors
0.74
9
2
Name
Order
Citations
PageRank
Oh-Heum Kwon1738.74
Kyung-Yong Chwa291997.10