  In this paper, we consider four single-machine scheduling problems with
release times, with the aim of minimizing the maximum lateness. In the first
problem we have a common deadline for all the jobs. The second problem looks
for the Pareto frontier with respect to the two objective functions maximum
lateness and makespan. The third problem is associated with a non-availability
constraint. In the fourth one, the non-availibility interval is related to the
operator who is organizing the execution of jobs on the machine (no job can
start, and neither can complete during the operator non-availability period).
For each of the four problems, we establish the existence of a polynomial time
approximation scheme (PTAS).
