id: 01299362
dt: j
an: 01299362
au: Tanaka, Keisuke; Vlach, Milan
ti: Minimizing maximum absolute lateness and range of lateness under
    generalized due dates on a single machine.
so: Ann. Oper. Res. 86, 507-526 (1999).
py: 1999
pu: Springer, Dordrecht
la: EN
cc: 
ut: maximum absolute lateness; range of lateness; generalized due dates; single
    machine
ci: 
li: doi:10.1023/A:1018987625819
ab: Summary: 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$.
rv: