id: 01347057
dt: j
an: 01347057
au: Baptiste, Philippe
ti: An O$(n^4)$ algorithm for preemptive scheduling of a single machine to
    minimize the number of late jobs.
so: Oper. Res. Lett. 24, No.4, 175-180 (1999).
py: 1999
pu: Elsevier Science Publishers (North-Holland), Amsterdam
la: EN
cc: 
ut: single machine scheduling; preemptive scheduling; dynamic programming
ci: Zbl 0709.90064
li: doi:10.1016/S0167-6377(98)00045-5
ab: Summary: We study the problem of minimizing, in the preemptive case, the
    number of late jobs on a single machine $(1|pmtn,r_j|\sum U_j)$. This
    problem can be solved by Lawler’s algorithm [{\it E. L. Lawler}, Ann.
    Oper. Res. 26, 125-133 (1990; Zbl 0709.90064)] whose time and space
    complexities are respectively $O(n^5)$ and $O(n^3)$. We propose a new
    dynamic programming algorithm whose complexities are respectively
    $O(n^4)$ and $O(n^2)$.
rv: