In this section we will consider single machine
scheduling in which
precedence constraints
exist between some or all of the jobs.
We will use the notation `i→j` (`i` precedes `j`) to indicate that
job `i` must be completed before job `j` can start processing.
Similarly we will use `j←i` to indicate that `j` follows `i`.
If `i→j` and there is no job `k` such that `i→k→j`
then `i` is the
direct predecessor
of `j`, and `j` is the
direct successor
of `i`.

The relationship between jobs is easier to visualize if the precedences are represented by a directed graph in which the nodes are jobs and the directions of the arcs are the precedence relations. A directed circuit is impossible in such a graph as it would represent a set of jobs none of which could be started before all others in the set were completed. If i→k, k→j, and i→j are three precedence constraints, then the third constraint is redundant as it is implied by the other two. If all such redundant arcs are deleted and the resulting graph contains no undirected circuits, it will be a directed forest (or branching), each component being a rooted tree (or arborescence). If a tree has a unique node without predecessors, it is known as a branching tree, the root node being called the lead job. If a tree has a unique node without successors, it is known as an assembly tree, the root node being called the terminal job.

If the precedence constraints can be represented by a graph that is both an assembly forest and a branching forest, then each component is known as a string. In addition, we require that all jobs within a string be processed together without interruption. Each string consists of a set of jobs whose relative order is uniquely determined by the precedence constraints, and so the scheduling problem is reduced to finding an optimal ordering of the strings.

If the processing time in string s of job `j` is `t _{s,j}`,
then the string's processing time may be defined as

When ready dates are not significant, then the
maximum lateness
can be minimized by a modified version of the EDD rule.
Each job is assigned a modified due date equal to the earliest due date of
itself and all its successors.
That is,
`d' _{j} = min{d_{i} : i is j or a successor of j}`.
If the jobs are then arranged in ascending modified due date order,
with ties being broken by use of the precedence constraints, the resulting schedule is optimal.

The proof of this is identical to that given for EDD schedules
minimizing maximum lateness, except in showing that
`L ^{1}_{i} ≤ L^{0}_{k}`
for some job

d_{j}> d_{i}≥ d'by definition of_{i}d'≥ d'as_{j}j→iinS= dfor some successor_{k}kof j, asd. Thus_{j}> d'_{j}L^{1}_{i}= C^{1}_{i}− d_{i}= C^{0}_{j}− d_{i}≤ Cas^{0}_{j}− d_{k}d_{i}≥ d_{k}= L^{0}_{k}

and hence `L ^{1}_{i} < L^{0}_{k}` and the proof is complete.

Any subset of a branching tree which is itself a branching tree is known as a
feasible subset.
For a feasible subset `f`,
let `t(f) = ∑{ t _{i} : i ∈ f }`
and let

From the set of all jobs

jwith no predecessors, determine the smallestz(j)and the corresponding largestfas defined above. Schedule job_{j}j, followed by an optimal schedule of the rest off, followed by an optimal schedule of all remaining jobs. Note that because we start with a branching forest the two required subschedules may be found using the same algorithm._{j}

Suppose the precedence constraints of a set of jobs do not form a branching tree.
We may generalize the concept of a feasible subset to that of an
initial set:
If `i` is in an initial set and `k` → i, then `k` must also be in the initial set.
Using initial sets in place of feasible sets, we get
Sidney's algorithm
[Sidney, J.B. One machine sequencing with precedence relations and deferral costs

. Working Papers 124 and 125,
Faculty of Commerce and Business Administration, Univeersity of British Columbia (1972)].

Determine the initial set

fwhich minimizest(f)/w(f). Schedulefoptimally, followed by the rest of the jobs not inf.

As before we may use the algorithm recursively to find the optimal subschedules,
but because set `f` no longer has a unique lead job, it is possible that `f` may
include all jobs, in which case there would be little use in using the same
algorithm.