SINGLE-MACHINE SCHEDULING WITH RELEASE AND DUE-DATE ASSIGNMENT TO MINIMIZE THE WEIGHTED NUMBER OF LATE JOBS

The problem of scheduling a jobs with unequal, in general, processing times and total processing time equal to a on a single machine to mini mize the weighted number of late jobs is considered. Each of the a tim e units with integer end points in the interval [0, a] is to be assign ed to a job so that the beginning of the time unit be the release date of the job and the end of the unit be its due date. Two rules for ass igning release and due dates are considered. For both, the problem is shown to be NP-hard in the strong sense in the nonpreemptive case even for equal job weights, and solvable in O(n) time in the preemptive ca se. (C) 1998 Published by Elsevier Science B.V. All rights reserved.