Ordonnancez un projet avec la méthode potentiels-tâches

Votre équipe doit mettre en production un modèle de scoring : collecter les données, les nettoyer, interroger les métiers, construire les variables, entraîner, préparer l’infrastructure, tester, déployer. Le directeur veut une date de livraison, et il veut savoir quelles tâches ne peuvent surtout pas prendre de retard. Où est la marge, et où n’y en a-t-il aucune ?

La méthode potentiels-tâches (ou méthode MPM) répond à ces questions avec un graphe et un calcul de plus longs chemins. C’est l’application la plus directe de tout ce que vous avez vu sur les chemins optimaux, et un grand classique des examens.

Le fil rouge : mettre un modèle en production

Le projet comporte sept tâches, avec leur durée en jours et leurs contraintes :

Tâche	Description	Durée	Contraintes
A	collecte des données	4	aucune
B	nettoyage	3	commence au plus tôt à la fin de A
C	entretiens avec les métiers	2	commence au plus tôt 1 jour après le début du projet
D	construction des variables	5	commence au plus tôt à la fin de B et à la fin de C
E	entraînement du modèle	3	commence au plus tôt à la fin de D
F	préparation de l’infrastructure	6	commence au plus tôt à la fin de C ; commence au plus tard 3 jours après le début de B
G	tests et déploiement	2	commence au plus tôt à la fin de E et à la fin de F

La contrainte « au plus tard » sur F traduit une exigence réelle : l’équipe infrastructure veut connaître l’architecture cible peu après le début du nettoyage, sans quoi elle réaffecte ses ingénieurs.

Des contraintes aux inégalités de potentiels

Une date par tâche

On associe à chaque tâche $i$ une inconnue $t_i$, sa date de début (on dit son potentiel). On ajoute deux tâches fictives de durée nulle : $\alpha$, le début du projet ($t_\alpha = 0$), et $\omega$, sa fin. Toute contrainte s’écrit alors comme une inégalité entre deux dates.

Contrainte en français	Inégalité	Arc du graphe
$j$ commence au plus tôt à la fin de $i$	$t_j - t_i \geq d_i$	$i \to j$, valeur $d_i$
$j$ commence au plus tôt $a$ jours après le début de $i$	$t_j - t_i \geq a$	$i \to j$, valeur $a$
$j$ commence au plus tard $b$ jours après le début de $i$	$t_j - t_i \leq b$, soit $t_i - t_j \geq -b$	$j \to i$, valeur $-b$

Toutes les inégalités ont la forme $t_j - t_i \geq v(i, j)$, et chacune devient un arc $(i, j)$ de valeur $v(i, j)$. Le graphe obtenu est le graphe potentiels-tâches.

Piège

La contrainte « au plus tard » donne un arc dans l’autre sens, avec une valeur négative. « F commence au plus tard 3 jours après le début de B » s’écrit $t_F \leq t_B + 3$, soit $t_B - t_F \geq -3$ : c’est un arc F → B de valeur $-3$, et non un arc B → F. C’est l’erreur la plus fréquente en examen.

Les contraintes implicites

Il faut encore dire que tout se passe entre $\alpha$ et $\omega$ : chaque tâche commence après $\alpha$ (arc $\alpha \to i$ de valeur 0) et se termine avant $\omega$ (arc $i \to \omega$ de valeur $d_i$). On ne garde que celles qui ne sont pas redondantes : si une tâche a déjà une contrainte de précédence, l’arc depuis $\alpha$ n’apporte rien.

Exemple

Pour notre projet :

• Contraintes explicites : $t_B - t_A \geq 4$, $t_C - t_\alpha \geq 1$, $t_D - t_B \geq 3$, $t_D - t_C \geq 2$, $t_E - t_D \geq 5$, $t_F - t_C \geq 2$, $t_B - t_F \geq -3$, $t_G - t_E \geq 3$, $t_G - t_F \geq 6$.
• Contraintes implicites non redondantes : $t_A - t_\alpha \geq 0$ (A n’a aucune autre contrainte) et $t_\omega - t_G \geq 2$ (G est la seule tâche sans successeur). Pour C, l’arc $\alpha \to C$ de valeur 1 existe déjà et domine l’arc implicite de valeur 0.

Existe-t-il un ordonnancement ?

Un ordonnancement est compatible s’il respecte toutes les inégalités. Or, le long d’un circuit $i_1 \to i_2 \to \dots \to i_1$, les inégalités s’additionnent : on obtient $0 \geq$ (valeur du circuit). D’où le critère :

À retenir

Il existe un ordonnancement compatible si et seulement si le graphe potentiels-tâches ne contient aucun circuit de valeur strictement positive. Un tel circuit exigerait qu’une tâche commence strictement après elle-même.

Ici, le seul arc « à rebours » est F → B, et depuis B on ne revient jamais à F (B mène à D, E, G, puis $\omega$) : il n’y a aucun circuit, l’ordonnancement existe.

Dates au plus tôt et chemin critique

Des plus longs chemins

La date de début au plus tôt de chaque tâche est la plus petite valeur de $t_i$ qui respecte toutes les contraintes. Chaque arc $(i, j)$ impose $t_j \geq t_i + v(i, j)$ : il faut donc prendre, pour chaque tâche, le maximum sur ses prédécesseurs, ce qui revient à calculer un plus long chemin de $\alpha$ à chaque tâche :

$$t_j = \max_{i \in \Gamma^{-1}(j)} \big(t_i + v(i, j)\big), \qquad t_\alpha = 0$$

On utilise l’algorithme de Bellman du chapitre 7 avec max au lieu de min ; si le graphe est sans circuit, un passage dans l’ordre topologique suffit.

Attention

En ordonnancement, on cherche des plus longs chemins, pas des plus courts : une tâche doit attendre toutes ses contraintes, donc la plus exigeante. C’est pour cela que le critère d’existence porte sur les circuits positifs, alors qu’en plus courts chemins ce sont les circuits négatifs qui posent problème.

Exemple

En traitant les tâches dans l’ordre $\alpha$, A, C, F, B, D, E, G, $\omega$ :

• $t_A = 0$ et $t_C = 1$ ;
• $t_F = t_C + 2 = 3$ ;
• $t_B = \max(t_A + 4,\; t_F - 3) = \max(4, 0) = 4$ ;
• $t_D = \max(t_B + 3,\; t_C + 2) = \max(7, 3) = 7$ ;
• $t_E = 7 + 5 = 12$ ;
• $t_G = \max(t_E + 3,\; t_F + 6) = \max(15, 9) = 15$ ;
• $t_\omega = 15 + 2 = 17$.

La durée minimale du projet est $T = t_\omega = 17$ jours.

L’arborescence des chemins optimaux garde, pour chaque tâche, l’arc qui a donné le maximum : $\alpha \to A$, $\alpha \to C$, $C \to F$, $A \to B$, $B \to D$, $D \to E$, $E \to G$, $G \to \omega$.

Le chemin critique

Un chemin critique est un chemin de valeur maximale de $\alpha$ à $\omega$ : sa valeur est exactement la durée minimale $T$. Ici, c’est $\alpha \to A \to B \to D \to E \to G \to \omega$, de valeur $0 + 4 + 3 + 5 + 3 + 2 = 17$. Les tâches qui s’y trouvent sont les tâches critiques : A, B, D, E, G. Tout retard sur l’une d’elles retarde le projet entier.

Le chemin critique (en rose) est un plus long chemin de α à ω, de valeur 17. Ses tâches ont la même date au plus tôt et au plus tard.

Dates au plus tard et marges

Au plus tard

Pour une durée de projet fixée à $T$, la date au plus tard $T_i$ d’une tâche est la date de début la plus tardive qui ne retarde pas la fin. Elle se calcule à rebours depuis $\omega$ ($T_\omega = T$) :

$$T_i = \min_{j \in \Gamma(i)} \big(T_j - v(i, j)\big)$$

Autrement dit, $T_i = T - \ell(i, \omega)$, où $\ell(i, \omega)$ est la valeur du plus long chemin de $i$ à $\omega$.

Exemple

