Eugene L. Lawler

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-83-139
October 1983

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/CSD-83-139.pdf

Suppose n jobs, each with a specified release date, due date and processing time, are to be scheduled for processing by a single machine, with the objective of minimizing the number of jobs that are not completed by their due dates. Three results, in the form of two algorithms and one NP-completeness proof, are presented. Our first result is to show that if release dates and due dates are "compatible," i. e. similarly ordered, an optimal schedule can be found in O( n log n) time by a procedure that is a natural generalization of that of Moore for the case in which all release dates are equal. This result improves on an O( n squared) solution to this problem by Kise, Ibaraki and Mine. For our second result, no particular relationship is assumed between the release dates and the due dates and the schedule is allowed to be preemptive. We show that a schedule minimizing the weighted number of late jobs can be found in O( n cubed W cubed) time where W is the sum of the integer weights assigned to the jobs. If the jobs are unweighted, then in effect W = n and the time bound reduces to O( n to the 6th power), thereby yielding a polynomial-bounded algorithm for a problem for which no such solution procedure was previously known. For our third result, we suppose that all release dates are equal and that each job has a deadline in addition to its due date. We show that it is an NP-hard problem to minimize the number of late jobs (with respect to due dates) while observing all deadlines. This result resolves an open question suggested by a result of J. Sidney.

BibTeX citation:

@techreport{Lawler:CSD-83-139,
    Author = {Lawler, Eugene L.},
    Title = {Scheduling a Single Machine to Minimize the Number of Late Jobs},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1983},
    Month = {Oct},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/6344.html},
    Number = {UCB/CSD-83-139},
    Abstract = {Suppose <i>n</i> jobs, each with a specified release date, due date and processing time, are to be scheduled for processing by a single machine, with the objective of minimizing the number of jobs that are not completed by their due dates. Three results, in the form of two algorithms and one NP-completeness proof, are presented. Our first result is to show that if release dates and due dates are "compatible," i. e. similarly ordered, an optimal schedule can be found in O(<i>n log n</i>) time by a procedure that is a natural generalization of that of Moore for the case in which all release dates are equal. This result improves on an O(<i>n squared</i>) solution to this problem by Kise, Ibaraki and Mine. For our second result, no particular relationship is assumed between the release dates and the due dates and the schedule is allowed to be preemptive. We show that a schedule minimizing the weighted number of late jobs can be found in O(<i>n cubed W cubed</i>) time where <i>W</i> is the sum of the integer weights assigned to the jobs.  If the jobs are unweighted, then in effect <i>W</i> = <i>n</i> and the time bound reduces to O(<i>n</i> to the 6th power), thereby yielding a polynomial-bounded algorithm for a problem for which no such solution procedure was previously known. For our third result, we suppose that all release dates are equal and that each job has a deadline in addition to its due date. We show that it is an NP-hard problem to minimize the number of late jobs (with respect to due dates) while observing all deadlines.  This result resolves an open question suggested by a result of J. Sidney.}
}

EndNote citation:

%0 Report
%A Lawler, Eugene L.
%T Scheduling a Single Machine to Minimize the Number of Late Jobs
%I EECS Department, University of California, Berkeley
%D 1983
%@ UCB/CSD-83-139
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1983/6344.html
%F Lawler:CSD-83-139