MAD Cours et exercices Ordonnancement et Statistiques PDF

Preview

Summary

Doc comportant l'embles des cours et exercices d'Ordonnancement...

Description

MAD - Méthodes d’Aide à la Décision Manuel de cours - Ordonnancement

Grenoble Ecole de Management Version 2.0

Marc Humbert

TD 1

L'étude et la conduite d’un projet complexe, et ceci dans des domaines très variés, nécessitent une parfaite coordination (un parfait ordonnancement) des différentes tâches inhérentes à ce projet. De manière très générale, on peut formuler un problème d’ordonnancement de la manière suivante : « soit un objectif dont la réalisation suppose l’exécution préalable de multiples tâches soumises à de multiples contraintes. Il s’agit alors de trouver un ordre et un calendrier d’activation de ces tâches, tels que ces contraintes soient satisfaites ». Le bon ordonnancement d’un projet doit permettre, notamment, de : o

Déterminer le processus opérationnel optimum de réalisation du projet ;

o

Evaluer l’impact de possibles dysfonctionnements ;

o

Fixer les dates de réalisation du projet ;

o

Hiérarchiser les priorités et les points critiques ;

o

Optimiser la répartition des moyens humains, matériels et financiers ;

o

Préciser les responsabilités ;

o

Suivre et de contrôler la progression des tâches.

Pour bien comprendre ce dont il va s’agir, prenons dès maintenant un exemple très concret : un projet (simplifié) de construction d’un nouveau siège social. La première étape de ce projet consiste à déterminer les tâches qui sont à accomplir, ainsi que leurs durées (nous supposerons, à des fins de clarification, que le projet se décompose en 7 tâches). Bien sûr, toutes les tâches ne peuvent être accomplies au même moment, et la deuxième étape consiste donc à déterminer les contraintes d’antériorité entre les tâches. Concrètement, les fondations (la tâche « A ») doivent précéder le gros œuvre (tâche B), qui lui-même doit précéder les huisseries, l'électricité, la plomberie et la toiture (les tâches C, D, E, F, respectivement). C’est seulement lorsque ces quatre dernières tâches seront achevées, que les travaux de finition (tâche G) pourront commencer. Pour le présenter de manière synthétique :

Tâche

Description

Durée

A B C

Fondations Gros-œuvre Huisseries Electricité Plomberie Toiture Finitions

5 12 4 6 5 7 15

D E F G

Contraintes d’antériorité

A B B B B C, D, E, F

Comment optimiser la planification d’un tel projet ? Grâce aux « modèles de graphes ». Concrètement, la méthode « PERT » (« Project Evaluation and Review Technique ») a été initialement mise au point pour la planification du projet POLARIS (construction de missiles à ogive nucléaire), dont elle a permis de réduire la durée de 7 à 4 ans. Il existe quelques variations dans la manière de planifier les projets, et dans la complexité des modèles utilisés, mais tous ont pour objectifs : (1) de visualiser l’ensemble des tâches et des contraintes d’un projet et (2) de déterminer un calendrier optimal d’exécution des tâches.

QUELQUES BASES

Dans un modèle de graphe, une tâche est représentée par un arc, les sommets correspondant alors aux étapes du projet 1. Formellement, l’on relie deux sommets i et j par un arc si la tâche i doit précéder la tâche j (ce qui matérialise la contrainte d’antériorité de i sur j). Appliquons cette méthode sur notre exemple de construction d’un nouveau siège social ; nous obtenons le graphe suivant :