À rebours depuis $T_\omega = 17$ : $T_G = 15$, $T_E = 12$, $T_D = 7$, $T_B = T_D - 3 = 4$, $T_A = T_B - 4 = 0$.

Pour F, deux successeurs : G (arc de valeur 6) et B (arc de valeur $-3$). Donc $T_F = \min(T_G - 6,\; T_B + 3) = \min(9, 7) = 7$. La contrainte « au plus tard » limite F plus que la fin du projet ! Enfin, $T_C = \min(T_D - 2,\; T_F - 2) = \min(5, 5) = 5$.

Marge totale et marge libre

Deux marges mesurent la souplesse d’une tâche :

• la marge totale $MT_i = T_i - t_i$ : le retard que peut prendre la tâche sans retarder la fin du projet ;
• la marge libre $ML_i = \min_{j \in \Gamma(i)} \big(t_j - t_i - v(i, j)\big)$ : le retard qu’elle peut prendre sans décaler la date au plus tôt d’aucune autre tâche.

On a toujours $0 \leq ML_i \leq MT_i$, et les tâches critiques sont exactement celles de marge totale nulle.

Tâche	A	B	C	D	E	F	G
Au plus tôt $t_i$	0	4	1	7	12	3	15
Au plus tard $T_i$	0	4	5	7	12	7	15
Marge totale	0	0	4	0	0	4	0
Marge libre	0	0	0	0	0	4	0

Les tâches critiques s'enchaînent sans temps mort jusqu'au jour 17 ; C et F peuvent glisser de 4 jours chacune sans retarder la fin.

Regardez C : sa marge totale vaut 4, mais sa marge libre est nulle. Pourquoi ? Pour la marge libre, on examine chaque successeur : $t_D - t_C - 2 = 7 - 1 - 2 = 4$, mais $t_F - t_C - 2 = 3 - 1 - 2 = 0$. Le moindre retard de C décale donc F (qui commence au plus tôt à la fin de C), même si le projet, lui, n’est pas retardé tant que ce retard ne dépasse pas 4 jours. Pour F, la marge libre vaut $\min(t_G - t_F - 6,\; t_B - t_F + 3) = \min(6, 4) = 4$.

La marge libre de C est nulle : le moindre retard décale F. La fin du projet, elle, ne bouge pas tant que le retard reste sous la marge totale de 4 jours.

def potentiels(taches, arcs):
    """arcs : liste de (i, j, valeur), avec les tâches fictives 'alpha' et 'omega'.
    Plus longs chemins par Bellman (max au lieu de min)."""
    sommets = ["alpha", *taches, "omega"]
    t = {x: float("-inf") for x in sommets}
    t["alpha"] = 0
    for _ in range(len(sommets)):
        change = False
        for i, j, v in arcs:
            if t[i] + v > t[j]:
                t[j], change = t[i] + v, True
        if not change:
            break
    else:
        raise ValueError("circuit de valeur positive : aucun ordonnancement")
    T = {x: float("inf") for x in sommets}
    T["omega"] = t["omega"]
    for _ in range(len(sommets)):               # au plus tard, à rebours
        for i, j, v in arcs:
            T[i] = min(T[i], T[j] - v)
    marge_libre = {i: min(t[j] - t[i] - v for a, j, v in arcs if a == i) for i in taches}
    return t, T, marge_libre

arcs = [("alpha", "A", 0), ("alpha", "C", 1), ("A", "B", 4), ("B", "D", 3), ("C", "D", 2),
        ("C", "F", 2), ("F", "B", -3), ("D", "E", 5), ("E", "G", 3), ("F", "G", 6), ("G", "omega", 2)]
t, T, ML = potentiels("ABCDEFG", arcs)
print(t["omega"], {x: T[x] - t[x] for x in "ABCDEFG"}, ML)   # 17, marges totales, marges libres

En entretien

« Le chemin critique d’un projet est le plus long chemin dans le graphe des contraintes : sa longueur est la durée minimale du projet, et ses tâches n’ont aucune marge. Pour raccourcir le projet, il faut accélérer une tâche critique ; accélérer une autre tâche ne sert à rien. »

La méthode potentiels-tâches est cousine de la méthode PERT, qui place les tâches sur les arcs plutôt que sur les sommets ; les logiciels de gestion de projet affichent le résultat sous forme de diagramme de Gantt, avec le chemin critique en rouge.

En résumé

• Chaque tâche $i$ a une date de début $t_i$ ; chaque contrainte s’écrit $t_j - t_i \geq v(i, j)$ et devient un arc $(i, j)$ de valeur $v(i, j)$. On ajoute $\alpha$ et $\omega$ et les contraintes implicites non redondantes.
• « Au plus tard $b$ jours après le début de $i$ » donne un arc de $j$ vers $i$, de valeur $-b$.
• Un ordonnancement existe si et seulement s’il n’y a aucun circuit de valeur strictement positive.
• Les dates au plus tôt sont des plus longs chemins depuis $\alpha$ ; la durée minimale est $T = t_\omega$ ; le chemin critique est un plus long chemin de $\alpha$ à $\omega$.
• Les dates au plus tard se calculent à rebours ; la marge totale $T_i - t_i$ protège la fin du projet, la marge libre protège les dates au plus tôt des autres tâches, et $0 \leq ML \leq MT$.

Exercices

Exercice · Traduire des contraintes

facile

Traduisez en inégalités de potentiels, puis en arcs, les contraintes suivantes (les durées sont $d_P = 4$ et $d_Q = 6$) :

1. Q commence au plus tôt à la fin de P.
2. Q commence au plus tôt 2 jours après le début de P.
3. Q commence au plus tard 5 jours après le début de P.
4. Q se termine au plus tard à la fin de P.

Voir la solution

1. $t_Q \geq t_P + 4$, soit $t_Q - t_P \geq 4$ : arc P → Q de valeur 4.
2. $t_Q - t_P \geq 2$ : arc P → Q de valeur 2.
3. $t_Q \leq t_P + 5$, soit $t_P - t_Q \geq -5$ : arc Q → P de valeur $-5$.
4. La fin de Q est $t_Q + 6$, celle de P est $t_P + 4$. On veut $t_Q + 6 \leq t_P + 4$, soit $t_P - t_Q \geq 2$ : arc Q → P de valeur 2. Attention : avec la contrainte 1, on obtiendrait le circuit P → Q → P de valeur $4 + 2 = 6 \gt 0$, donc aucun ordonnancement possible (Q ne peut pas à la fois commencer après la fin de P et finir avant).

En code

Python

def compatible(sommets, arcs):
    """Bellman avec max : False s'il existe un circuit de valeur strictement positive."""
    t = {x: 0 for x in sommets}
    for _ in range(len(sommets)):
        change = False
        for i, j, v in arcs:                   # arc (i, j, v) : t_j - t_i >= v
            if t[i] + v > t[j]:
                t[j], change = t[i] + v, True
        if not change:
            return True
    return False                               # ça bouge encore : circuit positif

c1 = ("P", "Q", 4)      # 1. Q au plus tôt à la fin de P
c2 = ("P", "Q", 2)      # 2. Q au plus tôt 2 jours après le début de P
c3 = ("Q", "P", -5)     # 3. Q au plus tard 5 jours après le début de P
c4 = ("Q", "P", 2)      # 4. Q finit au plus tard à la fin de P : t_P - t_Q >= 6 - 4
print(compatible("PQ", [c1, c2, c3]))   # True
print(compatible("PQ", [c1, c4]))       # False : circuit P -> Q -> P de valeur 4 + 2 = 6

R

compatible <- function(sommets, arcs) {
  # Bellman avec max : FALSE s'il existe un circuit de valeur strictement positive
  t <- setNames(rep(0, length(sommets)), sommets)
  for (passage in seq_along(sommets)) {
    change <- FALSE
    for (k in 1:nrow(arcs)) {                  # arc (i, j, v) : t_j - t_i >= v
      i <- arcs$i[k]; j <- arcs$j[k]
      if (t[i] + arcs$v[k] > t[j]) { t[j] <- t[i] + arcs$v[k]; change <- TRUE }
    }
    if (!change) return(TRUE)
  }
  FALSE                                        # ça bouge encore : circuit positif
}

