Ordonnancement ch3 [PDF]

Zitiervorschau

Chapitre 3 Ordonnancement de projets

1

C’est quoi l’ordonnancement de projet? (1) Il s’agit de réaliser un ensembles de tâches, ce travail nécessitant l’intervention de ressources disponible en nombre limité Les ressources considérées sont liées par des contraintes de précédence , et le critère à minimiser est la durée totale d’exécution du projet Le résultat se présente sous forme d’un diagramme de GANTT et de plan de charges des ressources.







2

C’est quoi l’ordonnancement de projet? (2) Les durées des tâches n’ont pas une valeur fixe. Elles découlent de l’estimation de la charge de travail nécessaire pour les réaliser (Une bonne méthode d’estimation des charges doit permettre d’approcher au mieux le temps nécessaire à la réalisation d’un projet, c’est-à-dire la durée la plus probable). Une durée dépend donc du nombre de personnes affectées à la tâche.  Un travail est non répétitif.  La durée est sensible aux aléas rencontrés durant le déroulement du projet.  Le critère à optimiser n’est pas toujours la durée.  La durée du projet peut être longue (plusieurs années) 

3

Méthodes d’ordonnancement de projet

GANTT Graphe potentiel tâche PERT



 

 

4

PERT - temps PERT – coût

La méthode GANTT (1) Méthode fort ancienne, datant de 1918 et pourtant très répandue. Elle consiste à déterminer la meilleure manière de positionner les différentes tâches d’un projet à exécuter, sur une période déterminée, en fonction:  Des durées de chacune des tâches  Des contraintes d’antériorité existant entre les différents tâches  Des délais à respecter  Des capacités de traitement 5

La méthode GANTT (2) Modes de gestion des priorités:  Priorité au produits ayant la date de livraison la plus proche;  Première commande confirmée, première commande exécutée;  Priorité à l’opération dont la durée est la plus courte;  Priorité à la tâche ayant la plus petite marge: Marge = temps restant jusqu’à la livraison – temps total d’achèvement du projet.

Priorité à la tâche ayant le ratio critique le plus faible:



Ratio critique = temps restant jusqu’à la livraison/somme des temps des opérations restant à effectuer.

6

La méthode GANTT (2) Le diagramme de Gantt permet de visualiser l’évolution d’un projet, et de déterminer la durée globale de sa réalisation. Le diagramme de GANTT se présente sous la forme d’un tableau quadrillé où chaque colonne correspond à une unité de temps et chaque ligne à une opération à réaliser. On définit une barre horizontale pour chaque tâche, la longueur de celle-ci correspondant à la durée de la tâche. La situation de la barre sur le graphique est en fonction des liens entre les différentes tâches.







7

La méthode GANTT (3) Un flottement: correspond au temps de retard qu’on peut prendre sur une tâche particulière sans pour autant augmenter la durée globale de réalisation du projet



8

La méthode GANTT (4)

Jalonnement au plus tôt: consiste à représenter les opérations en les faisant démarrer au plus tôt; Jalonnement au plus tard: consiste à représenter les opérations en les faisant démarrer au plus tard;

 

9

La méthode GANTT (5) Pour faire un jalonnement au plus tard :  on commence par positionner le plus tard possible la ou les tâches qui n’ont pas de successeurs, dans notre exemple, G ;  on positionne le plus tard possible la ou les tâches qui ont pour successeurs celles qu’on vient de représenter, dans notre exemple, D et F ;  et ainsi de suite jusqu’aux tâches qui n’ont pas d’antériorité. Dans notre exemple, à la suite de D et F, on représentera les tâches qui les ont pour successeurs, soit C, puis on représentera E, B et H et enfin A. 10

La méthode GANTT (7) 

Chevauchement:

la technique du chevauchement consiste à faire démarrer une opération alors que la précédente n’est pas terminée, ou à effectuer des opérations en parallèle, pour diminuer le temps global de réalisation du projet.

11

