Journal
ALGORITHMICA
Volume 32, Issue 2, Pages 247-261Publisher
SPRINGER
DOI: 10.1007/s00453-001-0076-9
Keywords
approximation; scheduling; multiprocessor tasks
Ask authors/readers for more resources
We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm that finds a schedule of makespan within a factor of (1 + epsilon) of optimal in the non-preemptive model. We extend our results by obtaining a polynomial time approximation scheme for the parallel processors variant of the multiprocessor task model.
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