La méthode MPM

La  méthode MPM (Méthode des potentiels métra)

Un graphe MPM sert à ordonnancer des tâches dans le temps en tenant compte des contraintes entre ces tâches. Il s’applique à des projets (constructions, informatique, etc…) ou à des processus industriels (par exemple : processus de fabrication d’une voiture…).

Le graphe PMP permet de répondre aux questions suivantes :

• Combien de temps le projet/processus durera-t-il ?
• A quel moment pourra-t-on commencer une tâche particulière ?
• Si cette tâche n’est pas terminée à temps, le projet/processus tout entier sera-t-il retardé ?
• Quelle tâche devrons-nous accélérer pour terminer le projet/processus plus tôt ?

On établit le graphe à partir d’un tableau contenant :

• La liste des tâches à réaliser
• La durée des tâches
• Les contraintes d’antériorité.

Pour Chaque tâche, on calcule quatre nombres :

• La date au plus tôt, c’est-à-dire la date à laquelle on peut commencer la tâche parce que les tâches précédentes sont terminées. On obtient cette date en calculant :

max(dates au plus tôt précédentes+ durées précédentes)

• La date au plus tard, c’est-à-dire la date maximale à laquelle on peut commencer la tâche sans repousser la fin du projet. On obtient cette date en calculant :

min(dates au plus tard suivantes- durée de la tache)

• La marge totale, c’est-à-dire le retard autorisé à la tache sans retarder la fin du projet. On obtient cette date en calculant :

(date au plus tard) – (date au plus tôt)

• La marge libre, c’est-à-dire le retard autorisé sans retarder aucune des tâches suivantes. On obtient cette date en calculant :

min(dates au plus tôt suivantes) – durée de la tâche) – date au plus tôt de la tâche)

Puis on construit le graphe, où chaque sommet est une tâche, où un arc de  à  signifie que la tâche  est antérieure à la tâche , et sur chaque sommet, on indique chacun des 4 nombres précédents, comme ceci :[pic 1][pic 2][pic 3][pic 4]

On déterminer enfin les tâches critiques, c’est-à-dire celles qui ne peuvent pas être retardées sans que l’ensemble du projet soit aussi retardé en conséquence (ce sont les tâches dont la marge totale est nulle), puis le chemin critique, c’est-à-dire la séquence des tâches critiques.

On notera que si on souhaite accélérer le projet, il est nécessaire d’essayer de réduire la durée des tâches critiques.

Exercice 0

Appliquons tout cela à l’exemple donné par le tableau de contraintes suivant :

On commence par ordonner les tâches par niveau (rappel : niveau 0 on trouve les tâches qui n’ont pas de contraintes d’antériorité et peuvent donc commencer en début de projet, et au niveau  on trouve les taches dont les tâches antérieures sont au niveau [pic 5][pic 6]

                                        [pic 9]

[pic 10]

                                                [pic 11]

                                                                                         4

le chemin critique est dans l’exemple ……………………………pour une durée totale de …………. semaines.

Exercice 1

On souhaite accomplir les tâches A, B, C, D, E, F et G ; on donne la durée de chacune, ainsi que les tâches qui doivent être réalisées auparavant :

...