Optimal scheduling for two-processor systems. (English) Zbl 0248.68023

Coffman, E. G. jun.; Graham, R. L.

Acta Inf. 1, 200-213 (1971).

In Mehrprozessorsystemen spielt die Arbeitsreihenfolge der anstehenden Tasks eine fundamentale Rolle. Der Durchsatz dieser Systeme, bzw. die Zeit für die Fertigstellung einer gegebenen Taskmenge hängt entscheidend davon ab. Die Autoren behandeln Systeme mit zwei identischen Prozessoren. Alle Tasks haben konstante Abarbeitungszeit. Die Taskmenge ist halbgeordnet entsprechend ihren Abhängigkeitsbeziehungen. Unter Berücksichtigung der gegebenen Halbordnung wird eine Abarbeitungsreihenfolge gesucht, die kürzeste Gesamtheit ergibt. Die Taskmenge wird als zyklenfreier gerichteter Graph zugelassen. Damit gehen die Autoren über die bis dahin behandelten hierarchischen Anordnungen hinaus. Es wird ein Algorithmus für die Konstruktion einer optimalen Reihenfolge gegeben. Die Anzahl der Schritte ist von der Ordnung \(N^2\), wenn \(N\) die Anzahl der Tasks ist. Das Ergebnis verbessert auch die bisherigen Möglichkeiten für den hierarchischen Fall, in dem bisher Algorithmen der Ordnung \(N^4\) bekannt sind. Durch Zeitquantelung lassen sich Aufgaben behandeln, in denen die Abarbeitungszeit der einzelnen Tasks unterschiedlich ist. Mit einigen Einschränkungen lassen sich die Resultate auf Systeme mit mehr als zwei Prozessoren ausdehnen.

Reviewer: Christoph Polze (Berlin)

MSC:

68M20	Performance evaluation, queueing, and scheduling in the context of computer systems
68Q25	Analysis of algorithms and problem complexity

References:

[1]	Fulkerson, D. R.: Scheduling in project networks. Proc. IBM Scientific Computing Symposium on Combinatorial Problems. New York: IBM Corporation 1966. · Zbl 0168.40706
[2]	Clark, W.: The Gantt chart (3rd Edition). London: Pitman and Sons 1952.
[3]	Hu, T. C.: Parallel sequencing and assembly line problems. Operations Research 9, No. 6 (Nov. 1961).
[4]	Muntz, R. R., Coffman, E. G., Jr.: Optimal preemptive scheduling on twoprocessor systems. IEEE Trans. on Computers C 18, No. 11, 1014-1020, Nov. 1969. · Zbl 0184.20504 · doi:10.1109/T-C.1969.222573
[5]	- Scheduling of computations on multiprocessor systems: The preemptive assignment discipline. PhD. Thesis, Electrical Eng. Dept., Princeton University, April 1969.
[6]	Graham, R. L.: Bounds for certain multiprocessing anomalies. BSTJ, Nov. 1966, pp. 1563-1581. · Zbl 0168.40703
[7]	? Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, No.2, 416-429 (1969). · Zbl 0188.23101 · doi:10.1137/0117039
[8]	Fujii, M., Kasami, T., Ninomiya, K.: Optimal sequence of two equivalent processors. SIAM J. Appl. Math. 17, No. 3, 784-789 (1969). · Zbl 0205.48603 · doi:10.1137/0117070
[9]	? Erratum. SIAM J. Appl. Math. 20, No. 1, 141 (1971). · Zbl 0222.90045 · doi:10.1137/0120018
[10]	Edmonds, J.: Paths, trees and flowers. Canad. J. Math. 17, 449-467 (1965). · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4
[11]	Lawler, E. L. (personal communication).