Parallel two-processor scheduling for interval ordered tasks

Shows that the problem of scheduling n unit-length tasks on two identical processors, for the case where the precedence constraint is an interval order, can be solved in O(log/sup 2//spl nu/+(n log n)//spl nu/) time with O(n/spl nu//sup 2/+n/sup 2/) operations on a CREW PRAM, where /spl nu//spl les/n is a parameter. By choosing /spl nu/=/spl radic/n, we obtain an O(/spl radic/n log n)-time algorithm in O(n/sup 2/) operations. For /spl nu/=n/log n, we have an O(log/sup 2/n)-time algorithm in O(n/sup 3//log/sup 2/n) operations. The best previously-known solution takes O(log/sup 2/n) time with O(n/sup 3/ log/sup 2/n) operations on a CREW PRAM. Our improvement is mainly caused by reducing the two-processor scheduling problem for interval orders to that of finding a maximum matching in a convex bipartite graph, which is a new approach.