Ich versuche das Thema mal aufzugreifen, da ich auch gerade damit beschäftigt bin.
Der obere Zweig wird gemäß erstellter Prioritäten gezeichnet. Von Suchschritt 0 zu 1 wird mit der Elementaroperation (EOP) 2 gemäß Prioritätenliste begonnen. Die Ausführungszeiten aller Nachfolger sind 45 (53 - 8). So wird dieser Ast bis zur EOP 12 durchgeführt. Jetzt prüft man, ob eine bessere Lösungsalternative vorhanden ist, indem die unteren Schranken berechnet werden. Bei Suchschritt 12 sieht die Berechnung so aus: (6 - 1) + 1/11 = 5,09 = <6>, bei Suchschritt 11 so: (6 - 1) + (10 + 1)/11 = 6 <6> und bei Suchschritt 10 so: (5 - 1) + (7 + 10 + 1)/11 = 5,64 <6>. Das kann man jetzt bis zum Suchschritt 0 durchführen.
Nun kommen mir jedoch folgende Fragen auf.
1) Warum wurde im oberen Baum die Priorität von EOP 10 und 8 vertauscht?
2) Warum wird der Suchschritt 1 mit k = 2 und nicht 1 gerechnet? k = 2 muss genommen werden, ansonsten kommt man nie über eine untere Schranke von <6>, obwohl die Ausführungszeit komplett auf Station 1 durchführbar ist.
3) Nach welchem Vorgehen wird der untere Ast berechnet? Suchschritt 13 und 14 sind offentsichtlich mit k = 1 gerechnet, ansonsten kommt man nicht auf eine untere Schranke unter <6> sondern eben <5>. Beide Suchschritte sind jedoch auch nach 11 ZE ausgeführt. Das bringt mich wieder zu Frage 2), denn EOP 2 ist auch nach 11 ZE, es sind 8 ZE Ausführungszeit, ausgeführt. Wenn k = 1 gerechnet wird, kommt man halt auf 4,82 und 4,27 für die unteren Schranken gemäß dem oben Beschriebenen vorgehen. Ausführungszeiten der Nachfolger sind jeweils 53 - 6 = 47 und 53 - (6 + 5) = 42.
