We present an efficient parallel algorithm for scheduling n unit length tasks on m identical processors when the precedence graphs are interval orders. The previous solution takes O(log sup(2)) time with O(n sup(3)log sub(n) sup(2)) operations on the CREW PRAM. Our improvement is mainly due to a reduction of the m-processor scheduling problem for interval orders to that of finding a maximum matching in a convex bipartite graph.
展开▼
