Document Type

Technical Report

Publication Date

Winter 1-1-1980


N unit-length jobs subject to precedence constraints are to be scheduled on two processors to minimize finish time. Previous algorithms for this well-known problem begin by finding the transitive closure, and so use time 0(min(mn, n2.61)). An 0(m+nα(n)) algorithm is presented. The algorithm constructs a “lexicographic maximum schedule,” which is shown to be optimal.