Scheduling loosely connected task graphs

摘要

We present a polynomial time algorithm for precedence-constrained scheduling problems in which the task graph can be partitioned into large disjoint parts by removing edges with high float, where the float of an edge is defined as the difference between the length of the longest path in the graph and the length of the longest path containing the edge. Our algorithm guarantees schedules within a factor 1.875 of the optimal independent of the number of processors. The best-known factor for this problem and in general is 2−2p, where p is the number of processors, due to Coffman–Graham. Our algorithm is unusual and considerably different from that of Coffman–Graham and other algorithms in the literature.