For a partial ordering given by its transitive reduction (covering relation), the Coffman–Graham algorithm can be implemented in linear time using the partition refinement data structure as a subroutine.
Abstractly, the precedence constraints define a partial order on the jobs, so the problem can be rephrased as one of assigning the elements of this partial order to levels (time slots) in such a way that each time slot has at most as many jobs as processors (at most W elements per level), respecting the precedence constraints.
A related algorithm can be used to minimize the total flow time for a version of the problem in which preemption of jobs is allowed.
[11] Coffman & Graham (1972) and Lenstra & Rinnooy Kan (1978)[12] state the time complexity of the Coffman–Graham algorithm, on an n-element partial order, to be O(n2).
Sethi (1976) shows how to implement the topological ordering stage of the algorithm in linear time, based on the idea of partition refinement.
[13] Sethi also shows how to implement the level assignment stage of the algorithm efficiently by using a disjoint-set data structure.