Coffman–Graham algorithm

It is named after Edward G. Coffman, Jr. and Ronald Graham, who published it in 1972 for an application in job shop scheduling. In this application, the elements to be ordered are jobs, the bound W is the number of jobs that can be scheduled at any one time, and the partial order describes prerequisite relations between the jobs. The goal is to find a schedule that completes all jobs in minimum total time. Subsequently, the same algorithm has also been used in graph drawing, as a way of placing the vertices of a directed graph into layers of fixed widths so that most or all edges are directed consistently downwards.

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. If the transitive reduction is not given, it takes polynomial time to construct it.

Problem statement and applications

In the version of the job shop scheduling problem solved by the Coffman–Graham algorithm, one is given a set of n jobs J₁, J₂, ..., J_n, together with a system of precedence constraints J_i < J_j requiring that job J_i be completed before job J_j begins. Each job is assumed to take unit time to complete. The scheduling task is to assign each of these jobs to time slots on a system of W identical processors, minimizing the makespan of the assignment (the time from the beginning of the first job until the completion of the final job). 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. This application was the original motivation for Coffman and Graham to develop their algorithm.

In the layered graph drawing framework outlined by Sugiyama, Tagawa & Toda (1981) the input is a directed graph, and a drawing of a graph is constructed in several stages:

1. A feedback arc set is chosen, and the edges of this set reversed, in order to convert the input into a directed acyclic graph with (if possible) few reversed edges.
2. The vertices of the graph are given integer y-coordinates in such a way that, for each edge, the starting vertex of the edge has a higher coordinate than the ending vertex, with at most W vertices sharing the same y-coordinate. In this way, all edges of the directed acyclic graph and most edges of the original graph will be oriented consistently downwards.
3. Dummy vertices are introduced within each edge so that the subdivided edges all connect pairs of vertices that are in adjacent levels of the drawing.
4. Within each group of vertices with the same y-coordinate, the vertices are permuted in order to minimize the number of crossings in the resulting drawing, and the vertices are assigned x-coordinates consistently with this permutation.
5. The vertices and edges of the graph are drawn with the coordinates assigned to them.

In this framework, the y-coordinate assignment again involves grouping elements of a partially ordered set (the vertices of the graph, with the reachability ordering on the vertex set) into layers (sets of vertices with the same y-coordinate), which is the problem solved by the Coffman–Graham algorithm. Although there exist alternative approaches than the Coffman–Graham algorithm to the layering step, these alternatives in general are either not able to incorporate a bound on the maximum width of a level or rely on complex integer programming procedures.

More abstractly, both of these problems can be formalized as a problem in which the input consists of a partially ordered set and an integer W. The desired output is an assignment of integer level numbers to the elements of the partially ordered set such that, if x < y is an ordered pair of related elements of the partial order, the number assigned to x is smaller than the number assigned to y, such that at most W elements are assigned the same number as each other, and minimizing the difference between the smallest and the largest assigned numbers.