Cours de Recherche Opérationnelle

 

Année 2002 - 2003

 

NOTIONS D’ORDONNANCEMENT

 

 

 

I. Notions de projet 2

II. Méthodes existantes 3

1. Méthode (diagramme) de GANTT_ 3

2. Méthode PERT_ 5

III. Exercice 7

IV. Résumé 9

1. PERT : 9

2. MPM : 9

3. GANT: 9

4. Informations complémentaires : 10

V. Chemin critique 11

VI. Exercice « construction d’une maison »_ 12

Tâches 12

Désignation Tâche_ 12

Durée_ 12

Prédécesseurs 12

 


 

I. Notions de projet

 

 

Notion de projet : (différence entre planification et gestion de projet)

- ensemble de tâches               la notion de tâche est relative

                                                           la notion de projet est relative

 

            Sur un projet, ne jamais descendre sur une tâche inférieure à 15 jours.

 

 

 

 

Projet :

            Projet = ensemble de tâche ayant pour but l’obtention des objectifs coût performances délais.

 

 

 

 

 

 

 

 

 

 

 

 


Contraintes :

-         Potentielle :

Ø préséance (exemple : une tâche B ne peut commencer que si la tâche V est terminée)

Ø localisation temporelle : contrainte par rapport aux dates (exemple : une tâche A doit commencer à une date donnée (1/1/96))

-         Disjonctives

Exemple : la machine A ne doit pas fonctionner en même temps que la tâche B

-         Cumulatives

 


 

II. Méthodes existantes

 

 

            Ï Méthode de GANTT

 

 

 

 

 

 


            Remplacée par la méthode CPM (Critical Method Path) et la méthode PERT (1958).

 

 

 

            Ï Méthode PERT

 

            Ordonnancer, calculer des délais de fin de projet, des marges (latitudes).

                        Þ création d’un schéma

                        Þ nécessite la création de chose abstraite

                        Þ création de tâche inexistante dans le projet

 

 

 

            Ï Méthode MPM     

 

            Méthode Potentiels Metna (Bernard Roy)

 

 

1. Méthode (diagramme) de GANTT

 

 

Objectifs :

mettre en évidence les durées des tâches et leurs posItionnements relatifs.

 

 

Avantages :

-         extrêmement compréhensible par tous

-         permet de suivre le déroulement des opérations dans le temps

-         permet une certaine synthèse de l’ensemble du projet

 

 

Inconvénients :

-         ne prend pas en compte les contraintes

-         ne permet pas de connaître le chemin critique

-         difficulté de remise à jour (pour les systèmes manuels)

 

Variante existant entre PERT/GANTT

Gestion atelier

 

Gestion de projet

 
 

 

 

 

 

 

 

 

GANTT

 

PERT/GANTT

 
 

 


Tâches

Durées prévues

Tâche précédente

Durée planifiée

Durée réalisée

A

4 mois 4

 

4

4

B

2 mois 3

A

2

 

C

3 mois 2

B

3

 

D

5 mois 5

C

5

 

E

6 mois 7

C

6

 

F

1 mois 2

A

1

 

 


Légende :

normal = tableau à l’état initial

souligné = valeurs prévues dans le planifié

italique = version 2 de la planification

 

 

 

Planifié

 

Réalisé

 

Réactualisé

 

 


Tps en mois

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

A

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

B

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

C

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

D

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

E

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

F

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Tps en mois

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

A

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

B

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

C

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

D

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

E

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

F

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Tps en mois

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

A

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

B

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

C

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

D

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

E

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

F

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Méthode PERT

 

 

Objectif :

Mettre en évidence les différentes liaisons du projet, c’est à dire des tâches entre elles. (nécessité de la méthode : Graphe)

 

 

Structure :

Bâtir :

-           le graphe correspondant aux tâches et à leurs contraintes

-           observer le chemin critique

-           notion de temps rattachés à chaque tâche

 

 

Construction d’un réseau PERT :

            Règles :

1.      tâche représentée par un arc O à O

2.      deux tâches successives sont représentées par deux flèches successives

O à O à O ; O représente l’étape initiale A

3.      le graphe doit avoir une seule entrée

4.      le graphe doit avoir une seule sortie

5.      le graphe se comporte comme une boucle

6.      chaque étape est référencée par un numéro

 

 

Remarques :

Tâche fictive :

-           tâche nécessaire pour représenter les contraintes du projet

-           elles ont pour valeur 0

-           elles sont souvent en pointillés

 

 

Exemple :

            ð L succède à J ; K succède à I [ et à J ]

J

 

L

 
 

 

I

 

K

 
 

 

 

 

 

 


J

 
            ð I et J fonctionne en parallèle

I

 
 

 

 

 

 

 

 


Autres notions :

Chemin critique : chemin tel que toute augmentation de la durée d’une tâche retarde d’autant la fin du projet. Intervalle de flottement nul.

 

 

