Skip to main content
SpringerLink
Log in

A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs

  • Single-Machine Scheduling
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The scheduling problem 1|pmtn, r j|Σw jU j calls forn jobs with arbitrary release dates and due dates to be preemptively scheduled for processing by a single machine, with the objective of minimizing the sum of the weights of the late jobs. A dynamic programming algorithm for this problem is described. Time and space bounds for the algorithm are, respectively,O(nk 2W 2) andO(k 2W), wherek is the number of distinct release dates andW is the sum of the integer job weights. Thus, for the problem 1|pmtn, r j|ΣU j, in which the objective is simply to minimize the number of late jobs, the pseudopolynomial time bound becomes polynomial, i.e.O(n 3k 2).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. K.R. Baker, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Preemptive scheduling of a single machine to minimize cost subject to release dates and precedence constraints, Oper. Res. 31(1983)381–386.

    Article  Google Scholar 

  2. R. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discr. Math. 2(1979)75–90.

    Google Scholar 

  3. H. Kise, T. Ibaraki and H. Mine, A solvable case of the one-machine scheduling problem with ready and due dates, Oper. Res. 26(1978)121–126.

    Article  Google Scholar 

  4. E.L. Lawler and J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Manag. Sci. 16(1969)77–84.

    Article  Google Scholar 

  5. E.L. Lawler, Sequencing to minimize the weighted number of tardy jobs, Rev. Française Automatique, Informatique, Recherche Operationnel, 10 supp. (1976) 27–33.

    Article  Google Scholar 

  6. E.L. Lawler, Three variations of Moore's algorithm for minimizing the number of late jobs, in preparation.

  7. J.M. Moore, Sequencingn jobs on one machine to minimize the number of tardy jobs, Manag. Sci. 15(1968)102–109.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Division, University of California, 94720, Berkeley, CA, USA

    E. L. Lawler

Authors
  1. E. L. Lawler
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lawler, E.L. A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Ann Oper Res 26, 125–133 (1990). https://doi.org/10.1007/BF02248588

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02248588

Keywords

Search

Navigation