Graphes, plus court chemin et ordonnancement de projets

Objectifs du chapitre — À la fin de ce chapitre, vous saurez :

• représenter un réseau par un graphe (sommets, arcs, valuations) ;
• calculer un plus court chemin par l'algorithme de Dijkstra ;
• construire un arbre couvrant de poids minimal par l'algorithme de Kruskal ;
• ordonnancer un projet par la méthode PERT : dates au plus tôt, au plus tard, marges ;
• identifier le chemin critique et raisonner sur la réduction de la durée d'un projet.

6.1 Les graphes

Définition — Graphe : ensemble de sommets (ou nœuds) reliés par des arêtes (liaisons non orientées) ou des arcs (liaisons orientées). Un graphe est valué quand chaque arc porte un nombre : distance, coût, durée, capacité.

Les graphes modélisent les réseaux routiers et ferroviaires, les réseaux logistiques (entrepôts et magasins), les réseaux électriques et de télécommunication, mais aussi les relations d'antériorité entre les tâches d'un projet. Vocabulaire utile :

• un chemin est une suite d'arcs consécutifs ; sa longueur est la somme des valuations ;
• un circuit est un chemin qui revient à son point de départ ;
• un graphe est connexe si l'on peut relier deux sommets quelconques ;
• un arbre est un graphe connexe sans cycle ; avec $n$ sommets, il compte exactement $n - 1$ arêtes.

6.2 Le plus court chemin : l'algorithme de Dijkstra (1959)

Il calcule le plus court chemin d'un sommet de départ vers tous les autres, quand toutes les valuations sont positives.

1. Donner l'étiquette 0 au sommet de départ et $+\infty$ aux autres.
2. Choisir le sommet non définitif de plus petite étiquette et le rendre définitif.
3. Pour chacun de ses voisins non définitifs, calculer « étiquette du sommet + longueur de l'arc » ; si c'est plus petit que l'étiquette du voisin, la remplacer et noter le prédécesseur.
4. Recommencer jusqu'à ce que tous les sommets soient définitifs. Le chemin se lit en remontant les prédécesseurs.

Exemple. Un livreur part d'un dépôt A. Les distances (en km) des tronçons sont : A-B 7, A-C 9, A-F 14, B-C 10, B-D 15, C-D 11, C-F 2, D-E 6, E-F 9.

Le plus court chemin de A à E mesure 20 km : A → C → F → E (9 + 2 + 9). On remarque que la liaison directe A-F (14 km) est moins intéressante que le détour par C (11 km). Les applications de navigation et les logiciels de tournées reposent sur des versions améliorées de cet algorithme.

6.3 L'arbre couvrant de poids minimal : l'algorithme de Kruskal (1956)

Problème : relier tous les sommets d'un réseau (raccorder des agences par fibre optique, des douars au réseau électrique) avec une longueur totale minimale, sans redondance.

1. Classer les arêtes par valuation croissante.
2. Les examiner dans cet ordre : retenir une arête si elle ne crée pas de cycle avec les arêtes déjà retenues.
3. S'arrêter quand on a retenu $n - 1$ arêtes.

L'algorithme est dit glouton : il fait à chaque étape le meilleur choix local, et l'on démontre que, pour ce problème, cela donne l'optimum global. Ce n'est pas le cas en général (chapitre 7).

6.4 L'ordonnancement de projets : la méthode PERT

Un projet (construction d'une usine, lancement d'un produit, organisation d'un événement) se décompose en tâches liées par des contraintes d'antériorité : une tâche ne peut commencer que lorsque ses prédécesseurs sont terminés. La méthode PERT (Program Evaluation and Review Technique, US Navy, 1958) et la méthode du chemin critique (CPM) permettent de calculer la durée minimale du projet et les tâches à surveiller.

Pour chaque tâche $i$ de durée $d_i$ :

• date de début au plus tôt $ES_i$ = maximum des dates de fin au plus tôt de ses prédécesseurs ; fin au plus tôt $EF_i = ES_i + d_i$ ;
• la durée minimale du projet est la plus grande date de fin au plus tôt ;
• date de fin au plus tard $LF_i$ = minimum des dates de début au plus tard de ses successeurs (pour la dernière tâche, la durée du projet) ; début au plus tard $LS_i = LF_i - d_i$.

Définition — Marge totale : $MT_i = LS_i - ES_i$, retard maximal que peut prendre une tâche sans retarder la fin du projet.

Définition — Marge libre : $ML_i$ = (plus petite date de début au plus tôt des successeurs) $- EF_i$, retard possible sans retarder le début au plus tôt d'aucune autre tâche.

Définition — Chemin critique : suite de tâches de marge totale nulle, qui relie le début et la fin du projet. Sa longueur est la durée minimale du projet ; tout retard sur une tâche critique retarde le projet d'autant.

On représente le projet par un graphe : dans la convention PERT, les tâches sont des arcs et les sommets des étapes (ce qui oblige parfois à ajouter des tâches fictives) ; dans la convention potentiel-tâches (MPM, Roy, 1958), les tâches sont des sommets, ce qui est plus simple. Le diagramme de Gantt présente ensuite le calendrier sous forme de barres.

6.5 Réduire la durée d'un projet

Pour raccourcir un projet, il faut agir sur le chemin critique : accélérer une tâche non critique ne sert à rien. On peut affecter plus de ressources à une tâche critique (heures supplémentaires, sous-traitance) en comparant le coût de l'accélération par jour gagné au gain (pénalités de retard évitées). Attention : en raccourcissant le chemin critique, un autre chemin peut devenir critique.

Dans le PERT probabiliste, chaque durée est estimée par trois valeurs (optimiste $a$, la plus probable $m$, pessimiste $b$) : durée moyenne $\dfrac{a + 4m + b}{6}$ et variance $\left(\dfrac{b - a}{6}\right)^2$. La durée du projet suit approximativement une loi normale dont la moyenne et la variance sont les sommes de celles des tâches critiques.

6.6 Méthode : ordonnancer un projet

1. Dresser le tableau des tâches : durée et prédécesseurs immédiats.
2. Calculer, dans l'ordre des tâches, les dates au plus tôt (passage avant).
3. Fixer la durée du projet et calculer les dates au plus tard en remontant (passage arrière).
4. Calculer les marges totales et libres.
5. Identifier le chemin critique (marges totales nulles) et vérifier que sa durée est celle du projet.
6. Tracer le diagramme de Gantt et commenter les tâches à surveiller.

Les pièges à éviter

• Prendre le minimum des fins des prédécesseurs pour la date au plus tôt (c'est le maximum : il faut attendre le dernier).
• Prendre le maximum des débuts des successeurs pour la date au plus tard (c'est le minimum).
• Confondre marge totale et marge libre.
• Appliquer Dijkstra à un graphe qui a des valuations négatives.
• Dans Kruskal, retenir une arête qui ferme un cycle.