Exercice 8 / 8Difficile
Chemin critique et marges
À toi
Une entreprise remplace son serveur de messagerie. Les dates de début au plus tôt t et au plus tard T sont déjà calculées (en jours) ; le projet dure 16 jours.
| Tâche | Description | Durée | Antérieures | t | T |
|---|---|---|---|---|---|
| A | Audit de l'existant | 2 | — | 0 | 0 |
| B | Commande des licences | 5 | A | 2 | 4 |
| C | Installation du serveur | 3 | A | 2 | 2 |
| D | Configuration | 4 | C | 5 | 5 |
| E | Migration des boîtes | 6 | B, D | 9 | 9 |
| F | Rédaction des guides | 3 | C | 5 | 10 |
| G | Formation | 2 | F | 8 | 13 |
| H | Bascule | 1 | E, G | 15 | 15 |
- Quel est le chemin critique ?
- Calcule la marge totale et la marge libre de F, la marge libre de G et la marge certaine de B.
- Si la configuration (D) prend 3 jours de retard, combien de jours dure le projet ?
Graphes et ordonnancement
Vocabulaire d'un graphe orienté
Un graphe orienté a des sommets et des arcs (x, y), de x vers y. Γ⁺(x) est l'ensemble des successeurs de x, Γ⁻(x) celui de ses prédécesseurs. Le nombre de successeurs s'appelle aussi le demi-degré extérieur, le nombre de prédécesseurs le demi-degré intérieur. Une source n'a aucun prédécesseur, un puits aucun successeur. La somme des nombres de successeurs est égale au nombre d'arcs.
Matrice d'adjacence et chemins
Ligne = origine, colonne = extrémité. La ligne de x donne ses successeurs, sa colonne ses prédécesseurs, et chaque 1 est un arc.
Le coefficient (i, j) de Mᵖ est le nombre de chemins de longueur p de i vers j. Dans la puissance booléenne M^[p], il vaut 1 s'il en existe au moins un.
Astuce de calcul : la ligne i de M² est la somme des lignes de M des successeurs de i. Avec les arcs A → B, A → C, B → C et C → A :
A B C A B C
M = [ 0 1 1 ] A M² = [ 1 0 1 ] A : ligne B + ligne C de M
[ 0 0 1 ] B [ 1 0 0 ] B : ligne C de M
[ 1 0 0 ] C [ 0 1 1 ] C : ligne A de M
Le 1 en (A, A) de M² est le circuit A → C → A, de longueur 2.
La fermeture transitive : Roy-Warshall
La fermeture transitive ajoute un arc x → y chaque fois qu'il existe un chemin de x vers y. Sa matrice M̂ se calcule ainsi : pour chaque sommet k, dans l'ordre, chaque ligne qui a un 1 dans la colonne k reçoit la somme booléenne de la ligne k, en utilisant la matrice telle qu'elle est à ce moment-là. Pour les arcs A → B et B → C : à l'étape k = B, la ligne A (qui a un 1 en colonne B) devient (0 1 0) ⊕ (0 0 1) = (0 1 1). On ajoute l'arc (A, C).
Les arcs à ajouter sont les 1 de M̂ qui étaient des 0 dans M. Un 1 sur la diagonale de M̂ signale un sommet qui appartient à un circuit.
Les niveaux d'un graphe sans circuit
Niveau 0 : les sommets sans prédécesseur. On les raye ; les sommets dont tous les prédécesseurs sont rayés forment le niveau 1, et ainsi de suite. Le niveau d'un sommet vaut un de plus que le plus grand niveau de ses prédécesseurs.
Le plus court chemin : Dijkstra
Chaque sommet porte une marque : la meilleure valeur connue depuis le départ, et le sommet d'où l'on vient. Au départ, 0 pour le sommet de départ, ∞ pour les autres. Puis on répète :
- on fixe le sommet non fixé de plus petite marque ;
- pour chacun de ses successeurs y non fixé, si marque(x) + v(x, y) est strictement plus petit que la marque de y, on la remplace et on note « vient de x ».
Avec A → B (5), A → C (2) et C → B (1) : on fixe A, B reçoit 5 (A) et C 2 (A) ; on fixe C, B passe à 2 + 1 = 3 (C) ; on fixe B. Le meilleur chemin vers B est A, C, B, de valeur 3. On le reconstruit en remontant les « vient de » depuis l'arrivée.
L'ordonnancement par la méthode MPM
Chaque tâche est un sommet ; on ajoute Début et Fin. d(x) est la durée de x.
- Date au plus tôt, de gauche à droite : t(Début) = 0 et t(x) = max [ t(p) + d(p) ] sur les tâches antérieures p. t(Fin) est la durée minimale du projet.
- Date au plus tard, de droite à gauche : T(Fin) = t(Fin) et T(x) = min [ T(s) ] − d(x) sur les tâches suivantes s.
- Une tâche est critique si t(x) = T(x). Le chemin critique va de Début à Fin par des tâches critiques : c'est le chemin le plus long.
- Marge totale MT(x) = T(x) − t(x) : retard possible sans retarder la fin du projet.
- Marge libre ML(x) = min [ t(s) ] − t(x) − d(x) : retard possible sans décaler aucune tâche suivante. Pour une tâche reliée à Fin, on prend t(Fin).
- Marge certaine MC(x) = min [ t(s) ] − max [ T(p) + d(p) ] − d(x), ou 0 si c'est négatif. Sans tâche antérieure, le max est remplacé par 0.
Exemple : A (3 jours), B (2 jours, après A), C (4 jours, après A), D (1 jour, après B et C). t(A) = 0, t(B) = t(C) = 3, t(D) = max [ 3 + 2 ; 3 + 4 ] = 7, t(Fin) = 8. T(D) = 7, T(B) = 7 − 2 = 5, T(C) = 7 − 4 = 3, T(A) = min [ 5 ; 3 ] − 3 = 0. Chemin critique : A, C, D. MT(B) = 5 − 3 = 2 et ML(B) = 7 − 3 − 2 = 2.
Tu es bloqué ?
Ouvre les indices un par un, le corrigé en dernier.
Indice 1
Une tâche est critique quand t = T. Le chemin critique relie Début à Fin par des tâches critiques, en suivant de vrais arcs.
Indice 2
MT(x) = T(x) − t(x) ; ML(x) = min [ t(s) ] − t(x) − d(x), sur les tâches suivantes s.
Indice 3
MC(x) = min [ t(s) ] − max [ T(p) + d(p) ] − d(x). Pour B, la seule antérieure est A et la seule suivante est E.
Voir le corrigé
Connecte-toi pour voir le corrigé
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données
Pour revoir la notion : chapitre 3 du cours Graphes et MPM, Puissances de la matrice d'adjacence et chemins de longueur p.
Tes réponses
Connecte-toi pour faire cet exercice
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données