L'ordonnancement PDF

L’ordonnancement ─ C’est quoi l’ordonnancement? ─ Pourquoi l’ordonnancement? ─ La méthode MPM: Méthode des Potentiels Métra ─ La méthode PERT: Program Evaluation and Review Technique ─ Diagramme de Gantt 1  10. La...

L’ordonnancement ─ C’est quoi l’ordonnancement? ─ Pourquoi l’ordonnancement? ─ La méthode MPM: Méthode des Potentiels Métra ─ La méthode PERT: Program Evaluation and Review Technique ─ Diagramme de Gantt 1  10. La planification Les retards apportés aux réalisations de projets dus en général à: − La fixation arbitraire d'un calendrier (planning). − Le manque de coordination entre les responsables des opérations concernant l'ordre de passage des différentes tâches et leur fin. C’est l’activité qui consiste à Conception déterminer et à ordonnancer les tâches du projet, à estimer leurs charges et à déterminer Planning Lancement les profils nécessaires à leur réalisation. Planification − Déterminer si les objectifs sont réalisés ou dépassés − Suivre et communiquer l’avancement Réalisation du projet − Affecter les ressources aux tâches Terminaison Cycle de vie d'un projet  11. Ordonnancement L'ordonnancement consiste à ordonner dans le temps un ensemble de tâches contribuant à la réalisation d'un même projet. Trouver la meilleure organisation possible des tâches pour minimiser le temps de la réalisation du projet et respecter la contrainte du temps 3  10. La planification Faire du café "à l'ancienne" Tâches Durée en Symboles Tâches immédiatement minutes précédentes Sortir les instruments nécessaires a (cafetière, café, moulin à café, casserole, filtre) 5 -- b Moudre le café 2 a c Faire chauffer l'eau 4 a d Verser le café moulu dans le filtre 1 b e Verser doucement l'eau sur le café moulu 3 c, d f Placer les tasses, cuillers, sucrier sur la table 3 -- g Apporter la cafetière et servir 2 e, f 4 La durée totale des tâches est de 20 minutes, mais on peut faire mieux !  11. Ordonnancement- définitions ─ Planning (calendrier): Liste de toutes les tâches avec leur durée prévue et les liens d’antériorité immédiats entre les tâches (les contraintes d'antériorité à respecter). ─ Tâches successives : Tâches qui s’effectuent les unes après les autres. ─ Tâches en parallèle : Tâches qui s’effectuent simultanément. ─ Date au plus tôt d’une tâche: Date à laquelle une tâche peut commencer, sachant que les tâches précédentes sont achevées, sans retarder la durée du projet. 5  11. Ordonnancement - définitions ─ Date au plus tard d’une tâche: Date limite de commencement d’une tâche, sans retarder la date au plus tôt de la tâche suivante. ─ Tâche critique : Tâche pour laquelle la date au plus tôt est égale à la date au plus tard. Tout retard dans la réalisation de cette tâche entraîne un retard du projet. ─ Chemin critique : Chemin le plus long reliant la première tâche à la dernière. Il passe par l’ensemble des tâches critiques.  Ensemble des tâches dont la durée à un impact direct sur la date de fin du projet. En cas de retard sur l’une de ces tâches, la date de fin du projet sera décalée. 6  11. Ordonnancement: Méthodes d’Ordonnancement 1. La méthode MPM (Méthode des Potentiels Métra) : Mise au point en France par Bernard. Roy (armement du paquebot France, 1958). 2. La méthode PERT (Program Evaluation and Review Technique) : Méthode développée par la marine américaine mise en place en 1957 (construction des fusées Polaris, projet Apollo). 3. Diagramme de Gantt (appelé aussi planning à barres) développé par Henry L. GANTT, ingénieur américain vers 1910. 7  11. Ordonnancement : La méthode MPM 1. Identifier les tâches du projet, les durées et attribuer un symbole à chaque tâche (par exemple: A, B, C…). 2. Déterminer pour chaque tâche la ou les tâches immédiatement antérieures (précédentes). 3. Ordonnancer les tâches par niveaux en respectant les contraintes à partir du planning: Placer au niveau 0 toutes les tâches qui n'ont pas de tâche antérieure. Barrer les tâches de niveau 0 dans la colonne "Tâches antérieures". Placer au niveau 1 toutes les tâches qui se retrouvent maintenant sans tâche antérieure. On déterminera ainsi le niveau de chaque tâche : les tâches de niveau k+1 seront les tâches dont les tâches antérieures sont de niveau inférieur avec au moins une tâche de niveau k parmi elles. a -- 0 a -- 0 a -- 0 b a b a 1 b a 1 Exemple: c a c a 1 c a 1 8 d b d b d b 2 e c, d e c, d e c, d 3  11. Ordonnancement : La méthode MPM La MPM utilise les conventions suivantes pour élaborer le graphe: − chaque tâche est représentée par un sommet − les contraintes de succession sont symbolisées par les arcs − chaque tâche est renseignée sur sa durée ainsi que sur la date à laquelle elle peut commencer au plus tôt ("date au plus tôt") et au plus tard ("date au plus tard") pour respecter le délai optimal de réalisation du projet. − le graphe commence et termine sur 2 sommets, respectivement appelés "Début" et "Fin" symbolisant les début et fin des opérations (mais ne correspondant pas une tâche).  Date au Date au Date au Date au plus tôt plus tard plus tôt plus tard de A de A Durée de la tâche A A B 9 Tâche A Tâche B  11. Ordonnancement : La méthode MPM Pour construire un graphe MPM ,on procède par niveaux : 1. On place d’abord le somment de début; 2. On identifie les tâches de niveau 0 et les relie au sommet «début»; 3. On identifie ensuite les tâches de niveau 1 et on les positionne sur le graphe en les reliant à leurs antécédents; 4. On contenue ainsi pour chaque niveau suivant jusqu'à ce que toutes les tâches aient pu être positionnées sur le graphe et reliées entre elles ; 5. Les tâches n'ayant pas de descendant sont à la fin reliées au sommet « Fin ». 10  11. Ordonnancement: La méthode MPM Exemple: La construction d'un complexe administratif se décompose en plusieurs tâches décrites dans le calendrier. Ce dernier donne également les précédences à respecter lors de la planification des travaux ainsi qu'une estimation de la durée (en mois) de chacune des tâches. Le but est de déterminer la durée minimale de ce projet. Tâches Nature de la tâche Durée Tâches (mois) précédentes A Terrassement, assainissement 3 B Recrutement d’une équipe de sécurité 2 C Commande des machines 4 D Construction du bâtiment administratif 2 A E Construction des ateliers 1 A F Formation de l’équipe de sécurité 3 B 11 G Aménagement des bureaux 2 D H Installation des machines 4 E, C, F  11. Ordonnancement: La méthode MPM Ordonnancement des tâches par niveaux Tâches Tâches niveau Tâches Tâches niveau Tâches Tâches niveau antérieures antérieures antérieures A 0 A 0 A 0 B 0 B 0 B 0 C 0 C 0 C 0 D A D A 1 D A 1 E A E A 1 E A 1 F B F B 1 F B 1 G D G D G D 2 H E, C, F H E, C, F H E, C, F 2 Tâches de niveau 0 : Tâches de niveau 1 : Tâches de niveau 2: (tâches sans pré-requis) N1 = {D; E; F} 12 N2 = {G;H} N0 = {A; B; C}  11. Ordonnancement: La méthode MPM On ajoute un sommet Début et un sommet Fin qui correspondent respectivement au début et à la fin des travaux Niveau N0 Niveau N1 Niveau N2 A D G Début Fin E B F H 13 C  11. Ordonnancement : La méthode MPM Construction du graphe : On relie les tâches par les tâches immédiatement antérieures. 3 2 0 A D G 2 3 Début Fin 0 E 4 1 0 2 3 B F H 4 C  11. Ordonnancement : La méthode MPM Par exemple, le sommet H admet 3 précédents (C, E et F). Donc il faut que les tâches C, E et F soient finies avant de pouvoir commencer la tâche H. 3 2 0 A D G 2 3 Début Fin 0 E 4 1 0 2 3 B F H 4 15 C  11. Ordonnancement : La méthode MPM La date de début au plus tôt de la tâche i , notée Ti , est la date à laquelle peut commencer au plus tôt la tâche i. Ti est la somme des délais prise sur la succession la plus défavorable des débuts de tâches commençant par la tâche initiale (Début) et se terminant par la tâche i. T0 = Tdébut = 0 et 𝐓𝐢 = 𝐦𝐚𝐱 𝐣∈𝐏 𝐢 (𝐓𝐣 + 𝐕 𝐣, 𝐢 ) P(i) est l’ensemble des tâches prédécesseurs de i V(i,j) le potentiel de l’arc reliant i à j Ti représente concrètement le temps MAXIMUM nécessaire pour atteindre ce sommet. 16  11. Ordonnancement : La méthode MPM Détermination des dates de début au plus tôt T0 = Tdébut = 0 et 𝐓𝐢 = 𝒎𝒂𝒙𝒋∈𝑷 𝒊 (𝑻𝒋 + 𝑽 𝒋, 𝒊 ) T(Début) = 0 T(A) = 0 ; T(B) = 0 ; T(C) = 0 Tâches Tâches antérieur T(D) = max[T(A) + v(A;D)] =0+3 P(D)={A} es A T(E) = max[T(A) + v(A; E)] = 0+3 P(E)={A} B T(F) = max[T(B) + v(B; F)] = 0+2 C P(F)={B} T(G) = max[T(D) + v(D; G)] = 3+2=5 D A P(G)={D} E A T(H) = max[T(E) + v(E;H); T(F) + v(F;H); T(C) + v(C;H)] F P(H)={E, B F, C} = max[3 + 1; 2 + 3; 0 + 4] = 5 G D H E, C, F T(Fin) = max[T(G)+v(G; Fin);T(H) + v(H; Fin)] P(Fin)={G, H} 17 Fin G, H = max[5+2; 5+4] = 9  11. Ordonnancement : La méthode MPM Le chemin le plus long entre les deux sommets Début et Fin est appelé chemin critique. Dans notre cas, il passe par les sommets B, F et H. Les tâches B, F et H sont alors dites tâches critiques. Le chemin de valeur maximale entre Début et Fin a pour valeur 9. Ainsi, la durée minimale du projet est de 9 mois. 0 3 3 2 5 0 A D G 2 0 3 9 Début 3 Fin 0 E 4 1 0 2 5 0 2 3 B F H 18 4 0 C  11. Ordonnancement : La méthode MPM Date de début au plus tard d’une tâche i notée Ti* est la date limite de commencement d’une tâche, sans retarder la date au plus tôt de la tâche suivante: Tfin*= Tfin = et Ti*= 𝒎𝒊𝒏𝒋∈𝑺 𝒊 (Tj*-V(i,j)) V(i,j) le potentiel de l’arc reliant la tâche i à la tâche j S(i) désigne l'ensemble des successeurs de la tâche i. Ti* représente concrètement la date à laquelle cet sommet doit obligatoirement être atteint si l'on ne veut pas augmenter la 19 durée totale du projet,  11. Ordonnancement : La méthode MPM Détermination des dates de début au plus tard : On commence par le sommet Fin de niveau le plus élevé jusqu‘à le sommet début: Tfin*= Tfin = 0 et Ti*= 𝒎𝒊𝒏𝒋∈𝑺 𝒊 (Tj*-V(i,j)) T*(Fin) = T(Fin) = 9 Tâches Tâches antérieur T*(G) = T*(Fin)-V(G,Fin)=9 - 2 = 7 es A T*(H) =T*(Fin)-V(H,Fin)= 9 - 4 = 5 B T*(D) = T*(G)-V(D,G)=7 - 2 = 5 C D A T*(E) =T*(H) -V(E,H)= 5 - 1 = 4 E A T*(F) = T*(H) -V(F,H)= 5 - 3 = 2 F B T*(A) =min(T*(E) -V(A,E), T*(D) -V(A,D)) G D H E, C, F =min[ 4 – 3; 5-3] = 1 Fin G, H 20 T*(B) = T*(F) -V(B,F)= 2 - 2 = 0  11. Ordonnancement : La méthode MPM 0 1 3 3 5 2 5 7 0 A D G 2 0 0 3 9 9 Début 3 4 Fin 0 E 4 1 0 0 2 2 5 5 0 2 3 B F H 4 0 1 C Remarques : Pour les tâches critiques, on a T*i = Ti La durée minimale du projet est égale à la somme des durées des tâches critiques. 21 Dans notre cas : d(B) + d(F) + d(H) = 2 + 3 + 4 = 9  11. Ordonnancement : La méthode MPM Marge totale d’une tâche: C'est le retard maximum que l'on peut prendre dans la mise en route de la tâche i sans remettre en cause les dates au plus tard des tâches suivantes (et donc sans retarde la fin du projet). Elle est dénie par : La marge totale, d'après la définition, est strictement positive pour les tâches non critiques et elle est nulle pour les tâches critiques. La marge totale d'une tâche représentera concrètement le retard maximal qu'on pourra prendre dans la réalisation d'une tâche sans retarder l'ensemble du projet 22 11. Ordonnancement : La méthode MPM: Marge totale, marge libre Dans le cas de l'exemple, on obtient les marges totales suivantes : 0 1 3 5 5 7 3 2 0 0 0 A D G 2 3 9 9 Début 3 4 Fin 0 E 4 1 0 0 2 2 5 5 0 2 3 B F H 23 4 0 1 C 11. Ordonnancement : La méthode MPM: Marge totale, marge libre Marge libre d'une tâche La marge libre de la tâche i est le retard maximum que l'on peut attribuer au démarrage de cette tâche sans changer les dates de début au plus tôt des tâches suivantes (c.-à-d. sans changer la suite de l'ordonnancement). Elle est dénie par : où S(i) est l'ensemble des suivants de i. La marge libre d'une tâche représentera concrètement le retard maximal qu'on pourra prendre dans la réalisation d'une tâche sans retarder le début des tâches suivantes 24 11. Ordonnancement : La méthode MPM: Marge totale, marge libre Calcul des marges libres : mL(A) = min[T(D) - T(A) - v(A;D);T(E) - T(A) - v(A; E)] = min[3 - 0 - 3; 3 - 0 - 3] = 0 mL(B) = T(F) - T(B) - v(B; F) = 2 - 0 - 2 = 0 mL(C) = T(H) - T(C) - v(C;H) = 5 - 0 - 4 = 1 mL(D) = T(G) - T(D) - v(D;G) = 5 - 3 - 2 = 0 mL(E) = T(H) - T(E) - v(E;H) = 5 - 3 - 1 = 1 mL(F) = T(H) - T(F) - v(F;H) = 5 - 3 - 2 = 0 mL(G) = T(Fin) - T(G) - v(G; Fin) = 9 - 5 - 2 = 2 mL(H) = T(Fin) - T(H) - v(H; Fin) = 9 - 5 - 4 = 0 25 11. Ordonnancement : La méthode MPM: Marge totale, marge libre Tableau des marges : Les tâches dont la marge totale est nulle, sont critiques (elles compose le chemin critique). 0 1 3 5 5 7 3 2 0 0 0 A D G 2 3 9 9 Début 3 4 Fin 0 E 4 1 0 0 2 2 5 5 0 2 3 B F H 26 4 0 1 C 11. Ordonnancement : La méthode MPM: Marge totale, marge libre Signification de la marge libre : Prenons par exemple la tâche G qui a une marge totale de 2. Si son précédent direct la tâche D est programmée au plus tard, c'est-à-dire en 5, la date de début au plus tôt de G devient 7 et donc voit sa marge s'annuler. Dès qu'on utilise la marge de la tâche D, elle réduit donc celle de G. Par contre si on utilise la marge de la tâche G en la programmant au plus tard (en 7) cela ne réduit pas la marge des autres tâches du projet. On peut donc utiliser librement cette marge de 2 unités de G. 27  11. Ordonnancement: Plan de l'ordonnancement Les méthodes d’ordonnancement permettent d’élaborer un graphe qui représente l’ensemble des tâches composant le projet ainsi que les liens qui existent entre elles. Sur le graphe, apparaissent également la durée de chaque tâche, la date à laquelle elle peut débuter au plus tôt et au la date à laquelle elle peut débuter plus tard. Plan de l'ordonnancement 1. Identification les tâches du projet, les durées et les contraintes; 2. Ordonnancer les tâches par niveaux en respectant les contraintes ; 3. Représenter le graphe le graphe du projet ; 4. Calculer les dates de réalisation au plus tôt de chaque tâche ; 5. Calculer les dates de réalisation au plus tard de chaque tâche ; 6. Déterminer les chemins critiques et les tâches critiques ; 28 7. Calculer les marges (marges libres et marges totales) ; 8. Interprétation.