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 ts,j, then the string's processing time may be defined as ts = ∑{ ts,j : j ∈ s }. Mean string flowtime is minimized by applying the SPT rule to the strings. On the other hand, if we wish to minimize mean job flowtime then the WSPT rule must be used, the weight of a string being the number of jobs it contains. Mean weighted job flowtime may be minimized by WSPT sequencing in which a string has the total weight of all jobs it contains.
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{di : 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 L1i ≤ L0k for some job k. If di ≥ dj then L1i ≤ L0j and the proof is complete. Otherwise,
dj > di ≥ d'i by definition of d' ≥ d'j as j → i in S = dk for some successor k of j, as dj > d'j. Thus L1i = C1i − di = C0j − di ≤ C0j − dk as di≥ dk = L0k
and hence L1i < L0k 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) = ∑{ ti : i ∈ f } and let w(f) = ∑{ wi : i ∈ f }. Let uj be the collection of all feasible subsets that have j as the lead job. For any job j, define z(j) = min{ t(f)/w(f) : f ∈ uj }, and let fj be the largest member of uj that minimizes z(j). The following algorithm may be used to minimize the mean weighted flow time (assembly) in a branching forest if all jobs are initially available.
From the set of all jobs j with no predecessors, determine the smallest z(j) and the corresponding largest fj as defined above. Schedule job j, followed by an optimal schedule of the rest of fj, 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.
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 f which minimizes t(f)/w(f). Schedule f optimally, followed by the rest of the jobs not in f.
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.