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.