Precedence Constraint (Scheduling)

computation scheduling

Definition

Precedence Constraint

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

Here is the completion time of job , and is the start time of job . A set of precedence constraints is usually modelled as a partial order on the job set .

Feasibility

Order preservation

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

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 is usually acyclic and transitive. Hence it can be represented by a directed acyclic graph, where an edge means that is an immediate prerequisite of .

If and , then . Therefore job 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 means that job must complete before job may start.

For example, the constraints

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 in the field states that precedence constraints are part of the instance:

Example

Household chores

Some chores must be completed before others. For example,

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