Berechnung der neuen Releasezeiten

Im Beispiel liegt folgende Abhängigkeitsstruktur vor: $\tau_{4} \longrightarrow \{\tau_{1}, \tau_{3}\} \longrightarrow \tau_{2}$. Ausgehend von dem Task $\tau_{4}$, der von keinem anderen Task abhängig ist, werden jetzt die einzelnen Werte mittels der Formel 6.1 berechnet.

$$r^{*}_{j} = max(r_{j}, max(r_{i} + C_{i}: \tau_{i} \longrightarrow \tau_{j}))$$ (6.1)

Das bedeutet, wenn der Task $\tau_{j}$ -in dem Beispiel der Task $\tau_{4}$- auf der Zeitachse einen größeren Wert hat als alle Tasks $\tau_{i}$, die ihm in einer Abhängigkeit vorausgehen, dann muß sein Wert nicht geändert werden. Falls die anderen Tasks mit ihren Release- und Ausführungszeiten aber auf der Zeitachse weiter rechts liegen, dann muß der Wert von Task $\tau_{j}$ entsprechend angepasst werden. Er darf auf keinen Fall seine Ausführung beginnen, bevor nicht die anderen in der Abhängigkeit vorausgehenden Tasks mit ihren Ausführungen fertig sind. Entsprechend gilt dies für die Tasks, die im Abhängigkeitsgraph folgen (vgl. Formel 6.2):

$$r^{*}_{4} = max(r_{4}, \{\}) = max(3, \{\}) =3$$ (6.2)

$$r^{*}_{3} = max(r_{3}, max(r^{*}_{4}+C_{4})) = max(2, 3+1) = 4$$ (6.3)

$$r^{*}_{1} = max(r_{1}, max(r^{*}_{4}+C_{4})) = max(2, 3+1) = 4$$ (6.4)

$$r^{*}_{2} = max(r_{2}, max(r^{*}_{3}+C_{3};r^{*}_{1}+C_{1} ))$$ (6.5)

$$= max(2, max(4+2; 4+2)) = 6$$ (6.6)

Für den genauen Algorithmus siehe [14]:p.188):