The Two-Processor Scheduling Problem is in Random NC
Umesh V. Vazirani, Vijay V. Vazirani · SIAM Journal on Computing · 1989
An efficient parallel algorithm $({\text{RNC}}^2 )$ for the two-processor scheduling problem is presented. An interesting feature of this algorithm is that it finds a highest-level-first schedule; such a schedule defines a lexicographically first solution to this problem in a natural way. A key ingredient of the algorithm is a generalization of a theorem of Tutte which establishes a one-to-one correspondence between the bases of the Tutte matrix of a graph and the sets of matched nodes in maximum matchings in the graph.