Transformierung der Abhängigkeiten

Die Grundidee der Transformierung von abhängigen ('dependent') Tasks in nichtabhängige ('independent') Tasks wird an einem Beispiel erklärt.

Figure 6.1: TT vor der Anpassung

Figure 6.2: Abhängigkeitsgraph

Man ordnet die Menge $\Gamma_{spor}$, die Abhängigkeiten aufweist (vgl. Bild mit technischer Tabelle 6.1), mit Hilfe der Vorgängerrelation (Präzedenzrelation) $<$ in einem Graphen (vgl. Bild 6.2) so an, dass der Task ohne Abhängigkeiten eine Wurzel bildet, und dann an diesen die jeweiligen Nachfolger rekursiv angehängt werden. Dann berechnet man für alle Knoten des Abhängigkeitsgraphen die neuen Releasezeiten $\Phi_{i}^{*}$ (oder $r_{i}^{*}$) und die neuen Deadlines $D_{i}^{*}$.