Optimal scheduling for two-processor systems (Q2556224)

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.