Single machine problems with non-negative time-lags

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].