Scheduling interval ordered tasks in parallel

We present the first NC algorithm for scheduling n unit length tasks on m identical processors for the case where the precedence constraint is an interval order. Our algorithm runs on a priority concurrent read, concurrent write parallel random access machine in O(log² n) with O(n⁵) processors, or in O(log³ n) time with O(n⁴) processors. The algorithm constructs the same schedule as the one produced by the sequential algorithm (list scheduling). On the other hand, we show that when the precedence constraints are allowed to be arbitrary, the construction of the list schedule is P-Complete.