Minimizing maximum absolute lateness and range of lateness under generalized due dates on a single machine

We investigate the problems of minimizing the maximum absolute lateness and range of lateness under generalized due dates on a single machine. In contrast to the traditional due date cases, we show that these problems are unary NP-hard. Furthermore, we present simple approximation algorithms for these problems, and show that they achieve the performance ratios of n for the problem of minimizing the maximum absolute lateness and of ⌈n/2⌉ for the problem of minimizing the range of lateness, where ⌈x⌉ is the smallest integer no less than x.