contraintes <- data.frame(i = c("P", "P", "Q", "Q"), j = c("Q", "Q", "P", "P"),
                          v = c(4, 2, -5, 6 - 4))   # contraintes 1, 2, 3, 4
compatible(c("P", "Q"), contraintes[1:3, ])    # TRUE
compatible(c("P", "Q"), contraintes[c(1, 4), ])   # FALSE : circuit P -> Q -> P de valeur 6

Exercice · Raisonner sur les marges

moyen

Dans le projet du fil rouge, les entretiens avec les métiers (C) démarrent avec 3 jours de retard par rapport à leur date au plus tôt. Quelles sont les conséquences ? Même question avec un retard de 5 jours.

Voir la solution

Retard de 3 jours : C commence à $t_C = 4$. Comme sa marge libre est nulle, d’autres tâches sont décalées : F ne peut commencer qu’à $4 + 2 = 6$ au lieu de 3. Mais $3 \leq MT_C = 4$, donc la fin du projet n’est pas retardée. On vérifie : D commence à $\max(4 + 3, 4 + 2) = 7$ (inchangé), F à 6, ce qui respecte la contrainte « au plus tard » ($6 \leq t_B + 3 = 7$), et G à $\max(15, 6 + 6) = 15$. Durée : toujours 17 jours.

Retard de 5 jours : $5 \gt MT_C = 4$, donc le projet prend $5 - 4 = 1$ jour de retard. Détail : $t_C = 6$, donc $t_F = 8$ ; la contrainte F → B impose alors $t_B \geq 8 - 3 = 5$, et D commence à $\max(5 + 3, 6 + 2) = 8$, E à 13, G à 16, et la fin à 18 jours. Le retard se propage à la fois par D et, de façon plus sournoise, par la contrainte « au plus tard » qui repousse le nettoyage B.

En code

Python

def au_plus_tot(arcs):
    """Dates au plus tôt : plus longs chemins depuis alpha (Bellman avec max)."""
    sommets = {x for a in arcs for x in a[:2]}
    t = {x: float("-inf") for x in sommets}
    t["alpha"] = 0
    for _ in range(len(sommets)):
        for i, j, v in arcs:
            t[j] = max(t[j], t[i] + v)
    return t

def projet(retard_C):
    return [("alpha", "A", 0), ("alpha", "C", 1 + retard_C),   # C démarre retard_C jours plus tard
            ("A", "B", 4), ("B", "D", 3), ("C", "D", 2), ("C", "F", 2), ("F", "B", -3),
            ("D", "E", 5), ("E", "G", 3), ("F", "G", 6), ("G", "omega", 2)]

for retard in (0, 3, 5):
    t = au_plus_tot(projet(retard))
    print(retard, {x: t[x] for x in ["B", "C", "D", "F", "G", "omega"]})
# 0 {'B': 4, 'C': 1, 'D': 7, 'F': 3, 'G': 15, 'omega': 17}
# 3 {'B': 4, 'C': 4, 'D': 7, 'F': 6, 'G': 15, 'omega': 17}
# 5 {'B': 5, 'C': 6, 'D': 8, 'F': 8, 'G': 16, 'omega': 18}

R

au_plus_tot <- function(arcs) {
  # dates au plus tôt : plus longs chemins depuis alpha (Bellman avec max)
  sommets <- unique(c(arcs$i, arcs$j))
  t <- setNames(rep(-Inf, length(sommets)), sommets); t["alpha"] <- 0
  for (passage in seq_along(sommets))
    for (k in 1:nrow(arcs)) t[arcs$j[k]] <- max(t[arcs$j[k]], t[arcs$i[k]] + arcs$v[k])
  t
}

projet <- function(retard_C) data.frame(          # C démarre retard_C jours plus tard
  i = c("alpha", "alpha", "A", "B", "C", "C", "F", "D", "E", "F", "G"),
  j = c("A", "C", "B", "D", "D", "F", "B", "E", "G", "G", "omega"),
  v = c(0, 1 + retard_C, 4, 3, 2, 2, -3, 5, 3, 6, 2))

for (retard in c(0, 3, 5)) print(au_plus_tot(projet(retard))[c("B", "C", "D", "F", "G", "omega")])
# retard 0 : B 4, C 1, D 7, F 3, G 15, omega 17
# retard 3 : B 4, C 4, D 7, F 6, G 15, omega 17
# retard 5 : B 5, C 6, D 8, F 8, G 16, omega 18

Exercice · Une contrainte de trop

difficile

L’équipe infrastructure ajoute une exigence : F doit commencer au plus tôt 4 jours après la fin de B. Écrivez la nouvelle inégalité et montrez qu’il n’existe plus aucun ordonnancement compatible. Quelle est la plus grande valeur $a$ telle que « F commence au plus tôt $a$ jours après le début de B » reste réalisable ?

Voir la solution

« Au plus tôt 4 jours après la fin de B » s’écrit $t_F \geq t_B + 3 + 4$, soit $t_F - t_B \geq 7$ : arc B → F de valeur 7. Avec l’arc F → B de valeur $-3$, on obtient le circuit B → F → B de valeur $7 - 3 = 4 \gt 0$. En additionnant les deux inégalités : $t_F - t_B \geq 7$ et $t_B - t_F \geq -3$ donnent $0 \geq 4$, ce qui est absurde. Aucun ordonnancement n’est compatible : on demande à F de commencer au moins 7 jours après B, et au plus 3 jours après.

Avec une contrainte $t_F - t_B \geq a$, le circuit vaut $a - 3$. Il faut $a - 3 \leq 0$, donc $a \leq 3$. Pour $a = 3$, le circuit est de valeur nulle, ce qui est permis : F commence alors exactement 3 jours après B. Dans ce cas, les tâches B et F sont « verrouillées » l’une à l’autre.

En code

Python

def compatible(arcs):
    """Bellman avec max : False s'il existe un circuit de valeur strictement positive."""
    sommets = {x for a in arcs for x in a[:2]}
    t = {x: 0 for x in sommets}
    for _ in range(len(sommets)):
        change = False
        for i, j, v in arcs:
            if t[i] + v > t[j]:
                t[j], change = t[i] + v, True
        if not change:
            return True
    return False

projet = [("alpha", "A", 0), ("alpha", "C", 1), ("A", "B", 4), ("B", "D", 3), ("C", "D", 2),
          ("C", "F", 2), ("F", "B", -3), ("D", "E", 5), ("E", "G", 3), ("F", "G", 6),
          ("G", "omega", 2)]
print(compatible(projet + [("B", "F", 3 + 4)]))   # False : circuit B -> F -> B de valeur 7 - 3 = 4

# F au plus tôt a jours après le début de B : arc B -> F de valeur a
print([a for a in range(7) if compatible(projet + [("B", "F", a)])])   # [0, 1, 2, 3] : a <= 3

R

compatible <- function(arcs) {
  # Bellman avec max : FALSE s'il existe un circuit de valeur strictement positive
  sommets <- unique(c(arcs$i, arcs$j))
  t <- setNames(rep(0, length(sommets)), sommets)
  for (passage in seq_along(sommets)) {
    avant <- t
    for (k in 1:nrow(arcs)) t[arcs$j[k]] <- max(t[arcs$j[k]], t[arcs$i[k]] + arcs$v[k])
    if (all(t == avant)) return(TRUE)
  }
  FALSE
}

projet <- data.frame(i = c("alpha", "alpha", "A", "B", "C", "C", "F", "D", "E", "F", "G"),
                     j = c("A", "C", "B", "D", "D", "F", "B", "E", "G", "G", "omega"),
                     v = c(0, 1, 4, 3, 2, 2, -3, 5, 3, 6, 2))
compatible(rbind(projet, data.frame(i = "B", j = "F", v = 3 + 4)))   # FALSE : circuit de valeur 4

# F au plus tôt a jours après le début de B : arc B -> F de valeur a
Filter(function(a) compatible(rbind(projet, data.frame(i = "B", j = "F", v = a))), 0:6)   # 0 1 2 3