Apprentissage interactif de la théorie des graphes
Apprentissage interactif de la théorie des graphes
Guest User
Using app without sign in
Calculateur de chemin critique
Identifie la plus longue séquence de tâches dépendantes dans un calendrier de projet, déterminant le temps le plus court possible pour le terminer.
Sélectionnez un algorithme et générez les étapes pour commencer la visualisation
La méthode du chemin critique (CPM) trouve la plus longue chaîne d'activités dépendantes dans un réseau de projet, qui détermine la durée minimale du projet. Les activités sur ce chemin critique ont une marge nulle : tout retard sur elles retarde tout le projet.
Le projet est modélisé comme un graphe orienté acyclique d'activités avec durées. Une passe avant en ordre topologique calcule le début et la fin au plus tôt de chaque activité ; une passe arrière calcule les dates au plus tard qui évitent de retarder le projet. La différence entre début au plus tard et au plus tôt est la marge de l'activité, et les activités à marge nulle forment le chemin critique. Les deux passes s'exécutent en O(V + E).
La CPM planifie les chantiers de construction, les livraisons de logiciels, les changements de série en fabrication et l'organisation d'événements. Les outils de gestion de projet comme Primavera et Microsoft Project calculent les chemins critiques en continu. C'est aussi une application scolaire des plus longs chemins dans les DAG et du tri topologique.
Lire l'article complet: Operations Research and Graph Theory
Algorithmes associés: PERT (Technique d'Évaluation et de Revue de Programme), RCPSP (Ordonnancement de Projet sous Contraintes de Ressources), Tri Topologique