Coffman–Graham algorithm

In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound W. When W = 2, it uses the minimum possible number of distinct levels, and in general it uses at most 2 − 2/W times as many levels as necessary.

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:

...
Wikipedia