Complexity results for single-machine problems with positive finish-start time-lags

In a single-machine problem with time-lags a set of jobs has to be processe d on a single machine in such a way that certain timing restrictions betwee n the finishing and starting times of the jobs are satisfied and a given ob jective function is minimized. We consider the case of positive finish-star t time-lags l(ij) which mean that between the finishing time of job i and t he starting time of job j the minimal distance l(ij) has to be respected. N ew complexity results are derived for single-machine problems with constant positive time-lags l(ij) = l which also lead to new results for Bow-shop p roblems with unit processing times and job precedences.