La méthode GANTT (8) Exercice (GANTT): La société G. Duval réalise une activité de décolletage de pièces pour l’industrie automobile. L’entreprise vient de recevoir une commande de 400 pièces qu’on appelle P001. Ces pièces doivent subir des opérations successives sur quatre postes de production : • le poste P1 dont la capacité est de 400 pièces à l’heure ; • le poste P2 dont la capacité est de 200 pièces à l’heure ; • le poste P3 dont la capacité est de 100 pièces à l’heure ; • le poste P4 dont la capacité est de 200 pièces à l’heure. L’entreprise souhaite ordonnancer sa production sous la forme d’un Gantt et se demande combien de temps il lui faut pour traiter la commande de 400 pièces P001. Sachant qu’on pourra effectuer au moins un transfert des lots de 100 pièces, déterminer l’ordonnancement optimale. 12

La méthode GANTT (9)

La production de notre lot de 400 P001 se termine au bout de 9 heures L’entreprise trouve que ce délai est trop long et se propose d’effectuer un chevauchement en coupant les lots de fabrication en quatre lots égaux. Cela va se traduire par un transfert au poste suivant toutes les 100 pièces.

13

La méthode GANTT (9)

Le projet se termine au bout de 5 heures et quart au lieu de 9 heures

14

PERT (1) 

PERT = Program Evaluation and Review Technique

•

C’est une méthode de gestion de projet et de planification

Elle a été développée aux états unis par la marine Américaine dans les années 1950 Domaine d’application: • Le P.E.R.T s’adapte à tout problème décomposable en activité elle-même soumises à des contraintes d’antériorités. De même, les ressources sont supposées disponibles, les durées des activités indépendantes" •

•

15

Domaines : construction d’immeubles, montage des fusées inter planaires, travaux administratifs, travaux industrielles, etc.…

PERT (2) Consiste à mettre en ordre un ensemble de tâches en utilisant un graphe orienté sans boucles dont :  Les arcs représentent les tâches, ils sont orientés dans le sens du déroulement du temps  Les sommets constituent des événement (Étapes de la réalisation des tâches), représentent les débuts et les fin de tâches  Les valuations des arcs sont les détails de l’exécution N.B: Les évènements particuliers O et F , représentent les instants de début et de fin des travaux 16

PERT (3) Date au plus tôt : θi désigne la date au plus tôt de l’événement Xi dij désigne la durée de l’opération (i, j) On a :   [i  dij  j

max

iu  ( j)

Date au plus tard : La date au plus tard de l’événement Xi est définie par : i si X i appartient à un chemin critique   i   [j  dij] sinon min    ju ( i ) 17

PERT (4) Chemin critique  Chemin critique est constitué par les événement (dits critiques) dont la date attendue est égale à la différence entre la date attendue de l’événement suivant (sur le chemin critique) et la valeur de l’arc qui les relie Marge libre m ij  j - (i  dij) Une réserve de temps dont on dispose sur une tâche qui permet si elle est consommée de ne pas tarder les dates au plus tôt des tâches ultérieures. 18

PERT (5) Marge totale

Mij  j  (i  d ij )

Une réserve de temps sur une tâche que si elle est consommée, l’opération (i,j) se termine à sa date au plus tard.

Tâche fictive 1

a 3

Soit les trois tâches suivantes: 2

c

4

b

Comment créer une tâche d qui n’a que b comme prédécesseur ? 19

PERT (6) a

1

b

2

a

1

c

3

c

3

5

d

4

6

4

N.B : La tâche fictive (5,3) a une durée d’exécution égale à 0 b

2

20

5

d

6

Exemple PERT Les opérations dans la construction d'un ensemble hydroélectrique : a) Construction des routes d'accès au site, b) Préparation des carrières et terrassements, c) Construction d'une cité pour le personnel, d) Commande du matériel hydraulique et électrique, e) Construction de la centrale, f) Construction du barrage et des digues, g) Construction des galeries et conduites forcées, h) Montage des machines, i) Essais. 21

Exemple PERT (suite)

22

Multi-PERT (1) La notion de réseau PERT correspond à la notion de gestion de projet. Quand le réseau d’ensemble de celui-ci devient trop complexe, on peut le diviser :  soit en un ensemble de sections qui seront organisées de manière indépendante ;  Soit en un ensemble de niveaux hiérarchiques qui seront eux aussi gérés indépendamment les uns des autres. On divise le projet en différentes sections organisées de manière indépendante, ce qui permet : au groupe de travail d’une section d’analyser et de modifier son propre réseau, indépendamment des autres; de connaître les responsables d’une avance ou d’un retard éventuel et d’engager leur responsabilité. 

