Coffman–Graham algorithm

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 J1, J2, ..., J**n, together with a system of precedence constraints Ji j* requiring that job Ji be completed before job Jj 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.{{citation

In the layered graph drawing framework outlined by 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.{{citation

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 {{math|x

The algorithm

The Coffman–Graham algorithm performs the following steps.

1. Represent the partial order by its transitive reduction or covering relation, a directed acyclic graph G that has an edge from x to y whenever {{math|x
2. Construct a topological ordering of G in which the vertices are ordered lexicographically by the set of positions of their incoming neighbors. To do so, add the vertices one at a time to the ordering, at each step choosing a vertex v to add such that the incoming neighbors of v are all already part of the partial ordering, and such that the most recently added incoming neighbor of v is earlier than the most recently added incoming neighbor of any other vertex that could be added in place of v. If two vertices have the same most recently added incoming neighbor, the algorithm breaks the tie in favor of the one whose second most recently added incoming neighbor is earlier, etc.
3. Assign the vertices of G to levels in the reverse of the topological ordering constructed in the previous step. For each vertex v, add v to a level that is at least one step higher than the highest level of any outgoing neighbor of v, that does not already have W elements assigned to it, and that is as low as possible subject to these two constraints.

Analysis

Output quality

As originally proved, their algorithm computes an optimal assignment for ; that is, for scheduling problems with unit length jobs on two processors, or for layered graph drawing problems with at most two vertices per layer. A closely related algorithm also finds the optimal solution for scheduling of jobs with varying lengths, allowing pre-emption of scheduled jobs, on two processors.{{citation

As well as finding schedules with small makespan, the Coffman–Graham algorithm (modified from the presentation here so that it topologically orders the reverse graph of G and places the vertices as early as possible rather than as late as possible) minimizes the total flow time of two-processor schedules, the sum of the completion times of the individual jobs. 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.{{citation

Time complexity

and {{citation | hdl-access = free

References

References

1. Leung, Joseph Y.-T.. (2004). "Handbook of Scheduling: Algorithms, Models, and Performance Analysis". CRC Press.
2. (1981). "Methods for visual understanding of hierarchical system structures". [[IEEE Systems, Man, and Cybernetics Society.
3. (2001). "Drawing Graphs: Methods and Models". Springer-Verlag.
4. (1999). "Graph Drawing: Algorithms for the Visualization of Graphs". Prentice Hall.