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 lij (minimal time-lags) are extensions of classical precence constraints (lij=0) and mean that Ci + lij <= Sj has to be satisfied for certain pairs (i,j) of jobs where Ci is the completion time of job i and Sj is the starting time of job j.

General relations (i,j) are denoted by prec (lij). If the relations have a special structure (chains, tree, etc.), we write chains (lij), tree (lij), etc. If all time-lags lij 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].