Exercice 7 / 8Moyen
Dates au plus tôt et au plus tard en MPM
À toi
Le laboratoire GSB refond son application de gestion des frais. Les durées sont en jours ouvrés.
| Tâche | Description | Durée | Tâches antérieures |
|---|---|---|---|
| A | Analyse des besoins | 4 | — |
| B | Maquettes de l'interface | 3 | A |
| C | Modélisation de la base | 5 | A |
| D | Développement de l'API | 6 | C |
| E | Développement de l'interface | 4 | B, C |
| F | Tests et recette | 3 | D, E |
| G | Formation des utilisateurs | 2 | B |
| H | Mise en production | 1 | F, G |
Calcule la date de début au plus tôt t et la date de début au plus tard T de chaque tâche, et de la Fin du 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
t(x) = max [ t(p) + d(p) ] sur les tâches antérieures p : on avance de gauche à droite, en prenant le maximum.
Indice 2
T(Fin) = t(Fin), puis T(x) = min [ T(s) ] − d(x) sur les tâches suivantes s : on recule, en prenant le minimum.
Indice 3
Pour E, deux antérieures : max [ t(B) + 3 ; t(C) + 5 ]. Pour T(B), deux suivantes : E et G.
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