An efficient parallel algorithm for scheduling interval ordered tasks

AbstractWe present an efficient parallel algorithm for scheduling n unit length tasks on m identical processors when the precedence graphs are interval orders. Our algorithm requires O(log2v+(nlogn)/v) time and O(nv2+n2) operations on the CREW PRAM, where v can be any number between 1 and n. By choosing v=n, we obtain an O(nlogn)-time algorithm with O(n2) operations. For v=n/logn, we have an O(log2n)-time algorithm with O(n3/log2n) operations. The previous solution takes O(log2n) time with O(n3log2n) operations on the CREW PRAM. Our improvement is mainly due to a simple dynamic programming recurrence for computing the lengths of optimal schedules and a reduction of the m-processor scheduling problem for interval orders to that of finding a maximum matching in a convex bipartite graph