Gegeben: G = (V,E) gerichtet G beschreibt Vorrang-Relation zwischen Tasks
Gesucht: Schedule für 2 Prozessoren
z.B.
bedeutet: i muß vor j bearbeitet werden.
Kante (x,y) in G' besagt, daß x und y gleichzeitig bearbeitet werden können.
Bilde G' = (V,E') ungerichtet wie folgt:
(x,y) E'x ist nicht Vorgänger von y und y ist nicht Vorgänger von x .
Falls folgende Situation
auftritt und zwischen i und j bzw. k und l keine Nachfolgebeziehungen bestehen, dann kann auch zwischen i und l bzw. k und j keine Nachfolgebeziehung bestehen, d.h., der Konflikt der auftritt, wenn i parallel zu j und k parallel zu l bearbeitet wird, kann dadurch beseitigt werden, indem man i parallel zu l und k parallel zu j bearbeitet.
D.h. ersetze
durch
.