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

We investigate the problems of minimizing the maximum absolute lateness and range oflateness under generalized due dates on a single machine. In contrast to the traditional duedate cases, we show that these problems are unary NP‐hard. Furthermore, we present simpleapproximation algorithms for these problems, and show that they achieve the performanceratios of n for the problem of minimizing the maximum absolute lateness and of [ n/2 ] forthe problem of minimizing the range of lateness, where [ x ] is the smallest integer no lessthan x.