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 cont rast to the traditional due date cases, we show that these problems are una ry NP-hard. Furthermore, we present simple approximation algorithms for the se problems, and show that they achieve the performance ratios of n for the problem of minimizing the maximum absolute lateness and of inverted right perpendicular n/2 inverted left perpendicular for the problem of minimizing the range of lateness, where inverted right perpendicular x inverted left perpendicular is the smallest integer no less than x.