An O(n(4)) algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

We study the problem of minimizing, in the preemptive case, the number of l ate jobs on a single machine (1 /pmtn, r(j) / Sigma U-j). This problem can be solved by Lawler's algorithm [E.L. Lawler, Ann. Oper. Res. 26 (1990) 125 -133] whose time and space complexities are respectively O(n(5)) and O(n(3) ). We propose a new dynamic programming algorithm whose complexities are re spectively O(n(4)) and O(n(2)). (C) 1999 Elsevier Science B.V. All rights r eserved.