Skip to main content
SpringerLink
Log in

Preemptive Scheduling of. Precedence-Constrained Jobs on Parallel Machines

  • Conference paper
Deterministic and Stochastic Scheduling

Part of the book series: NATO Advanced Study Institutes Series ((ASIC,volume 84))

Abstract

Polynomial time-bounded algorithms are presented for solving three problems involving the preemptive scheduling of precedence-constrained jobs on parallel machines: the “intree problem”, the “two-machine problem with equal release dates”, and the “general two-machine problem”. These problems are preemptive counterparts of problems involving the nonpreemptive scheduling of unit-time jobs previously solved by Brucker, Garey and Johnson and by Garey and Johnson. The algorithms and proofs (and the running times of the algorithms) closely parallel those presented in their papers. These results improve on previous results in preemptive scheduling and also suggest a close relationship between preemptive scheduling problems and problems in nonpreemptive scheduling of unit-time jobs.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. P. Brucker, M.R. Garey, D.S. Johnson (1977) Scheduling equal length tasks under tree-like precedence constraints to minimize maximum lateness. Math. Oper. Res. 2, 275–284.

    Article  MathSciNet  MATH  Google Scholar 

  2. M.R. Garey, D.S. Johnson (1976) Scheduling tasks with non-uniform deadlines on two processors. J. Assoc. Comput. Mach. 23, 461–467.

    MathSciNet  MATH  Google Scholar 

  3. M.R. Garey, D.S. Johnson (1977) Two-processor scheduling with start times and deadlines. SIAM J. Comput. 6, 416–426.

    Article  MathSciNet  MATH  Google Scholar 

  4. T.F. Gonzalez, D.B. Johnson (1980) A new algorithm for preemptive scheduling of trees. J. Assoc. Comput. Mach. 27, 287–312.

    MathSciNet  MATH  Google Scholar 

  5. R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326.

    Article  MathSciNet  MATH  Google Scholar 

  6. E.C. Horvath, S. Lam, R. Sethi (1977) A level algorithm for preemptive scheduling. J. Assoc. Comput. Mach. 24, 32–43.

    MathSciNet  MATH  Google Scholar 

  7. J.K. Lenstra. Private communication.

    Google Scholar 

  8. N. Megiddo (1979) Combinatorial optimization with rational objective functions. Math. Oper. Res. 4, 414–423.

    Article  MathSciNet  MATH  Google Scholar 

  9. C.L. Monma (1979) Linear-time algorithm for scheduling equal-length tasks with due dates subject to precedence constraints. Technical Memorandum 79-1712, Bell Laboratories, Holmdel, NJ.

    Google Scholar 

  10. R.R. Muntz, E.G. Coffman, Jr. (1969) Optimal preemptive scheduling on two-processor systems. IEEE Trans. Comput. C-18, 1014–1020.

    Article  Google Scholar 

  11. R.R. Muntz, E.G. Coffman, Jr. (1970) Preemptive scheduling of real-time tasks on multiprocessor systems. J. Assoc. Comput. Mach. 2, 324–338.

    MathSciNet  Google Scholar 

  12. S. Sahni, Y. Cho (1979) Nearly on line scheduling of a uniform processor system with release times. SIAM J. Comput. 8, 275–285.

    Article  MathSciNet  MATH  Google Scholar 

  13. J.D. Ullman (1975) NP-Complete scheduling problems. J. Comput. System Sci. 10, 384–393.

    Article  MathSciNet  MATH  Google Scholar 

  14. J.D. Ullman (1976) Complexity of sequencing problems. In: E.G. Coffman, Jr. (ed.) (1976) Computer & Job/Shop Scheduling Theory, Wiley, New York, 139–164

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of California, Berkeley, USA

    E. L. Lawler

Authors
  1. E. L. Lawler
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Mathematics, Dalhousie University, Halifax, Nova Scotia, Canada

    M. A. H. Dempster

  2. Balliol College, Oxford, England

    M. A. H. Dempster

  3. Mathematisch Centrum, P.O. Box 4079, 1009 AB, Amsterdam, The Netherlands

    J. K. Lenstra

  4. Econometric Institute H2-11, Erasmus University, P.O. Box 1738, 3000 DR, Rotterdam, The Netherlands

    A. H. G. Rinnooy Kan

Rights and permissions

Reprints and permissions

Copyright information

© 1982 D. Reidel Publishing Company

About this paper

Cite this paper

Lawler, E.L. (1982). Preemptive Scheduling of. Precedence-Constrained Jobs on Parallel Machines. In: Dempster, M.A.H., Lenstra, J.K., Rinnooy Kan, A.H.G. (eds) Deterministic and Stochastic Scheduling. NATO Advanced Study Institutes Series, vol 84. Springer, Dordrecht. https://doi.org/10.1007/978-94-009-7801-0_6

Download citation

  • DOI: https://doi.org/10.1007/978-94-009-7801-0_6

  • Publisher Name: Springer, Dordrecht

  • Print ISBN: 978-94-009-7803-4

  • Online ISBN: 978-94-009-7801-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation