Abstract
Givenm parallel processors each of them having the same speed but different intervals of availability, the problem of constructing a preemptive schedule forn independent tasks which completes each task in the given intervals is examined. We present an 0 (n+m logm) time algorithm to obtain such a schedule if there exists one. We show that the number of induced preemptions is proportional to the total number of processing intervals of all processors.
Zusammenfassung
Fürm identische Prozessoren, die nur in vorgegebenen Zeitintervallen zur Verfügung stehen, undn unabhängige Verrichtungen wird ein präemptiver Ablaufplan gesucht, so daß alle Verrichtungen innerhalb dieser Intervalle durchgeführt werden können. Es wird gezeigt, daß ein solcher Plan, falls er existiert, mit einem Aufwand von 0 (n + m logm) konstruiert werden kann und die Anzahl der dabei erzeugten Unterbrechungen proportional zur Anzahl der gegebenen Verfügbarkeitsintervalle aller Prozessoren ist.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Blum, M., R.W. Floyd, V.R. Pratt, R.L. Rivest, andR.E. Tarjan: Time bounds for selection. J. Comptr. Syst. Sci.7, 1972, 448–461.
Gonzalez, T., andS. Sahni: Preemptive scheduling of uniform processor systems. J. Assoc. Comput.25, 1978, 92–101.
McNaughton, R.: Scheduling with deadlines and loss functions. Management Science6, 1959, 1–12.
Sahni, S.: Preemptive scheduling with due dates. Operations Research5, 1979, 925–934.
Schmidt, G.: Preemptive scheduling on parallel processors with time dependent availabilities. Unpublished Manuscript, 1983.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Schmidt, G. Scheduling on semi-identical processors. Zeitschrift für Operations Research 28, 153–162 (1984). https://doi.org/10.1007/BF01920917
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01920917