| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 439229 | Theoretical Computer Science | 2008 | 11 Pages |
Abstract
We consider the problem of online scheduling a set of equal-processing-time tasks with precedence constraints so as to minimize the makespan. For arbitrary precedence constraints, it is known that any list scheduling algorithm has a competitive ratio of 2−1/m, where m is the number of machines. We show that for intree precedence constraints, Hu’s algorithm yields an asymptotic competitive ratio of 3/2.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
