Scheduling Graphs on Two Processors

Consider a directed acyclic graph (dag) D with n nodes and e edges. D represents a task system; a node corresponds to a task, and an edge $(x,y)$ means that task x must be finished before task y can be started. We shall restrict attention to systems in which all tasks require the same processing time. Coffman and Graham give an algorithm for determining nonpreemptive schedules on two processors for such systems. The first part of their algorithm assigns unique labels to nodes. The second part uses these labels to construct a list schedule (in the sense of Graham). The time taken for each part is O(n² ). We give an algorithm to determine the labeling in $O(n + e)$ steps. Similar algorithms have independently been devised to test undirected graphs for chordality. We give a second algorithm to construct a schedule from the labeling in O(nα (n) + e) steps. α (n) is an almost constant function of n.