How to Learn the Coffman–Graham Algorithm: DAG Labels, Precedence Constraints, Two-Processor Optimality and Layered Scheduling

If every task takes one unit of time and some tasks must wait for others, how should two processors work so the whole job finishes as early as possible? The Coffman–Graham algorithm answers this important special case exactly, using a carefully constructed priority order before list scheduling begins.

This Learning Hall article develops Coffman–Graham from directed acyclic graphs and precedence constraints to successor labels, lexicographic priority, two-processor optimality, width-bounded layering, implementation details and professional limits. The central lesson is that a good schedule often begins before the first task is placed: the difficult work is creating the right order.

Quick Read

Represent tasks as a DAG: u→v means u must finish before v can start.
The classical Coffman–Graham problem assumes unit-duration tasks.
First build a special total order by labelling vertices from the sinks backwards.
Candidates are compared through the labels already assigned to their successors.
The resulting order drives a list schedule.
For two identical processors, the classical Coffman–Graham schedule is optimal for unit-time tasks with arbitrary precedence constraints.
The same ordering idea is also used in width-bounded layering of DAGs.
For more processors or richer task models, the method remains useful but its exact optimality guarantee no longer transfers unchanged.

1. Beginner Level: Scheduling Is Not Just Sorting

Suppose five one-minute tasks satisfy:

A → C
B → C
C → E
D → E

A and B may start immediately. C must wait for both. D is independent until E, and E must wait for C and D. A topological order can tell us a legal sequence, but many topological orders exist, and not all create equally good parallel schedules.

Coffman–Graham adds a priority rule designed specifically around the precedence structure.

2. The Model

The graph is directed and acyclic.
Every vertex is one task.
Every task has equal processing time, conventionally one unit.
An edge u→v means u precedes v.
There are identical processors; the strongest classical guarantee is for two.
Tasks are non-preemptive in the standard formulation: once started, they run for their unit duration.

If jobs have arbitrary durations, release dates, communication delays, resource capacities or machine-specific speeds, you have changed the scheduling problem. Do not carry an optimality theorem into a different model.

3. Why Start From the Sinks?

A sink has no successors. Since Coffman–Graham prioritises vertices partly by the structure below them, the algorithm labels from the end of the dependency graph backwards. Once all successors of a vertex are labelled, that vertex becomes eligible to receive a label.

This is a useful algorithm-design pattern: when a decision depends on information about descendants, compute the descendants first.

4. Successor-Label Signatures

For every eligible unlabeled vertex, gather the labels of its successors and sort that list in decreasing order. This ordered list is the vertex’s current signature. Candidate signatures are compared lexicographically under the convention used by the implementation.

The selected candidate receives the next label. Continue until all vertices have unique labels. Different references describe the orientation with opposite numerical directions, so implementation should state its convention explicitly rather than copy inequalities blindly.

5. A Consistent Labelling Convention

One useful convention is:

label = 1
while unlabeled vertices remain:
    eligible = vertices whose successors are all labeled
    for each v in eligible:
        signature(v) = successor labels sorted descending
    choose eligible v with lexicographically smallest signature
    assign v the current label
    label += 1

Sinks begin with empty signatures and therefore appear first in this reverse construction. The scheduling phase then uses the labels in the corresponding priority direction.

6. The List-Scheduling Phase

Now move forward in time. A task is ready when all its predecessors have completed. At each time slot, fill available processors with the highest-priority ready tasks according to the Coffman–Graham order.

while unfinished tasks remain:
    ready = unfinished tasks whose predecessors are complete
    choose up to m ready tasks by Coffman–Graham priority
    run them for one unit
    mark them complete

The remarkable part is that for m=2 under the classical assumptions, this priority construction is not merely a heuristic: it gives an optimal schedule length.

7. Why an Ordinary Topological Order Is Not Enough

Kahn’s algorithm or DFS can generate a legal topological order, but legality and quality are different questions. A poor tie-break can postpone a task that unlocks a long chain, causing one processor to sit idle later.

Coffman–Graham’s successor-aware labelling anticipates future precedence pressure. It prefers tasks according to the structure that lies downstream, not simply alphabetically or by discovery time.

8. The Two-Processor Optimality Result

Coffman and Graham proved that their method finds a minimum-length non-preemptive schedule for unit-execution-time tasks with arbitrary precedence constraints on two identical processors. Later work improved implementation complexity and analysed behaviour for more processors.

This is exactly the kind of theorem professionals must quote with its assumptions attached. “Coffman–Graham is optimal” is incomplete. “Coffman–Graham is optimal for the classical two-processor, unit-task, precedence-constrained model” is meaningful.

