Precedence Constraint (Scheduling)

computation scheduling

Definition

Precedence Constraint

A precedence constraint in scheduling is an ordering requirement between jobs. If $i\prec j$, then job $j$ may start only after job $i$ has completed:

$$C_i\le S_j.$$

Here $C_i$ is the completion time of job $i$, and $S_j$ is the start time of job $j$. A set of precedence constraints is usually modelled as a partial order on the job set $J$.

Feasibility

Order preservation

A schedule is feasible with respect to a precedence relation $\prec$ only if

$$\forall i,j\in J:i\prec j⟹C_i\le S_j.$$

The constraint is about time, not necessarily about machine assignment. Two jobs related by precedence may run on different machines, but the successor cannot start before the predecessor has completed.

Structure

The relation $\prec$ is usually acyclic and transitive. Hence it can be represented by a directed acyclic graph, where an edge $i\to j$ means that $i$ is an immediate prerequisite of $j$.

If $i\prec j$ and $j\prec k$, then $i\prec k$. Therefore job $k$ cannot start until both direct and indirect predecessors have completed.

Directed graph

Precedence constraints can be modelled by a directed acyclic graph. Vertices are jobs. An edge $i\to j$ means that job $i$ must complete before job $j$ may start.

For example, the constraints

$$1\prec 2,1\prec 3,2\prec 4,2\prec 5,3\prec 5,4\prec 5,5\prec 6$$

can be drawn as follows.

The graph must be acyclic. A cycle would require some job to be completed before itself, directly or indirectly, which makes the precedence constraints infeasible.

Notation

In scheduling notation, the symbol $\mathrm{prec}$ in the $\beta$ field states that precedence constraints are part of the instance:

$$\alpha \mid \mathrm{prec}\mid \gamma .$$

Example

Household chores

Some chores must be completed before others. For example,

$$\text{vacuum}\prec \text{mop}\text{and}\text{prepare dinner}\prec \text{wash dishes}.$$

With two people, unrelated chores can run in parallel, but a successor must wait for its prerequisite to finish.