Ordonnancement : la méthode MPM et le chemin critique

Ordonnancer un projet, c'est fixer les dates de ses tâches en respectant leurs contraintes d'antériorité (telle tâche ne peut commencer qu'une fois telle autre finie), de façon à terminer le projet au plus tôt. La méthode MPM (méthode des potentiels Métra) représente chaque tâche par un sommet d'un graphe valué, calcule pour chacune une date de début au plus tôt et une date de début au plus tard, et en déduit la durée minimale du projet et son chemin critique : la suite de tâches qui ne tolèrent aucun retard. Ce chapitre déroule la méthode en cinq étapes sur un projet informatique complet, comme le demandent les exercices d'ordonnancement de l'E3.

Ordonnancement, MPM et PERT

La méthode MPM a été mise au point en France par le mathématicien Bernard Roy en 1958. La même année, aux États-Unis, la marine américaine développait la méthode PERT pour planifier son programme de missiles Polaris. Les deux méthodes donnent les mêmes résultats ; elles diffèrent par la façon de dessiner le graphe : MPM met les tâches sur les sommets, PERT sur les arcs (chapitre 10). Le programme laisse le choix entre les deux ; ce cours détaille MPM, la plus simple à dessiner, et montre PERT ensuite.

Le graphe d'un projet est toujours sans circuit : une tâche ne peut pas attendre, même indirectement, sa propre fin. Toute la méthode repose sur ce fait et sur les deux outils des chapitres précédents : les niveaux (chapitre 5) et le chemin de valeur maximale (chapitre 6).

Le projet fil rouge et le tableau des tâches

Une PME remplace son vieux serveur de fichiers. Le technicien chargé du projet a listé les tâches, leur durée en jours ouvrés et, pour chacune, les tâches qui doivent être terminées avant qu'elle commence (ses tâches antérieures, ou prédécesseurs) :

Les tâches antérieures indiquées sont les antériorités immédiates : F attend D et E, donc aussi, indirectement, B, C et A, mais on ne les écrit pas.

Étape 1 : les niveaux des tâches

On détermine les niveaux du graphe des antériorités, avec la méthode du tableau des prédécesseurs. Ils serviront à placer les tâches en colonnes et à faire les calculs dans le bon ordre.

Niveaux : N₀ = {A}, N₁ = {B, C}, N₂ = {D, E, H}, N₃ = {F, G}, N₄ = {I}, N₅ = {J}.

Il est utile aussi de dresser le tableau des successeurs, qu'on lit en retournant les antériorités ; il servira pour les dates au plus tard :

Étape 2 : construire le graphe MPM

Les conventions du graphe MPM :

• chaque tâche est un sommet, représenté par un rectangle ;
• on ajoute deux sommets fictifs, Début et Fin, qui ne sont pas des tâches (durée nulle) ;
• un arc va de chaque tâche vers chacune de ses tâches suivantes ; il porte la durée de la tâche d'origine (le temps qu'il faut attendre, après le début de x, pour pouvoir commencer y) ;
• Début est relié aux tâches sans antériorité (arcs de valeur 0), et chaque tâche sans successeur est reliée à Fin (arc portant sa durée) ;
• les sommets sont placés en colonnes, niveau par niveau.

Dans chaque rectangle, on écrira deux nombres : la date de début au plus tôt t et la date de début au plus tard T de la tâche. Beaucoup de corrigés écrivent aussi la durée de la tâche dans son rectangle, à côté de son nom, plutôt que sur chacun des arcs qui en partent : c'est la même information, et le dessin reste lisible.

Étape 3 : les dates de début au plus tôt

La date de début au plus tôt t(x) d'une tâche est la date la plus proche à laquelle elle peut commencer, toutes ses tâches antérieures étant finies. Le projet commence à la date 0.

On prend le maximum parce qu'une tâche doit attendre que toutes ses tâches antérieures soient finies : c'est la plus tardive qui décide. C'est exactement la recherche du chemin de valeur maximale du chapitre 6.

Le projet dure au minimum 19 jours ouvrés.

Étape 4 : les dates de début au plus tard

La date de début au plus tard T(x) d'une tâche est la date la plus tardive à laquelle elle peut commencer sans retarder la fin du projet. On la calcule en partant de la fin.

On prend le minimum parce que la tâche x doit être finie avant le début au plus tard de chacune de ses tâches suivantes : c'est la plus exigeante qui décide.

On retrouve bien T(A) = 0, la date de début du projet.

Étape 5 : tâches critiques et chemin critique

Une tâche est critique quand sa date au plus tôt est égale à sa date au plus tard : t(x) = T(x). Elle n'a aucune marge : le moindre retard sur elle retarde la fin du projet.

Les tâches critiques sont A, C, E, G, I et J. Un chemin critique est un chemin de Début à Fin qui ne passe que par des tâches critiques : ici Début → A → C → E → G → I → J → Fin. Sa valeur est la somme des durées de ses tâches : 3 + 6 + 3 + 4 + 2 + 1 = 19, la durée minimale du projet. C'est le chemin de valeur maximale du graphe.

Interpréter les résultats

Les sujets demandent presque toujours d'interpréter, avec les mots du contexte :

• « La durée minimale de réalisation du projet est de 19 jours. »
• « Les tâches critiques sont le recueil des besoins, la commande du serveur, son installation, la migration des données, les tests et la mise en production : un retard sur l'une d'elles retarde d'autant la mise en production. »
• « La rédaction du cahier des charges (B) peut commencer au plus tôt le jour 3 et au plus tard le jour 10 sans retarder le projet. »

Et si une durée change ? On refait les calculs à partir de la tâche modifiée, ou on raisonne :

• si la migration des données (G, critique) dure 6 jours au lieu de 4, le chemin critique s'allonge de 2 jours : le projet dure 21 jours ;
• si le choix de la sauvegarde (D, non critique, t = 5, T = 12) dure 9 jours au lieu de 2, D finit au plus tôt à 14, F commence à 14 au lieu de 12 et finit à 16, date où G finit aussi : I commence toujours à 16, le projet dure toujours 19 jours. Mais D, B et F deviennent critiques : il y a maintenant deux chemins critiques, et plus aucune réserve sur cette branche.

En Python : les dates d'un projet

def dates_mpm(taches):
    """taches : dict tâche -> (durée, liste des tâches antérieures),
    les tâches étant données dans un ordre compatible avec les niveaux.
    Renvoie (durée du projet, dates au plus tôt, dates au plus tard)."""
    tot = {}
    for x, (d, anterieures) in taches.items():
        tot[x] = max((tot[p] + taches[p][0] for p in anterieures), default=0)
    fin = max(tot[x] + d for x, (d, _) in taches.items())
    suivantes = {x: [y for y, (_, ant) in taches.items() if x in ant] for x in taches}
    tard = {}
    for x in reversed(list(taches)):
        d = taches[x][0]
        tard[x] = min((tard[s] for s in suivantes[x]), default=fin) - d
    return fin, tot, tard

projet = {"A": (3, []), "B": (2, ["A"]), "C": (6, ["A"]), "D": (2, ["B"]),
          "E": (3, ["C"]), "H": (2, ["B"]), "F": (2, ["D", "E"]),
          "G": (4, ["E"]), "I": (2, ["F", "G"]), "J": (1, ["H", "I"])}
fin, tot, tard = dates_mpm(projet)
print(fin)                                          # 19
print([x for x in projet if tot[x] == tard[x]])     # ['A', 'C', 'E', 'G', 'I', 'J']

Les logiciels de gestion de projet (GanttProject, ProjectLibre, Microsoft Project) font exactement ces calculs quand tu saisis des tâches, des durées et des liens « fin-début ». Le chapitre Planifier : WBS, diagramme de Gantt et chemin critique du cours Gestion de projet montre comment ce planning s'intègre à la conduite d'un projet informatique, du découpage en tâches au suivi de l'avancement.

Exercices

petit = {"A": (2, []), "B": (4, []), "C": (3, ["A"]),
         "D": (5, ["A", "B"]), "E": (2, ["C"]), "F": (1, ["D", "E"])}
fin, tot, tard = dates_mpm(petit)
print(fin, tot, tard)
# 10 {'A': 0, 'B': 0, 'C': 2, 'D': 4, 'E': 5, 'F': 9} {'F': 9, 'E': 7, 'D': 4, 'C': 4, 'B': 0, 'A': 2}