9. More Than Two Processors

With m processors, the same scheduling idea can be used, but the exact two-processor theorem does not magically generalise. Classical worst-case analysis gives approximation information rather than universal optimality.

That boundary is educationally valuable: algorithms often have a narrow region where a strong theorem holds and a wider region where the method is still useful but must be judged as a heuristic or approximation.

10. Coffman–Graham as a Layering Algorithm

The ordering is also used to place vertices into layers of bounded width. Think of each layer as a time slot or drawing rank that can contain at most W vertices. Vertices are considered according to the Coffman–Graham order and placed as low as possible while respecting edges and the width limit.

This connection explains why the algorithm appears in both scheduling theory and hierarchical graph drawing. A processor capacity and a layer-width capacity are structurally similar constraints.

11. Transitive Edges and Input Normalisation

If A→B and B→C, an explicit A→C edge does not change the partial order, but it changes successor lists. Implementations should understand whether their chosen formulation assumes a transitive reduction or tolerates redundant precedence edges.

For learning, use small DAGs and keep every edge meaningful. For production, document whether preprocessing removes redundant edges and confirm that doing so preserves the intended scheduling semantics.

12. Data Structures

Adjacency lists for successors and predecessors.
A count of unlabeled successors during the reverse labelling phase.
Compact successor-label signatures or an ordering structure that avoids repeatedly sorting full lists.
Ready queues keyed by Coffman–Graham priority during scheduling.
Explicit task IDs separate from labels so re-labelling does not corrupt graph identity.

The original presentation is often described in O(n²)-style terms; subsequent work, including Sethi’s, developed faster implementations. This is another professional lesson: an algorithmic idea and its first implementation complexity are not always the same thing.

13. Implementation Failure Modes

Running it on a cyclic graph: the precedence relation must be acyclic.
Mixing edge orientation: decide whether u→v means u precedes v and keep that convention everywhere.
Reversing the lexicographic rule: references use different label orientations; test against a known example.
Scheduling before predecessors finish: priority never overrides feasibility.
Assuming arbitrary task lengths: classical optimality uses unit execution times.
Assuming optimality for m>2: the guarantee changes.
Ignoring redundant edges: input representation can affect a naive signature implementation.
Using unstable accidental tie-breaks: define deterministic task-ID tie-breaking for reproducible tests.

14. How to Test It

Verify every produced schedule respects every edge.
For small n, enumerate all legal two-processor schedules and confirm Coffman–Graham achieves the minimum makespan.
Test chains, antichains, diamonds, forks, joins and disconnected DAG components.
Add redundant transitive edges and check whether your documented input policy gives consistent results.
Randomly generate small DAGs and compare against an exact search or integer-programming oracle.
Check deterministic output under task-name permutations.

15. Beginner-to-Professional Learning Ladder

Beginner: draw precedence DAGs and identify ready tasks at each time step.
Intermediate: compute successor-label signatures by hand and construct the priority order.
Advanced: implement labelling plus list scheduling and exhaustively verify small two-processor instances.
Professional: formalise task duration, release, resource and communication assumptions; benchmark against exact or modern heuristic schedulers; and state precisely which guarantee still applies.

16. How to Teach and Learn the Priority Rule

Do not begin with code. Give learners a DAG and ask them to predict which sink should receive the first label. Then reveal the successor signatures, run the rule, investigate one tie, modify one edge and observe how the order changes. Only after the dependency between future structure and present priority is understood should the procedure be coded.

This Predict–Run–Investigate–Modify–Make progression and subgoal labelling reduce the temptation to memorise a lexicographic recipe without understanding what it protects.

17. Practice Problems

Find three different topological orders of the same DAG and compare their two-processor makespans.
Label a six-vertex DAG using a declared Coffman–Graham convention.
Construct a case where an arbitrary ready-task tie-break creates avoidable idle time.
Brute-force all schedules for a small DAG and verify the Coffman–Graham result.
Change one task from unit duration to duration two and explain why the classical theorem no longer directly applies.
Implement width-bounded layering and compare it visually with ordinary longest-path layering.
Measure how much time your implementation spends constructing successor signatures versus scheduling.

18. Sources and Further Reading

Final idea: Coffman–Graham is not “just another topological sort”. It shows how a legal partial order can be refined into a priority order whose future-aware structure changes the quality of parallel execution. The professional habit is to separate feasibility, priority and guarantee: first define what schedules are legal, then design the priority rule, then prove or measure what that rule buys you.

Small Group Tutorials