Remerciez-le!

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

Recherche Opérationnelle - Ordonnancement Yves Correc 26/02/2007 3–1 Recherche

Recherche Opérationnelle - Ordonnancement Yves Correc 26/02/2007 3–1 Recherche Opérationnelle Ordonnancement Yves Correc Recherche Opérationnelle - Ordonnancement Yves Correc 26/02/2007 3–2 Sommaire 3. ORDONNANCEMENT...............................................................................................................3–3 3.1. Caractérisation d'un projet .....................................................................................................3–3 3.2. Représentation graphique......................................................................................................3–4 3.3. Problématique du chemin critique..........................................................................................3–6 3.4. Méthode (française) potentiel-tâche: MPM...........................................................................3–7 3.5. Méthode (américaine) potentiel-étape: PERT ......................................................................3–9 3.6. Modifications du projet .........................................................................................................3–10 3.7. Contraintes disjonctives .......................................................................................................3–11 3.8. Contraintes cumulatives.......................................................................................................3–14 3.9. Optimisation du coût et de la durée d'un projet ...................................................................3–24 Recherche Opérationnelle - Ordonnancement Yves Correc 26/02/2007 3–3 3. ORDONNANCEMENT 3.1. CARACTÉRISATION D'UN PROJET L'organisation d'un grand projet pose des problèmes dont la complexité et la taille ont nécessité le développement de méthodes de planification. La première étape est la caractérisation du projet: Celui-ci est décomposable en un certain nombre d'opérations (plus ou moins) élémentaires appelées tâches. Ce découpage est un délicat compromis: trop fin, il devient inextricable, trop grossier il masque l'importance de certaines opérations élémentaires. En pratique, on procède souvent par niveaux, chaque tâche identifiée pouvant être à son tour considérée comme un petit projet décomposable à un niveau inférieur. Une tâche est définie par 4 caractéristiques : - i = nom (ou code) de la tâche, - ti = date de début de la tâche (on note parfois fi la date de fin) - di = durée de tâche (di = fi – ti), - γ γ γ γik = quantité du moyen k (personnel, matière, coût...) nécessaire à l'accomplissement de la tâche i . Elle est évidemment liée à di, et peut varier au cours du temps. γ γ γ γik ti ti + di On appellera ordonnancement d'un projet tout ensemble de valeurs données aux caractéristiques ( ti, di, γ γ γ γik ) pour toute tâche i d'un projet. Ces tâches sont l'objet de contraintes (on ne peut faire n'importe quoi n'importe comment !…). Ces contraintes sont de trois types : (1) contraintes de type potentiel: tj - ti ≥ ≥ ≥ ≥ aij - Localisation temporelle absolue (une tâche doit débuter après telle date, ou bien être achevée pour telle date). - Succession entre tâches (localisation temporelle relative: une tâche ne peut commencer avant l'achèvement d'autres tâches) (2) contraintes de type disjonctif : [ti , ti + di ] ∩ ∩ ∩ ∩ [ tj , tj + dj ] = ∅ ∅ ∅ ∅ - Deux tâches ne peuvent être réalisées simultanément (utilisation des mêmes moyens par exemple). On peut dans certains cas se ramener au type potentiel. (3) contraintes de type cumulatif : ( ) γ ik k i t t ≤ ∑ Γ ( ) - Difficiles à prendre en compte, elles proviennent de la limitation des moyens disponibles à un instant donné. Résoudre un problème d'ordonnancement consistera dans ces conditions à rechercher un ordonnancement (s'il existe) qui satisfasse les contraintes imposées et optimise un certain objectif. Ce dernier pourra par exemple être la durée totale de réalisation du projet, que l'on cherchera à minimiser. On ne traitera pas dans un premier temps les contraintes de moyens. Recherche Opérationnelle - Ordonnancement Yves Correc 26/02/2007 3–4 3.2. REPRÉSENTATION GRAPHIQUE On se propose de représenter graphiquement les tâches que l'on vient de définir, et si possible les contraintes correspondantes. La méthode la plus ancienne , la seule disponible avant 1960, est le planning à barres ou diagramme de Gantt (Henry Gantt 1917). Ce type de diagramme utilise deux échelles perpendiculaires de coordonnées: l'axe des abscisses pour le temps, et l'axe des ordonnées pour les différentes tâches. On représente alors chaque tâche par un segment de droite horizontal dont la longueur est proportionnelle à la durée de la tâche. Exemple : Soit un projet constitué de 4 tâches: A (durée 3 semaines) doit précéder B durée (2 semaines) et D (durée 6 semaines) non exclusives, ainsi que C (durée 3 semaines) qui suit B. durée 1 2 3 4 5 6 7 8 9 10 A B C D Cette représentation est très parlante pour figurer l'état d'avancement d'un projet (en rouge) par rapport aux prévisions (en gris). Mais elle est limitée aux petits projets et ne permet pas de traduire convenablement les contraintes existant entre tâches. Enfin les renseignements véritablement intéressants sont les dates effectives ti de début des tâches, ainsi que les éventuelles marges disponibles sur certaines d'entre elles (pour répondre à la question de savoir si un retard sur une tâche particulière peut se répercuter à l'ensemble du projet, ou non). C'est pourquoi sont apparues des méthodes plus modernes basées sur la théorie des graphes. Méthode américaine (PERT) La méthode américaine PERT (Program Evaluation and Review Technique, 1959) développée pour l'US Navy par Malcom, Roseboom, Clark et Fazar, a permis un gain de temps de 2 à 3 ans sur le développement du programme de missiles Polaris. A la même époque, Walker et Kelley mettaient au point pour DuPont la méthode CPM (Critical Path Method, 1959), analogue à la précédente sauf sur certains points de détail. On ne distinguera pas, dans la suite, ces deux méthodes regroupées sous le vocable de "méthode américaine". Ce sont en fait des extensions du diagramme de Gantt, obtenues en construisant un graphe dont les arcs correspondent aux segments du diagramme, et les sommets aux étapes de la réalisation, c'est à dire à la fin de certaines tâches et au début d'autres: S'il est dit qu'une tâche doit en précéder deux autres, les arcs associés seront adjacents, et partageront un tel sommet qui sera l'étape "fin de la première tâche et début de la seconde et de la troisième". étape i-jk tache j tache i tache k Ce type de représentation du projet, sous la forme d'un graphe dont les arcs représentent les tâches et les sommets des étapes, est appelée "potentiel - étape" , par analogie avec un réseau électrique dont les nœuds sont portés à un certain potentiel (qui dans le cas présent est en fait le temps). Recherche Opérationnelle - Ordonnancement Yves Correc 26/02/2007 3–5 On poursuivra l'exemple précédent, en construisant ce graphe à partir du diagramme de Gantt. Pour cela on identifiera les nœuds-étapes (E1, E2, E3, E4, E5, FIN) avec les jonctions des segments du diagramme, pour obtenir le graphe suivant: durée 1 2 3 4 5 6 7 8 9 10 A B C D E3 E5 E1 E2 FIN E4 Chaque arc sera ensuite valué par la durée de la tâche qu'il représente. Il convient de souligner l'aspect relativement artificiel de cette construction, qui n'est pas toujours évidente à réaliser, et qui surtout supporte mal les modifications ultérieures du projet. On ne peut pratiquement traduire avec ce type de représentation que les contraintes de type potentiel. On obtient sur cet exemple le graphe suivant: E1 E2 E3 E5 E4 FIN A B D C 3 2 6 3 t1 t5 t3 t4 t2 Méthode française (MPM) Vers la même époque (1958), Bernard Roy introduisait la méthode des potentiels METRA (MPM), souvent appelée "méthode française", caractérisée par une représentation "potentiel – tâche", et utilisée pour la construction du paquebot France (1959). Chaque sommet du graphe représente ici une tâche, et chaque arc une contrainte de potentiel, c'est à dire une relation temporelle entre tâches. On affectera donc à chaque arc-contrainte sortant d'un sommet la durée de la tâche associée à ce sommet, pour répercuter vers la tâche extrémité de l'arc la contrainte correspondante (on doit avoir achevé cette tâche dont on donne la durée avant de pouvoir commencer la suivante). On pourra donc définir très simplement le graphe à partir de la liste des tâches, ce qui nous donne immédiatement les sommets, et du dictionnaire des précédents qui est la traduction directe des relations d'antériorité entre tâches (au contraire de la méthode américaine dont la gymnastique de construction des sommets –E1, E2, E3, E4 sur l'exemple précédent- auxquels vont être connectés les arcs-tâches n'est pas toujours évidente). Recherche Opérationnelle - Ordonnancement Yves Correc 26/02/2007 3–6 On introduira dans les deux cas un sommet "début de projet" noté α α α α, et un sommet "fin de projet" noté ω. L'application de la méthode française "potentiel-tâche" au même exemple donne le graphe suivant: α α α α A B C D ω 0 2 6 3 t-début tC tB tD tA t-fin 2 2 Cette méthode est donc beaucoup plus puissante que la méthode PERT pour le traitement des contraintes que l'on peut rencontrer. Elle permet en effet l'adjonction de nouvelles contraintes par simple adjonction d'arcs, sans remanier profondément le graphe. Le résultat de tout cela est qu'une évolution de la méthode MPM (PDM : Precedence Diagram Method, 1980) est aujourd'hui universellement utilisée, même si l'on parle souvent, par abus de langage, d'un "PERT", comme on dit un "frigidaire" au lieu d'un réfrigérateur… Nous détaillerons ces deux méthodes au moyen d'un exemple (construction d'un pavillon). Les travaux à réaliser, leur durée, et leurs précédents obligatoires (les autres travaux qui devront impérativement être achevés pour que la tâche considérée puisse commencer – typiquement on ne pourra débuter la couverture qu'après en avoir terminé avec la charpente, etc), sont résumés dans uploads/Management/ projets.pdf