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.
Gabow, Harold N., "An Almost-Linear Algorithm for Two Processor Scheduling ; CU-CS-169-80" (1980). Computer Science Technical Reports. 167.