Online scheduling of equal-processing-time task systems

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.