Graphe des tâches : sommets et arcs orientés

Terminale Technologique · Mathématiques STMG Terminale

À retenir

• Un sommet du graphe des tâches est une opération, sa durée est écrite dans le sommet. • Un arc orienté A C signifie : C ne commence qu'après la fin de A. • Le jalon de durée nulle ferme le graphe ; sans sommet de fin, rien n'est comparable à la fin du projet. • Le graphe est acyclique : on peut donc le lire dans un ordre topologique, chaque sommet venant après tous ses prédécesseurs.

Le cours

1. Des opérations aux sommets et aux arcs Le graphe des tâches est la traduction graphique du tableau : chaque opération devient un sommet, chaque précédence un arc orienté. La flèche va de la tâche qui doit finir vers celle qui doit commencer, et la durée est écrite dans le sommet, non sur l'arc. • Un sommet est une tâche ; le losange de droite est le jalon Z, de durée nulle. • Un arc A C est la contrainte « C commence après la fin de A ». • Un chemin est une suite de tâches enchaînées du début à la fin du projet. • Le chemin critique est tracé en bleu, les arcs de marge en gris. • Un tel graphe est acyclique : il ne contient aucun cercle de flèches. A · 4 j C · 6 j D · 8 j E · 7 j F · 5 j G · 4 j H · 2 j B · 5 j I · 5 j Z · 0 j 2. Ordre topologique : dans quel ordre lire le graphe Le graphe se lit de gauche à droite : chaque sommet est placé dans une colonne de rang topologique, et l'on ne peut retenir un sommet que si tous ses précédents sont placés. Pour le déménagement, un ordre possible est A, B, C, D, I, E, F, G, H, Z. • Rangs : A et B au rang 0, C au rang 1, D et I au rang 2, E au rang 3. • Toute flèche va vers un rang strictement plus grand (B E passe du rang 0 au rang 3) : c'est la garantie de l'absence de cycle. • B peut être déplacé après C sans rien changer : l'ordre topologique n'est pas unique. • Cet ordre est le squelette de l'algorithme de balayage qui donne le chemin critique. 3. Pièges de construction du graphe • Inverser le sens d'une flèche : on obtiendrait un planning où la machine est posée avant la dépose des réseaux. • Oublier le jalon final : sans sommet de fin, rien n'est comparable à la fin du projet. • Ajouter une flèche entre deux tâches qui ne partagent qu'une ressource : le parallélisme disparaît. • Tracer deux arcs dans le même sens entre deux sommets : le second ne change rien.

Dans ce chapitre