Détaillons un peu. Sur ce graphe, la durée d’une tâche est reportée à l'intérieur du cercle (sommet) correspondant à cette tâche et/ou sur les arcs qui partent de ce cercle. Il serait possible, de manière optionnelle, d’ajouter au graphe un cercle qui matérialiserait le début du projet. Dans notre graphe, nous pouvons observer qu’une seule tâche n’a pas de contrainte d’antériorité : la tâche A. C’est donc par cette tâche que nous devons démarrer le projet, et le cercle correspondant peut faire office de sommet de début de projet. S’il y avait plusieurs tâches pouvant être démarrées en parallèle dès le départ, nous pourrions, de manière à obtenir un graphe plus « propre », ajouter un cercle de début de projet qui serait relié à toutes ces tâches. Dans notre graphe, nous avons ajouté un sommet de fin de projet, qui, comme vous pouvez le voir, ne correspond à aucune tâche : cela nous permettra de ne pas oublier de tenir compte de la durée de la tâche G dans le calcul de la durée totale du projet. De manière à réaliser le projet en un temps minimal tout en respectant ses contraintes, il nous faut déterminer un calendrier d’activation des tâches. Cette durée minimale du projet correspond au chemin le plus long dans le graphe. Cela peut paraître paradoxal au premier abord, mais il faut bien que nous ayons le temps d’effectuer toutes les tâches avec tous les enchainements possibles, en particulier le plus long. Pour chaque tâche, nous allons commencer par déterminer la date au plus tôt de début d’exécution. Pour qu’une tâche puisse commencer, il est nécessaire que toutes les tâches qui la relient à la tâche du début du projet soient réalisées. Il faut donc évaluer le plus long chemin entre le sommet initial du graphe et le sommet correspondant à cette tâche. On utilise un algorithme de recherche du plus long chemin dans un graphe. Cet algorithme utilise un principe très simple, mais extrêmement

1

On parle de méthode potentiel-étapes, ou AOA (Activities On Arcs), en Anglais. Cette méthode étant cependant un peu lourde du fait de la nécessité d’introduire des tâches fictives, nous préférerons dans le cadre de ce cours utiliser une autre méthode, dite « Potentiel-tâches », ou AON (Activities On Nodes), en Anglais.

puissant : le principe d’optimalité de Bellman. Cet algorithme spécifie simplement que pour trouver le plus long chemin dans un graphe, à partir d’un sommet de départ jusqu’à un sommet quelconque S du graphe, il suffit de prendre la plus grande parmi toutes les longueurs maximales des chemins qui arrivent aux sommets prédécesseurs, additionnées des longueurs des arcs reliant ces sommets à S. Nous allons l’expliciter davantage et l’illustrer par un exemple. Outil #1 : algori lgorithme thme de recherche des dates au plus tôt. Tant qu’il existe un sommet non traité, choisir un sommet S dont tous les prédécesseurs pi ont été traités ; la date au plus tôt de S (dplustot(S)) est égale au maximum pour tous les prédécesseurs pi de la somme (date au plus tôt de pi + durée de pi), soit dplustot(S)=max(dplustot(pi)+d(pi). Une remarque : on procède niveaux par niveaux dans le graphe. Pour simplifier, on peut commencer par faire un premier parcours du graphe pour numéroter les sommets. Les sommets de niveau 1 correspondent aux tâches que l’on peut démarrer dès le début du projet. Les sommets de niveau 2 sont tous ceux qui ont au moins un prédécesseur de niveau 1 et dont tous les prédécesseurs sont de niveau 1 ou inférieur. On procède ainsi en parcourant tous les sommets du graphe. Une fois les dates au plus tôt déterminées, il nous faut fixer les dates de réalisation au plus tard. Outil #2 : algorithme de recherche des dates au pl plus us tard tard.. Les dates de réalisation au plus tard sont obtenues par le même calcul que précédemment, mais en partant « de la fin du graphe ». Pour trouver la date au plus tard de début d’une tâche i, il faut avoir déjà calculé les dates au plus tard de toutes les tâches qui suivent la tâche i. La date au plus tard de la tâche i sera alors égale à la valeur minimale de la différence (date au plus tard(si)-durée(i)). Outil #3 : marges. La marge totale d’une tâche est la différence entre sa date au plus tard et sa date au plus tôt. La marge totale d’une tâche critique est nulle. La marge libre d’une tâche est le délai maximal par rapport à la date au plus tôt pour le démarrage d’une tâche tel que le calendrier des tâches qui suivent ne soit pas modifié. Pour une tâche i qui a une date au plus tôt dplustot(i) et une durée d(i), elle est égale à la différence entre la plus petite des dates au plus tôt des tâches qui suivent et (dplustot(i)+d(i)). Outil #4 : tâches critiques et chemin critique. On dit qu’une tâche de A vers B est « critique » si la différence entre la date au plus tard de B et la date au plus tôt de A est égale à la durée de la tâche à accomplir. L’ensemble des tâches critiques constitue le chemin critique, c’est-à-dire le chemin sur lequel aucune tâche ne doit avoir de retard pour ne pas retarder l’ensemble du projet 2.

Nous obtenons, au final, le graphe ci-après.

2 Outil #5 : diagramme de Gantt. Dans un diagramme de Gantt, on représente le temps en abscisse et on représente la durée d’exécution des tâches par des barres horizontales. On peut utiliser des couleurs différentes pour les tâches critiques et représenter par des pointillés la marge des tâches non critiques. Ces diagrammes sont historiquement antérieurs aux modèles PERT (et équivalents) et sont moins « efficaces » pour l’optimisation du calendrier dans la mesure où les contraintes ne sont pas représentées. En revanche, ils sont encore utilisés en complément des modèles PERT car ils sont d’excellents outils de communication sur le planning du projet et son avancement.

TD 2

Pour aller plus loin, et ne pas se limiter à la recherche d’un calendrier d’exécution des tâches, nous allons à présent détailler 3 modèles plus « réalistes », qui prennent en compte le hasard, les coûts, et d’autres types de contraintes. Outil #6 : modèle probabili probabiliste ste ste.. En réalité, la véritable méthode PERT permet d’associer des durées aléatoires aux tâches. C’est évidemment un modèle plus réaliste : le responsable d’une tâche a souvent du mal à en estimer la durée de manière certaine et aura plus de confort à travailler à partir de 3 estimations basées sur son expérience :

o pi = estimation de la durée la plus probable, la plus vraisemblable, de la tâche i ; o ai = estimation optimiste ; on envisage le scénario de déroulement le plus favorable ; o bi = estimation pessimiste ; on se place dans le scénario le plus défavorable. A partir de ces 3 estimations, on modélise habituellement l’espérance et l’écart-type de la durée Di de la tâche en fonction de pi, ai et bi :

Illustrons. Pour notre projet de construction d’un nouveau siège social, nous donnons dans le tableau ci-après les durées pi, ai et bi de chaque tâche, ce qui nous permet, comme vous pouvez le voir, de calculer l’espérance et l’écart-type de la durée de la tâche.

Tâche A B C D E F G

pi 5 12

ai 4 10

bi 7 14

E(Di) 5,17 12

4 6 5 7 15

3 5 4 5 12

6 7 7 12 20

4,17 6 5,17 7,5 15,33

s 0,5 0,67 0,5 0,33 0,5 1,17 1,33

Fonctionnement du modèle probabil probabiliste iste. Pour la suite, on applique la méthode habituelle de détermination de calendrier en utilisant la durée espérée de chaque tâche. On peut additionner ces durées espérées pour déterminer la date au plus tôt espérée pour chaque tâche, et, finalement, l'espérance de la durée totale du projet qui est égale à la somme des durées espérées des tâches critiques.

Pour calculer la variance de la durée du projet, on peut également additionner les variances des tâches critiques, mais uniquement en faisant l’hypothèse que ces durées sont des variables indépendantes. On obtient l’écart-type de la durée du projet en prenant la racine carrée de la variance trouvée. Dans notre exemple, la variance du projet est égale à la somme des variances des 4 tâches critiques : A, B, F et G soit : 0,5² + 0,67² + 1,17² + 1,33² = 3,83. L’écart-type est donc égal à 1,96. Enfin, si le nombre de tâches critiques est suffisamment grand, on peut appliquer le théorème central-limite et considérer que la durée du projet suit une loi Normale, et il est alors possible de calculer des probabilités. On peut, par exemple, calculer la probabilité d’avoir une durée du projet inférieure à 43 jours. On trouve 0,9372. Outil #7 : la méthode CPM (Cri (Critical tical Path Method). En réalité, dans la pratique, la durée d’une tâche est souvent étroitement liée aux moyens mis en œuvre pour la réaliser, et donc à son coût. On va donc supposer qu’il est possible d’accélérer une tâche à partir de sa durée normale pour arriver à une durée dite « minimale ». Le coût correspondant à cette durée minimale est évidemment supérieur au coût correspondant à la durée normale. Il est pratique de faire une approximation linéaire de cette courbe durée/coût comme le montre le schéma ci-après.

Principe de ll’’algorithme CPM. Initialisation : on commence par déterminer l’ordonnancement de coût minimum. Cela conduit à un premier chemin critique. Ensuite, on procède étape par étape. A chaque étape, on cherche à réduire la durée du projet en réduisant la durée d’une ou plusieurs tâches critiques (ce qui, bien sûr, élève le coût). Pour cela, on examine le chemin critique :

o

S’il n’y en a qu’un, on choisit de réduire la durée de la tâche critique dont le coût d’accélération est le plus bas. On réduit cette tâche jusqu’au point où : soit on atteint sa durée minimale, soit un autre chemin devient critique ;

o

Dans le cas où il y a plusieurs chemins critiques, il faut considérer toutes les combinaisons de réductions de durées de tâches critiques permettant de réduire tous les chemins critiques. Jusqu’au moment où on ne peut plus réduire les chemins critiques.

Pour illustrer cet algorithme, reprenons l’exemple du projet de construction d’un nouveau siège social. Nous donnons les durées minimales et les coûts d’accélération dans le tableau suivant :

Tâche A

Durée normale 5

Durée minimal minimale e 5

B C D E F G

12 4 6 5 7 15

12 3 5 3 4 10

Coût d’accélér d’accélération ation

400 500 400 700 400

A partir de ces données, on détermine le calendrier d’exécution du projet en utilisant les durées normales, ce qui nous donne le graphe ci-après.

Le chemin critique est composé des tâches A, B, F et G. La durée des tâches A et B ne pouvant pas être réduite, on choisit de réduire parmi les tâches critiques F et G celle qui a le coût d’accélération le plus bas, c’est-à-dire la tâche G. On peut réduire la durée de cette tâche de 1 jour, pour un coût de 400, de 2 jours pour un coût de 800, et jusqu’à 5 jours pour un coût de 400 x 5 = 2000 (on passe alors de la durée normale 15 à la durée minimale 10). On met à jour le graphe :

Le chemin critique est toujours composé des tâches A, B, F et G. La durée de la tâche G ne peut plus être réduite. La seule tâche critique qui peut encore être réduite est la tâche F. On peut réduire la durée de cette tâche de 1 jour pour un coût de 700, mais on ne peut pas la réduire de plus de 1 jour car la tâche D devient critique, ce qui crée un second chemin critique dans le graphe. On réduit donc la durée de la tâche F de 7 à 6 jours pour un coût de 700. On met à jour le graphe une nouvelle

fois, ce qui donne :

Nous avons à présent 2 chemins critiques : {A, B, F, G} et {A, B, D, G}. Si nous voulons encore réduire la durée du projet, il faut réduire la durée des deux chemins critiques. Réduire la durée de B et G serait possible, mais ces 2 tâches ne peuvent plus être accélérées. La seule solution est de réduire à la fois D et F. Nous ne pouvons réduire la durée de ces 2 tâches que d’une seule journée, car, audelà, la tâche E deviendrait également critique. Nous réduisons donc la durée de la tâche D de 6 à 5 jours et celle de la tâche F de 6 à 5 jours, pour un coût total de 1200. On met à jour le graphe une dernière fois :

