Skip to main content
SpringerLink
Log in

A multifit algorithm for uniform multiprocessor scheduling

  • Contributed Papers
  • Conference paper
  • First Online:
Theoretical Computer Science

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 145))

Abstract

Independent tasks are nonpreemptively scheduled on m≧2 processors which are assumed to have different speeds. By generalizing ideas of bin packing techniques scheduling algorithms are constructed which have better worst case bounds than the well-known LPT algorithm.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. COFFMAN, E.G. jr. (ed.): Computer and job/shop scheduling theory, John Wiley and Sons, New York, 1976.

    Google Scholar 

  2. COFFMAN, E. G. jr., GAREY, M.R., JOHNSON, D.S.: An application of bin-packing to multiprocessor scheduling, SIAM J. Comp., 7 (1978), 1–17.

    Google Scholar 

  3. GONZALEZ, T., IBARRA, O.H., SAHNI, S.: Bounds for LPT schedules on uniform processors, SIAM J. Comput., 6 (1977), 155–166.

    Google Scholar 

  4. GRAHAM, R.L.: Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math., 17 (1969), 416–429.

    Google Scholar 

  5. LAWLER, E.L., LENSTRA, J.K., RINNOOYKAN, A.H.G.: Recent developments in deterministic sequencing and scheduling: a survey, in: M.A.H. DEMPSTER et al. (ed.): Deterministic and stochastic Scheduling, D. Reidel, Dordrecht, 1982, 35–73.

    Google Scholar 

  6. LIU, J.W.S. and LIU, C.L.: Bounds on scheduling algorithms for heterogeneous computer systems, Information Processing 74, North Holland, Amsterdam 1974, 349–353.

    Google Scholar 

  7. LIU, J.W.S., YANG, A.: Optimal scheduling of independent tasks on heterogeneous computing systems, ACM National Conference 1974, 38–45.

    Google Scholar 

  8. STEPPAT, H.: Bin-packing-Methoden für das Scheduling in uniformen Mehrprozessorsystemen, Diplomarbeit, Kiel 1982, to appear.

    Google Scholar 

  9. ULLMAN, J.D.: NP-complete scheduling problems, J. of Comp. and System Sciences, 10 (1975), 384–393.

    Google Scholar 

  10. ULLMAN, J.D.: Complexity of sequencing problems, in [1]

    Google Scholar 

  11. KUNDE, M.: Bounds for multifit scheduling algorithms on uniform multiprocessor systems, Bericht 8203, Institut für Informatik und Praktische Mathematik, Kiel 1982.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik und Praktische Mathematik, Universität Kiel, Olshausenstraße 40-60, D-2300, Kiel 1, W. Germany

    Manfred Kunde

Authors
  1. Manfred Kunde
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Armin B. Cremers Hans-Peter Kriegel

Rights and permissions

Reprints and permissions

Copyright information

© 1982 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kunde, M. (1982). A multifit algorithm for uniform multiprocessor scheduling. In: Cremers, A.B., Kriegel, HP. (eds) Theoretical Computer Science. Lecture Notes in Computer Science, vol 145. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0036479

Download citation

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

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-11973-9

  • Online ISBN: 978-3-540-39421-1

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation