Approximation Schemes for Minimizing the Maximum Lateness on a Single Machine with Release Times under Non-Availability or Deadline Constraints

Imed Kacem, Hans Kellerer

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 deadli…