Synthèse et décision décision.. Généralement, il existe des coûts indirects associés à un projet (par exemple, le coût de location d’un matériel ou d’un bâtiment). Dans notre exemple, on supposera que ces coûts indirects s’élèvent à 1000 par jour. Les coûts indirects s’élèvent donc à 39000 lorsque le projet est réalisé en 39 jours, et à 32000 lorsqu’il se réalise en 32 jours. Dès lors, le tableau ci-dessous présente une synthèse des étapes CPM, avec l’ensemble des coûts associés au projet :

Etape

0 1 2 3

Accélération

Durée du projet

Coûts accélération

39 34 33 32

0 2000 700 1200

G (5 jours) F (1 jour) D et F (1 jour

Coûts accélération cumulé cumuléss 0

2000 2700 3900

Coûts indirects

Coût total

39000 34000 33000 32000

39000 36000 35700 35900

Ou, sous forme graphique :

Le tableau (ou le graphique) permet d’apprécier les coûts totaux correspondant aux différentes durées de projet comprises entre 39 et 32 jours. Si on privilégie le critère du coût total minimal, le meilleur choix est de réaliser le projet en 33 jours pour un coût total de 35700.

A l’issue du cours sur l’ordonnancement, vous devez savoir : 1. 2. 3. 4. 5. 6. 7. 8.

Calculer la date au plus tôt d’une tâche i ; Calculer la date au plus tard d’une tâche i ; Calculer la marge totale d’une tâche i ; Déterminer le chemin critique d’un projet ; Déterminer la durée minimale d’un projet ; Calculer la durée minimale espérée d’un projet ; Calculer la probabilité d’avoir une durée minimale/maximale ; Utiliser la méthode CPM.

EXERCICES SUR L’ORDONNANCEMENT

Exercice 1

Exercice 2

Les contraintes associées au projet sont les suivantes : o o o o o o o

La grue ne peut fonctionner que si le branchement électrique est réalisé ; On a besoin de la grue pour les fondations ; L’installation de la fosse septique et les fondations ne peuvent être réalisées que si les travaux de terrassement sont terminés ; Le gros œuvre ne peut commencer que lorsque les fondations sont terminées ; La maçonnerie doit être terminée pour que les tâches 7,8 et 9 puissent débuter ; La couverture se décompose en deux phases : construction de la charpente (tâche 7' de durée 8 jours) et couverture proprement dite (tâche 7'' de durée 6 jours) ; Les travaux d’électricité se décomposent en gros travaux (tâche 9' de durée 5 jours) et petits

o o o

o o

o

travaux (tâche 9'' de durée 5 jours) ; Les travaux de menuiserie se décomposent en huisseries (tâche 10' de durée 7 jours) et petits travaux (tâche 10'' de durée 4 jours) ; Il est nécessaire que la plomberie, la charpente, les huisseries et les gros travaux d'électricité soient terminés pour que l'on puisse commencer le plâtre ; Les petits travaux d'électricité et de menuiserie peuvent commencer dès que les plâtres sont secs (la durée de séchage est de 21 jours, à partir du moment où les plâtres sont terminés et la couverture achevée). Le carrelage peut commencer dès que le plâtre est terminé (il n’est pas nécessaire qu’il soit sec) ; La pose des appareils sanitaires peut être réalisée dès que le carrelage est posé ; cependant, il faut un délai de 21 jours entre le moment où les appareils sanitaires sont commandés et celui où ils sont livrés ; Les travaux de peinture ne peuvent commencer que lorsque le plâtre est sec, que lorsque les travaux de menuiserie et d'électricité sont terminés, et que lorsque le carrelage est posé.

Faites un modèle de graphe et déterminer la durée minimale des travaux, les dates au plus tôt et au plus tard, les marges totales, et le chemin critique.

Exercice 3

Exercice 4

Exercice 5...