Date au plus tôt et date au plus tard :

 


Tâches

A

B

C

D

Précédant

 

A

A

BC

 

 

 

 

 

Intervalle de flottement et marges :

 

 

 

 

 

 

 


Evénement Ej

 

Evénement Ei

 
Marges :

 

 

 

 

 

 

 

 

 


Marges libres de Tij          : ML(Tij) = tj – ti - dij

Marges totale  Tij             : MT(Tij) = t’j – ti – dij

Marges certaine  Tij          : MC(Tij) = tj – t’i - dij

 

Marge libre d’une tâche : durée de flottement ou retard maximal de la tâche, sans perturber la date au plutôt de l’événement suivant.

Marge totale : durée de flottement ou retard maximal sans perturber la date de fin de projet.

 

 

Mise au point et gestion d’un PERT :

1.      recueil des informations :

-      les tâches

-      les implications des tâches

-      les durées de chacune d’elles

-     

2.      feuillets de remise à jour + procédure

3.      dépouiller

4.      traiter, analyser

5.      interprétations éventuelles

6.      responsabilité + actions correctives

 

III. Exercice

 

            Réalisation d’un ouvrage.

            Les tâches A, B, C, D, E, F, G, H

                        Les durées (en jours) : A = 2, B = 4, C = 4, D = 2, E = 6, F = 2, G = 4, H = 1

                        Les contraintes :

Tâches

A

B

C

D

E

F

G

H

Précédant

 

 

A

B

A

C D

B

F G

 

1.      construction d’un réseau PERT

 

 

 

 

 

 

 


 


            Un événement (par exemple) = contrat signet

 

Tâches

Précédant

B

A

D

A C

 

 

NON

 

OUI

 

A

 

B

 

C

 

D

 

A

 

B

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


            Limite : on aurait tendance à créer trop de tâche fictive pour simplifier le graphe.

 

 

2.      Calcul des dates au plutôt : tj = Max. {ti + dij}

 

 

3.      calcul des dates au plus tard : inverser le graphe, c’est à dire

-      l’entré devient l’événement de sortie

-      la sortie devient l’événement d’entrée

-      inverser les flèches

 


 

IV. Résumé

Un événement, rendez-vous technique

 
1. PERT :

 

 

 

 

 

 

 

 

 

 

 

 

 

 


                        Intérêt : fixer une date

                        Variante : la longueur de la tâche proportionnelle à la durée de la tâche ® visuelle

Lien de dépendance

 
2. MPM :

 

Tâche, forme indépendante de la durée de la tâche

 
 

 

 

 

 

 

 

 

 


3. GANT:

Tâche

 
 

 

Tâche

 

Temps

 
 

 

 

 

 

 

 

 

 

 

 

 

 


4. Informations complémentaires :

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

X démarre après C et D

 
 

 

 

 

 

 

 

 

 

 

 

 

 

X démarre après C et D

F démarre après D

 
 

 

 

 

 

 

 

 

 

 

 



 

V. Chemin critique

 

Chemin critique : « CHEMIN LE PLUS LONG, DUREE MAXIMALE DU PROJET »

 

 

1.      A partir du PERT

 

 

 

 

 

 

 

 


                                               Chemin critique ® DD +tôt = DD +tard

 

 

 

2.      A partir du MPM

 

 

 

 

 

 

 


                                               Chemin critique ® DD +tôt = DD +tard

 

 

3.      A partir du CALCUL DES MARGES LIBRES POUR CHAQUE TACHE

 

MTi = DF +tard – DD +tôt – DTi

Tâche critique si marge libre = 0

 

DD +tôt

 

DD +tard

 
 

 

 

 

 

 

 

 

 


4.      A partir du TABLEAU DES POTENTIELS

 

Chemin critique = les tâches n’ayant aucune « marge libre »


 

VI. Exercice « construction d’une maison »

 

 

1.      Enumérer les différentes tâches

2.      Tracer le tableau des tâches préalables

 

Tâches

Désignation Tâche

Durée

Prédécesseurs

A 1

Cmd et livraison câblage

3

 

B 2

Pose câblage

4

A,I

C 3

Inspection câblage

1

B

D 4

Cmd et livraison mat plomberie

4

 

E 5

Travaux plomberie extérieure

2

D : Redondant avec E

 
H,D

F 6

Travaux plomberie extérieure

5

I,D,E

G 7

Terrassement

1

 

H 8

Fondation

3

G

I 9

Construction ossature

5

H

J 10

Cmd et livraison brique

6

 

K 11

Briquetage

3

J,I

L 12

Cmd et livraison tuile

14

 

M 13

Construction charpente

2

I

N 14

Pose couverture

2

M,L

O 15

Revêtement intérieur

3

M,C,F

P 16

Aménagement intérieur

3

N,O

Q 17

Inspection générale

2

P,S

R 18

Nettoyage extérieur

1

N,K,O

S 19

Aménagement extérieur

3

R