Potts, C. N.; Wassenhove, L. N. Van - In: Management Science 34 (1988) 7, pp. 843-858
This paper considers the problem of scheduling n jobs, each having a processing time, a due date and a weight, on a single machine to minimize the weighted number of late jobs. An O(n log n) algorithm is given for solving the linear programming problem obtained by relaxing the integrality...