Branch and Bound : Optimisation de l'Ordonnancement par Exploration et Élagage
Définition PMBOK v8
Le Branch and Bound (séparation et évaluation) est une technique d'ordonnancement qui consiste à décomposer un problème en sous-problèmes plus petits et à utiliser des fonctions d'évaluation pour éliminer tout sous-problème ne contenant pas la solution optimale. Cette technique explore et élimine systématiquement les ordonnancements potentiels afin de trouver une séquence de tâches optimale qui minimise la durée totale du projet tout en respectant toutes les contraintes.
Catégorie : Technique d'ordonnancement (Scheduling Technique) – Domaine de Performance : Planification (Planning Performance Domain)
Pourquoi c'est important pour l'examen
Cette technique est fréquemment testée à l'examen PMI dans les questions portant sur l'optimisation de l'ordonnancement sous contraintes. Les questions évaluent votre capacité à reconnaître quand utiliser le Branch and Bound par rapport à d'autres techniques comme le chemin critique (CPM) ou la chaîne critique (CCM). L'examen teste également la compréhension de son application dans des contextes où la recherche exhaustive est impossible.
Points clés à retenir (pour l'examen)
- Principe fondamental : Décomposition en sous-problèmes + élimination des branches non optimales via des fonctions d'évaluation (bounding functions)
- Objectif principal : Trouver la séquence de tâches qui minimise la durée totale du projet
- Condition d'application : Projets complexes avec de nombreuses contraintes où l'exploration exhaustive est irréaliste
- Différence clé avec CPM : Le Branch and Bound explore plusieurs chemins potentiels et élimine ceux qui ne peuvent pas mener à la solution optimale, contrairement au CPM qui calcule un seul chemin critique
- Relation avec l'approche adaptative : Utilisable dans les environnements où les détails du projet évoluent et où l'ordonnancement détaillé n'est pas possible initialement
- Contrainte majeure : Nécessite des fonctions d'évaluation précises pour être efficace
- Output attendu : Un ordonnancement optimal validé par élimination des solutions sous-optimales
Exemple type examen PMI
Un projet de construction comporte 15 tâches avec des dépendances complexes et des contraintes de ressources. Le chef de projet doit trouver l'ordonnancement qui minimise la durée totale. L'exploration manuelle de toutes les combinaisons possibles prendrait des semaines. Quelle technique d'ordonnancement utiliser ?
Réponse : Branch and Bound, car elle permet d'explorer systématiquement les solutions potentielles tout en éliminant rapidement les branches qui ne peuvent pas produire la solution optimale.
Pièges à l'examen PMI
-
Piège : Confondre Branch and Bound avec la méthode du chemin critique (CPM) Réalité : Le CPM calcule le chemin le plus long ; le Branch and Bound explore et élimine des solutions potentielles pour trouver l'optimale
-
Piège : Croire que Branch and Bound garantit toujours la solution optimale Réalité : Elle trouve l'optimale seulement si les fonctions d'évaluation sont correctement conçues
-
Piège : Penser que cette technique est réservée aux approches prédictives Réalité : Elle peut être utilisée dans les approches adaptatives où l'ordonnancement se fait progressivement
-
Piège : Confondre avec l'ordonnancement par flux (flow-based scheduling) Réalité : Le flow-based scheduling optimise le flux de livrables ; le Branch and Bound optimise la séquence des tâches
Connexions PMI importantes
| Concept lié | Type de relation | Point d'attention examen |
|---|---|---|
| Chemin critique (CPM) | Alternative / Complément | Le CPM identifie le chemin le plus long ; le Branch and Bound explore plusieurs chemins pour trouver l'optimal |
| Ordonnancement par flux (Flow-based) | Approche différente | Le flow-based maximise le flux de livrables ; le Branch and Bound minimise la durée sous contraintes |
| Décomposition progressive | Contexte d'application | Le Branch and Bound est utile quand les détails évoluent et qu'une planification initiale complète est impossible |
| Contraintes de ressources | Input essentiel | Les contraintes sont utilisées dans les fonctions d'évaluation pour éliminer les branches |
Questions de révision rapide
- Dans quel contexte de projet le Branch and Bound est-il particulièrement adapté par rapport au CPM ?
- Quelle est la conséquence si les fonctions d'évaluation (bounding functions) sont mal conçues ?
- Comment le Branch and Bound se distingue-t-il de l'ordonnancement par flux ?
- Pourquoi cette technique est-elle utile même dans les approches adaptatives où les détails évoluent ?
- Quel est le résultat attendu après application complète du Branch and Bound ?
Référence PMBOK v8
Section 2 – Project Management Performance Domains (Domaine de Performance Planification) Terme : Branch and Bound (définition dans le glossaire des techniques d'ordonnancement)
Astuce mémoire : "Branch = Explorer, Bound = Éliminer" – La technique sépare les branches, puis les élimine si elles ne peuvent pas contenir la solution optimale.