23

Multi-PERT (2) Multi-PERT: Les réseaux à sections multiples Sous-réseau n’ayant qu’un seul événement de liaison

Sous réseau ayant deux événements de liaison

24

Multi-PERT (3) Multi-PERT: Les réseaux à niveaux multiples Multi-PERT à niveaux multiples

• Au niveau 1, une seule activité fait l’objet d’une mention particulière nécessitant l’accès à un réseau inférieur, celui de niveau 2. • Au niveau 2, une tâche fait l’objet d’une mention particulière nécessitant elle aussi l’accès à un réseau inférieur, celui de niveau 3. • Une fois le réseau 3 terminé, on remonte au niveau 2. • Une fois le réseau 2 terminé, on remonte au niveau 1 dont on termine l’exécution. 25

PERT à coût minimal (1) 

La durée de réalisation de certaines tâches peut être réduite, moyennant un coût qui est fonction de la réduction. Ex : la réduction est réalisée par des heures supplémentaires

Méthode PERT-coût : Le coût est proportionnel à la réduction de la durée. Objectif de PERT-coût: Définition du coût d’accélération de chaque tâche par unité de temps gagnée



26

PERT à coût minimal (2) La courbe des coûts d‘une tâche en fonction de sa durée a en général l‘allure suivante:

CA C CN

DA 27

DN

PERT à coût minimal (3) Chaque tâche du projet est caractérisée par:  Un coût normal CN  Une durée normale de réalisation DN  Une durée accélérée (crash duration) DA: la plus petite durée envisageable pour la réalisation de la tâche  Un coût accéléré CA(coût de réalisation pour la durée accélérée

28

PERT à coût minimal (4) Hypothèse de relation linéaire du coût par rapport au temps de réalisation : le coût décroit linéairement en fonction de temps.

Coût marginal (coût supplémentaire associé à la réduction de la durée de réalisation de la tâche): CM 

29

CA  CN DN  DA

PERT à coût minimal (5) Méthodologie proposée : 1. Etablir le réseau des activités normales 2. Sélectionner les tâches réductibles du chemin critique. 3. Classer les tâches par ordre croissant de coût marginal (CM). 4. Réduire sur les tâches les moins coûteuses. 5. Modifier le réseau PERT de nouveau. 6. Calculer la durée et le sur-coût. Remarque: L'existence de plusieurs chemins critiques impose d'opérer sur une activité de chaque chemin simultanément de telle sorte que la somme des coûts marginaux associés aux réductions soit minimisée parmi tous les choix possible 30

PERT à coût minimal (6) 

Exemple

Date de fin 16 31

PERT à coût minimal (7) Exemple (Itération 1) :  Il faut réduire la longueur d'un arc sur le chemin critique. La réduction de C est la plus faible. La suite des réductions est :  1 jour de C de coût 6  date de fin 15

32

PERT à coût minimal (8) Exemple (itération 2) :  Deux chemins critiques (A,D et A,C,E) : réduire une tâche qui appartient aux deux chemins, ou bien réduire plusieurs tâches différentes (une appartenant à chaque chemin) de coût le plus faible.  1 jour de D et C de coût 8  date de fin 14

33

PERT à coût minimal (9) Exemple (itération 3) :  Trois chemins critiques (A,D ; B,E et A,C,E) : réduire une tâche qui appartient aux trois chemins, ou bien réduire deux tâches différentes (une appartenant à chaque chemin) de coût le plus faible.  1 jour de A et E de coût 17  date de fin 13

34

PERT à coût minimal (10 Exemple (itération 4) :  Deux chemins critiques (A,D et B,E) : réduire une tâche qui appartient aux deux chemins, ou bien réduire deux tâches différentes (une appartenant à chaque chemin) de coût le plus faible.  1 jour de A et B de coût 19  date de fin 12

35

PERT à coût minimal (11) Exemple (itération 4) :

NB : aucune autre réduction n’est possible car on a réduit au maximum A et D qui représentent un chemin critique. La réduction de E et de C n’améliore pas la date de fin du projet.

36