Upper and lower bounds on the makespan of schedules for tree dags on linear arrays

We find, in polynomial time, a schedule for a complete binary tree directed acyclic graph (dag) with n unit execution time tasks on a linear array who se makespan is optimal within a factor of 1 + o(1). Further, given a binary tree dag T with n tasks and height h, we find, in polynomial time, a sched ule for T on a linear array whose makespan is optimal within a factor of 5 + o(1). On the other hand, we prove that explicit lower and upper bounds on the mak espan of optimal schedules of binary tree dags on linear arrays differ at l east by a factor of 1 + root 2/2. We also find, in polynomial time, schedul es for bounded tree dags with n unit execution time tasks, degree d, and he ight h is an element of o(n(1/2)) boolean OR omega(n(1/2)) on a linear arra y which are optimal within a factor of 1 + o(1), this time under the assump tion of links with unlimited bandwidth. Finally, we compute an improved upper bound on the makespan of an optimal s chedule for a tree dag on the architecture independent model of Papadimitri ou and Yannakakis [14], provided that its height is not too large.