Dates au plus tard et marges — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 7)

Dates au plus tard et marges

Graphes sans circuit et ordonnancement de projets · niveau 2

Énoncé

La date de fin au plus tard $T (i)$ de la tâche $i$ est la date la plus tardive à laquelle $i$ peut se terminer sans retarder la fin du projet. On note $t (i)$ sa date de début au plus tôt, $d (i)$ sa durée et $succ (i)$ l'ensemble de ses successeurs.

Justifier : $T (n - 1) = t (n - 1)$ et, pour $0 \leq i < n - 1$ , $T (i) = min_{j \in succ (i)} {T (j) - d (j)}$ .
Dans quel ordre calculer les $T (i)$ ? Écrire la fonction.
La marge de $i$ est $T (i) - d (i) - t (i)$ . Montrer que les tâches d'un chemin critique ont une marge nulle.
Calculer les marges des tâches du projet à 8 tâches du cours (durées $D = [0, 6, 3, 1, 7, 9, 8, 0]$ ).

Corrigé

La tâche $n - 1$ (fin du projet) doit finir à la durée minimum du projet, $t (n - 1)$ . Une tâche $i < n - 1$ doit être finie quand chacun de ses successeurs $j$ commence, au plus tard à $T (j) - d (j)$ ; la contrainte la plus forte est le minimum sur $j \in succ (i)$ .
$T (i)$ dépend des $T (j)$ pour $j > i$ (numérotation isotone) : on calcule par $i$ décroissants, en parcourant les successeurs, donc dans le graphe $G$ lui-même.


static int[] plusTard(Liste[] G, int[] D, int duree) { int n = D.length;
    int[] F = new int[n];
    F[n - 1] = duree;                                   // base : fin du projet
    for (int i = n - 2; i >= 0; i--) {                  // tous les succ(i) sont > i
        F[i] = Integer.MAX_VALUE;
        for (Liste l = G[i]; !vide(l); l = reste(l)) { int j = premier(l);
            F[i] = Math.min(F[i], F[j] - D[j]);         // j commence au plus tard à F[j]-d(j)
        }
    }
    return F;
}

Sur un chemin critique $0 \to \dots \to n - 1$ , chaque tâche commence exactement à la fin de la précédente et la dernière finit à $t (n - 1)$ : en remontant le chemin, on obtient $T (i) = t (i) + d (i)$ pour chacune, donc une marge nulle. Un retard sur l'une d'elles retarde le projet.
Exécution (avec $t$ calculé par le programme du cours) :


t      = [0, 0, 0, 6, 3, 6, 15, 23]
T      = [0, 6, 6, 23, 15, 15, 23, 23]
marges = [0, 0, 3, 16, 5, 0, 0, 0]


nom : marges
valeurs : 0 0 3 16 5 0 0 0
vert : 0 1 5 6 7
legende : en vert, marge nulle : les tâches du chemin critique

Les tâches $0$ , $1$ , $5$ , $6$ , $7$ du chemin critique ont une marge nulle ; la tâche $3$ peut glisser de $16$ jours sans retarder le projet.