Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

F. Jouvet, Lycée hôtelier de Nice 1/9 La méthode M.P.M., méthode des potentiels

F. Jouvet, Lycée hôtelier de Nice 1/9 La méthode M.P.M., méthode des potentiels metra [Document réalisé pour la réunion du 27 janvier 2006 organisée à Marseille] 1. Introduction : les problèmes d’ordonnancement, définitions 1.1. L’ordonnancement Supposons que nous ayons à réaliser la recette de l’Aigo boulido (ancienne recette du “ petit peuple ” méditerrannéen). À chacune des tâches élémentaires ou “ étapes ” de réalisation de la recette, nous associons une lettre code (indiquée ci- dessous entre parenthèses) et le temps nécessaire à son accomplissement. Bien évidemment la réalisation d’une telle recette ne nécessite pas un travail d’organisation si complexe qu’il faille mettre en œuvre une méthode d’ordonnancement aussi formalisée et mathématisée que celle que nous allons étudier… il ne s’agit là que d’un exemple pédagogique. Aigo boulido, recette pour 4 personnes Denrées : 6 gousses d’ail, 3 cuillerées à soupe d’huile, 1 feuille de laurier, 1 branche de sauge, 2 oeufs, 4 tranches fines de pain rassis, sel. 1. Mettre 1 litre ½ d’eau dans une casserole avec du laurier, de la sauge, du sel, et porter à ébullition (A, 5 mn). 2. Éplucher de l’ail, le hacher, le mettre dans un mortier (B, 5 mn). 3. Ajouter de l’huile d’olive dans le mortier et piler (C, 3 mn). 4. Verser ce mélange dans l’eau bouillante et cuire à feu vif pendant 10 mn (D, 10 mn). 5. Faire chauffer une soupière et mettre des tranches de pain rassis au fond (E, 5 mn). 6. Casser des œufs en séparant le blanc et le jaune, mettre les jaunes dans un bol (F, ½ mn). 7. Passer le bouillon au chinois (G, ½ mn). 8. Verser une louche de bouillon sur les jaunes d’œufs et remuer vivement (H, ½ mn) 9. Reverser cette préparation dans le bouillon en battant au fouet (I, 1mn). 10. Verser une louche de bouillon dans la soupière, laisser le pain s’imprégner, servir chaud (J, 2 mn). Nous sommes en présence d’un travail qui comprend de nombreuses tâches ou opérations, ces deux derniers termes étant synonymes. Observons maintenant les opérations B et C. Il est clair que B doit précéder C. Il est possible d’adopter la notation suivante pour symboliser l’expression “ B doit précéder C ” : B < C. Ainsi la réalisation des diverses tâches doit tenir compte de contraintes : ici B < C signifie qu’il faudra respecter la contrainte d’antériorité de B par rapport à C. B et C sont des éléments de la recette et il existe une relation, B<C, entre ces éléments. La théorie des graphes est une façon de représenter, puis d’analyser, sous forme synthétique les éléments d’un ensemble et les relations qui les unissent. F. Jouvet, Lycée hôtelier de Nice 2/9 Dans l’exemple qui nous préoccupe, les diverses tâches A, B, C... sont les éléments, et la relation que l’on met en avant est l’antériorité de certaines tâches par rapport à d’autres. Dans la théorie des graphes chaque élément est représenté par un sommet et la relation entre deux sommets par un arc (→) si la relation est à sens unique, par une arête (↔) si la relation n’est pas à sens unique. Pour ce qui concerne la contrainte d’antériorité entre B et C il s’agit d’une relation à sens unique puisque si B<C alors C ne peut pas précéder B. Nous aurons donc la représentation suivante : B→C Dans tout ce qui va suivre, les graphes ne comporteront que des arcs. On dit, dans ce dernier cas, que le graphe est orienté. Il nous est loisible de choisir des modes différents de représentation. Nous pouvons décider, comme indiqué plus haut, que B < C sera représenté par : Mais nous pourrions inversement décider d’associer un arc (et non plus un sommet) à chaque tâche et un sommet à l’événement “ la tâche qui précède ce sommet est achevée ”. La représentation de B < C serait alors la suivante : B (5) C(3) Le sommet numéroté 2 est l’événement “ fin de la tâche B ” (ce qui ne correspond pas forcément au début immédiat de la tâche C, mais indique simplement que si B < C, alors il faut attendre la fin de la réalisation de B pour pouvoir débuter C et que C débutera au plus tôt dès l’achèvement de B). Le sommet numéroté 3 est l’événement “ fin de la tâche C ”. On voit que la manière de modéliser le problème peut être différente alors même que notre objectif est identique : organiser au mieux la succession des tâches composant la recette. À la première façon de réaliser la modélisation correspond la méthode M.P.M. que nous allons étudier. C’est la façon française de représenter le problème. À la deuxième façon de réaliser la modélisation correspond la méthode P.E.R.T., que nous n’étudierons pas, et qui est la façon américaine de représenter le problème. 1.2. Planning d’ordonnancement ou programme Un planning d’ordonnancement ou programme est relatif à la conception ou à la réalisation d’un ensemble complexe de tâches soumises à des contraintes nombreuses. Il consiste à déterminer l’ordre et le calendrier d’exécution des différentes tâches en tenant compte des contraintes. Il doit être suivi, pour être complet, par le contrôle du déroulement des travaux et il doit prévoir la coordination entre les différentes opérations pour déceler, en temps opportun, des retards prévisibles. 1.3. Les divers types de contraintes On distingue : 1.3.1. Les contraintes potentielles, qui se subdivisent en : 1.3.1.1. Contraintes de succession ou contraintes d’antériorité : deux cas sont possibles. 1.3.1.1.1. Le cas d’une tâche qui ne peut débuter que lorsqu’une autre tâche a été exécutée. 1.3.1.1.2. Le cas d’une tâche qui ne peut débuter qu’après qu’une autre, non achevée, a débuté depuis un certain temps : il y a succession avec recouvrement. Nous traiterons essentiellement des problèmes où seuls ces deux types de contraintes existent. 1.3.1.2. Contraintes de date. Dans ce cas une tâche ne peut commencer avant une date précise. On parle aussi de contraintes de localisation temporelle. 1.3.2. Les contraintes disjonctives F. Jouvet, Lycée hôtelier de Nice 3/9 Supposons que nous ne disposions, pour la préparation de la recette l’Aigo boulido, que d’un seul point de chauffe, les autres points étant utilisés pour la préparation d’autres recettes. Alors la tâche A (porter l’eau à ébullition) ne peut pas être réalisée en même temps que la tâche E (faire chauffer une soupière). On a donc : A < E ou (exclusif) E < A. L’exécution simultanée de A et E est impossible : nous sommes en présence d’une contrainte disjonctive. 1.3.3. Les contraintes cumulatives Supposons que nous voulions impérativement exécuter tout ou partie de A et E en même temps : nous aurons besoin de cumuler deux points de chauffe durant l’exécution simultanée de A et E. Cette contrainte d’exécution simultanée que nous nous imposons crée une contrainte cumulative qui est de pouvoir disposer de deux points de chauffe au même moment. Ce cumul de deux points de chauffe ne pourra excéder les capacités disponibles au moment considéré. 2. Tableau d’analyse d’un projet et graphe M.P.M. La réalisation d’un graphe présentant l’analyse d’un problème d’ordonnancement nécessite une étude préalable des diverses tâches à considérer, de leur durée (déterminée ou aléatoire), et des relations entre les tâches (principalement les contraintes d’antériorité). Habituellement, les conclusions de cette étude font l’objet d’une synthèse sous la forme d’un tableau. À titre d’exemple voici le tableau correspondant à la réalisation de la recette de l’Aigo boulido : Tâches Opérations préalables Durées en minutes A 5 B 5 C B 3 D A, C 10 E 5 F 0,5 G D 0,5 H F, G 0,5 I H 1 J E, I 2 Sur la base de ce tableau on trace le graphe M.P.M., en utilisant la symbolique vue plus haut, graphe dans lequel : 11. Chaque opération est représentée par un “ sommet ”, habituellement dessiné sous la forme d’un rectangle dans lequel on inscrit le numéro ou la lettre code de l’opération. Le plus clair est de considérer que le sommet A représente le début de l’opération A, que le sommet B représente le début de l’opération B et ainsi de suite. 12. Chaque arc représente une contrainte de succession et l’on inscrit sur cet arc une valeur numérique, appelée potentiel, qui est le délai minimum, après le début de la tâche notée à l’extrémité initiale de l’arc, au bout duquel peut démarrer la tâche notée à l’extrémité finale de l’arc. Ici nous avons considéré que la durée d’exécution d’une tâche était en même temps le délai minimum avant de pouvoir lancer la tâche qui lui est immédiatement postérieure ; mais il n’en n’est pas toujours ainsi. 13. On introduit une opération initiale notée 0 ou 1 ou Début qui correspond au début du travail. 14. On introduit une opération finale ou terminale notée “ n ” ou Fin qui correspond à l’achèvement du travail. Le graphe associé au tableau de l’Aigo boulido est le suivant : F. Jouvet, Lycée hôtelier de Nice 4/9 3. uploads/Management/ methode-des-potentiels-metra-f-jouvet-03-2006-bts-option-a-et-b.pdf