THEORIE & SYMBOLISMES

 

L'objectif n'est pas de présenter la Théorie des Graphes mais d'introduire un vocabulaire à partir des concepts à l'origine des différentes représentations des plannings.

 

La théorie des graphes en soutien à la Recherche Opérationnelle

La théorie des graphes n'est que la partie de la théorie des ensembles qui concerne les relations binaires d'un ensemble avec lui-même à condition que l'ensemble soit dénombrable.

Dans un ensemble fini E (collection d'objets bien définis, différents les uns des autres et dénombrés), on peut considérer l'ensemble de tous les couples (collection ordonnée de deux éléments) qui peuvent être formés avec chacun de ses éléments. Cet ensemble de tous les couples est appelé ensemble produit. Si l'on considère que certains couples ont entre eux une relation représentant une propriété qui les lie et que les autres couples n'ont pas, on réalise la bi-partition de l'ensemble qu'on appelle un graphe.

Exemple : considérons l'ensemble E constitué de 4 éléments, S1 à S4.

E={ S1,S2,S3,S4 }

L'ensemble des couples de E est :

E x E = { (S1,S1), (S1,S2),(S1,S3),(S1,S4),(S2,S1),(S2,S2),(S2,S3),(S2,S4),(S3,S1),(S3,S2),(S3,S3),(S3,S4),(S4,S1),(S4,S2),(S4,S3),(S4,S4) }

On peut considérer un graphe G de E x E tel que :

G =  { (S1,S2),(S1,S3),(S2,S2),(S2,S3),(S3,S1),(S3,S4) }

Parmi les représentations graphiques possibles, on retiendra celle du diagramme de Venn (points et flèches).

 

Méthode PERT - Le diagramme de Venn

 

La figure ci-dessus représente l'ensemble E (composé de 4 éléments) et le graphe G des relations entre ses éléments où :

  • S1, S2, S3, S4 sont appelés sommets,
  • chaque flèche reliant un sommet origine (Si) à un sommet fin (Sj) est appelée arc,
  • un chemin est une suite d'arcs, telle que {(S1,S2), (S2,S3), (S3,S4)},
  • un circuit sera une suite d'arcs reliant un même sommet : { (S1,S2), (S2,S3), (S3,S1) }  ou  { (S1,S3), (S3,S1) }.
  • une boucle sera l'arc { (S2,S2) } marquant une relation de S2 avec lui-même. La boucle correspond à un circuit composé d'un seul arc.

 

 

Application à l'ordonnancement

Réaliser un planning c'est essentiellement ordonner entre elles un certain nombre de tâches concourant à l'exécution d'un ouvrage. Cet ouvrage, encore dénommé projet, réalisation, oeuvre, procédure, etc. peut être défini de deux manières différentes :

  • soit comme un ensemble de tâches liées entre elles par une relation d'antécédence,
  • soit comme un ensemble d'événements ou d'étapes liés entre eux par les tâches à accomplir pour les atteindre.

Nous avons dans les deux cas un ensemble fini (un ouvrage a un commencement et une fin) dont les éléments sont dénombrables (on peut recenser le nombre de tâches ou d'étapes, certains de ces éléments ayant entre eux une relation que d'autres n'ont pas (bi-partition). Dans les deux cas, on obtient donc un graphe.

Le diagramme de Venn utilisé pour présenter les relations entre étapes est appelé réseau. Ce réseau représente la logique du projet, logique totalement indépendante du temps.

 

 

La méthode PERT

Les inventeurs de la méthode PERT ont considéré que :

  • les arcs représentent les tâches,
  • les sommets représentent les étapes.

Les étapes sont des états particuliers du projet qu'il est possible de décrire avec précision.

Chaque tâche correspond à un traitement du projet qui a pour effet de le faire passer de l'état correspondant à l'étape début de la tâche à un état correspondant à l'étape fin de la tâche.

Planning PERT composé de 4 tâches en série.

Voici l'exemple d'un réseau PERT. Il est composé de 4 tâches. Dans ce cas simple de tâches en série, 5 étapes ont été nécessaires pour le définir.

La forme de ce graphe et sa longueur sur l'axe horizontal sont indépendantes du temps. C'est l'intérêt principal de ce type de graphe : que le projet démarre en début ou en fin d'année, qu'il prenne du retard ou pas, le graphe est toujours le même !

 

 

La méthode des potentiels

D'autres méthodes ont été développées à partir de l'autre convention possible : c'est ainsi que la méthode des potentiels représente un réseau dans lequel les tâches sont les sommets du graphe et les arcs les relations qu'elles ont entre elles.

 

Méthode PERT - Exemple de graphe en méthode des potentiels

Cet exemple correspond à la vue "Réseau de tâches" de l'outil de gestion de projet Microsoft Project.

Les tâches sont généralement représentées sous la forme d'un rectangle dans lequel sont insérées des informations (libellé, durée, dates, marges, ressources, coûts, etc.). Les arcs qui relient certaines tâches entre elles expriment ici la relation d'antécédence qui les ordonne deux à deux. Le réseau est alors l'ensemble de toutes les tâches ordonnées entre elles.

Concernant le temps, la forme et les dimensions de ce graphe sont également indépendantes de la durée des tâches et du projet. C'est l'immense avantage des plannings par réseau par rapport aux plannings de GANTT.

 

La plupart des outils de gestion de projet ont adopté cette méthode car elle permet la saisie des tâches sous la forme de "liste verticale", comme dans un tableur. Les tâches étant ensuite identifiées par un numéro d'ordre, il est aisé de spécifier la liste des prédécesseurs de chaque tâche.
L'avantage par rapport au PERT, c'est qu'il n'y a pas besoin de disposer d'une représentation graphique du réseau complet avant de pouvoir commencer la saisie des tâches. L'identifiant unique de chaque tâche est en effet fourni par l'outil durant la saisie alors qu'en PERT, l'identifiant de chaque tâche est constitué du couple (i,j) des identifiants de ses étapes début et fin. Il faut donc avoir numéroté toutes les étapes avant de pouvoir saisir les données des tâches et calculer des dates.
Forts de cet avantage, les outils de gestion de projet proposent des vues - "PERT", "Réseau CPM" ou autres - censées montrer les tâches avec leurs relations de dépendance. Mais la qualité de ces graphiques laisse à désirer et ne rivalisera jamais avec celle d'un graphe conçu et réalisé avec la méthode PERT.

Les méthodes ROY ou MPM (méthode des potentiels METRA) sont des variantes.

Quoi qu'il en soit, les deux méthodes, PERT et potentiels, ont exactement la même finalité et fournissent les mêmes résultats quant aux calculs des dates des plannings réalisés avec chacune d'elles.


La suite ne traite que du PERT.

 

 

Le symbolisme du PERT

Pour dessiner le réseau PERT, on utilise généralement les symboles suivants :

  • ETAPE : figure fermée (rond, ovale, rectangle) à laquelle est associée un code alphanumérique qui sert d'identifiant.
    L'étape représente le début ou la fin d'une tâche.
  • TACHE : représentée par un vecteur reliant l'étape début et l'étape fin
    Chaque tâche est identifiée par le couple des codes alphanumériques de ses étapes de début et de fin.
    On verra plus loin qu'une tâche possède de nombreuses autres propriétés (libellé, durée, responsable, calendrier, etc.)

 

Haut de page