This paper is devoted to the following version of the single machine
preemptive scheduling problem of minimizing the weighted number of late
jobs. A processing time, a release date, a due date and a weight of each
job are given. Certain jobs are specified to be completed in time, i.e.,
their due dates are assigned to be deadlines, while the other jobs are
allowed to be completed after their due dates. The release/due date
intervals are nested, i.e., no two of them overlap (either they have at most
one common point or one covers the other).
Necessary and sufficient conditions for the completion of all jobs in time
are considered, and an
O(nlogn) algorithm (where n is
the number of jobs) is proposed for solving the problem of minimizing
the weighted number of late jobs in case of oppositely ordered processing
times and weights.