In a single machine problem with time-lags a set of jobs has to be processed in such a way that certain timing restrictions between the finishing and starting times of the jobs are satisfied.

Non-negative finish-start time-lags l_{ij} (minimal time-lags)
are extensions of classical precence constraints (l_{ij}=0) and
mean that
C_{i} + l_{ij} <= S_{j} has to be satisfied for certain
pairs (i,j)
of
jobs
where C_{i} is the completion time of job i and S_{j} is the
starting time of job j.

General relations (i,j) are denoted by prec (l_{ij}).
If the relations have a special structure (chains, tree, etc.), we write
chains (l_{ij}), tree (l_{ij}), etc.
If all time-lags l_{ij} are equal to a constant l which is part of
the input, we write prec (l),
prec (1) means that we have unit-time time-lags.
Note that the reductions in the third subgraph hold for all types of precedence
constraints like chains, intree, outtree, tree, sp-graph, prec.

For more details cf. Brucker & Knust [1999].