An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems
We study a generalization of the nonpreemptive scheduling problem on hypercube parallel task systems. We generalize the problem by limiting the maximum number of tasks that can be simultaneously executed. We describe a simple 3-approximation algorithm for this problem when speedup and execution times are monotone in the number of processors assigned to a task. (C) 1999 Published by Elsevier Science B.V. All rights reserved.
approximation algorithms nonpreemptive scheduling parallel task systems