We show that the problem of scheduling n unit length tasks on two identical processors for the case that the precedence constraint is an interval order can be solved in O(log~2 v +(n logn)/v) time with O(nv~2 +m~2) oper-ations on the CREW PRAM, where v <= n is a param-eter. By choosing v = n~(1/2), we obtain an O(n~1/2log n)-time algorithm in O(n~2) operations. For v = n/log~2n) operations. The best previously known solution takes O(log~2 n) time with O(n~3 log~2 n) operations on the CREW PRAM. Our improvement is mainly caused by reducing the two-processor scheduling problem for in-terval orders to that of finding a maximum matching in a conver bipartite graph, which is a new approach.
展开▼
