Interaktives Graphentheorie-Lernen
Interaktives Graphentheorie-Lernen
Guest User
Using app without sign in
Rechner für den kritischen Pfad
Identifiziert die längste Folge von abhängigen Aufgaben in einem Projektplan und bestimmt die kürzestmögliche Zeit zur Fertigstellung.
Wählen Sie einen Algorithmus und generieren Sie Schritte, um die Visualisierung zu beginnen
Die Methode des kritischen Pfades (CPM) findet die längste Kette abhängiger Vorgänge in einem Projektnetz, die die minimale Projektdauer bestimmt. Vorgänge auf diesem kritischen Pfad haben keinen Puffer: jede Verzögerung bei ihnen verzögert das ganze Projekt.
Das Projekt wird als gerichteter azyklischer Graph von Vorgängen mit Dauern modelliert. Ein Vorwärtsdurchlauf in topologischer Reihenfolge berechnet den frühesten Start und Abschluss jedes Vorgangs; ein Rückwärtsdurchlauf berechnet die spätesten Zeiten, die das Projekt nicht verzögern. Die Differenz zwischen spätestem und frühestem Start ist der Puffer des Vorgangs, und Vorgänge mit null Puffer bilden den kritischen Pfad. Beide Durchläufe laufen in O(V + E).
CPM plant Bauprojekte, Software-Releases, Rüstwechsel in der Fertigung und Veranstaltungsplanung. Projektmanagement-Werkzeuge wie Primavera und Microsoft Project berechnen kritische Pfade fortlaufend. Es ist auch eine Lehrbuchanwendung längster Pfade in DAGs und der topologischen Sortierung.
Den ganzen Artikel lesen: Operations Research and Graph Theory
Verwandte Algorithmen: PERT (Program Evaluation and Review Technique), RCPSP (Ressourcenbeschränkte Projektplanung), Topologische Sortierung