Exercices résolus

1.

[Tiré de B. T. Smith, "Introduction à la théorie des graphes et des réseaux". Tome II,
Département de Génie industriel, École Polytechnique de Montréal, Sept. 1983.]

Considérons comme exemple d'un projet abordable par la technique PERT, une recette
de cuisine:
BEIGNETS D'ANANAS 1

1. Égouttez les tranches d'ananas. Épongez-les avec un papier absorbant. Mettez-les

dans un saladier avec le rhum et le sucre vanillé. Laisser macérer 1 heure.

2. Pâte à frire: mélangez au fouet électrique dans une grande terrine: farine, sel, jaune
d'oeuf, beurre fondu, bière et environ 1 verre d'eau tiède. Cette pâte doit être à
peine coulante. Ajoutez enfin le rhum et le blanc d'oeuf battu en neige. Laissez
reposer jusqu'à ce que les ananas aient fini de macérer.

3. Égouttez les tranches d'ananas et coupez-les en deux.

4. Trempez chaque morceau dans la pâte à frire, puis dans l'huile bouillante
(éventuellement, procédez à la poêle). Quand les beignets sont bien dorés,
égouttez-les sur un papier absorbant.

5. Poudrez de sucre à fruits pour présenter.

---------------------------------------------------

Mettre cette recette sous la forme d'un graphe sans cycle avec, à côté de chaque activité
(arc) un estimé de son temps d'exécution.

Dans cet exemple simple, la durée du projet (les beignets terminés) est estimée à 1 heure
30 minutes et celle-ci est la longueur du chemin le plus long entre le début du projet (le
sommet 1) et sa fin (le sommet 6).

1 Les Doigts d'Or Cuisine. Numéro 3, 1976.

 2
la macération
ajouter et trancher (1 hre )
l'ananas et mettre dans
un saladier ( 5 min. ) confection de
la pâte ( 15
min.) 3
1

égoutter et trancher
l'ananas ( 5 min .)

la cuisson ( 15 min. )

poudrer et sucrer ( 5 min. )

5 6

2. [NOBE 95, pp. 407 - 413]

Considérons un projet d'implantation de réseau micro-informatique, que nous appellerons

par la suite projet RESO, qui compte 3 phases successives.

- Phase 1: planification, c'est-à-dire évaluation initiale, prise en considération des

différentes approches possibles et analyse des coûts relatifs à chaque approche.
Cette phase se termine par l'approbation du budget nécessaire à la mise en œuvre
de l'approche retenue.

- Phase 2: mise en place du matériel, installation du logiciel puis formation du

personnel.

- Phase 3: élaboration des procédures pour assurer le fonctionnement adéquat du

réseau.
Chacune de ces phases se ramifie en plusieurs tâches, qui sont énumérées et décrites au
tableau 2.1. Notons que les serveurs mentionnés dans la tâche G sont des unités qui sont
les dépositaires des ressources communes (fichiers, imprimantes, etc.) et qui coordonnent
le trafic sur le réseau; que les ponts de la tâche K sont des unités qui assurent la liaison
entre différents serveurs ou différents réseaux. La durée prévue pour chaque tâche
apparaît à la dernière colonne du tableau.

L'avant-dernière colonne donne, pour chaque tâche, une liste de tâches dont le
parachèvement est nécessaire et suffisant à son démarrage. Par exemple, l'analyse des
coûts, tâche dénotée D, pourra démarrer dès que seront terminées les tâches B et C; mais
la structure du réseau et le plan de formation devront être complètement élaborés avant
que l'on puisse passer à l'analyse des coûts.

Code Description Prédécesseurs Durée

immédiats (en jours)

A Évaluation initiale - 5
B Élaboration de la structure du réseau A 10
C Élaboration du plan de formation du personnel A 3
D Analyse des coûts B, C 5
E Révision des plans et approbation du budget B, C, D 5
F Mise en place du câblage E 5
G Montage des serveurs F 5
H Montage des stations de travail G 3
I Installation du logiciel d'exploitation du réseau H 4
J Montage des lignes téléphoniques G 5
K Montage des ponts G 3
L Documentation de la structure du réseau I, J, K 5
M Formation du personnel L 8
N Négociation de la politique d'entretien H, J, K 2
O Élaboration des procédures d'exploitation L, N 5
P Élaboration des procédures de copies de sécurité O 5
Q Élaboration des procédures d'entretien et de réparation O 5

Tableau 2.1 - Implantation d'un réseau micro-informatique.

Le réseau complet est représenté à la figure 2.1. Puisque la tâche initiale A est
prédécesseur immédiat de B et de C, le tracé du réseau des tâches débute comme suit.
 3

1 A
2 4
C

L'analyse des coûts, tâche D, admet comme prédécesseurs immédiats les tâches B et C. Il
faudrait donc que B et C partagent le même sommet terminal.

En combinant les contraintes des 2 sous-réseaux, on pourrait conclure que les arcs B et C
ont le même sommet initial et le même sommet terminal. Bien que cette affirmation ne
comporte pas d'illogisme, la tradition et les conventions de codage utilisées dans les
logiciels de gestion de projets interdisent cette pratique. On ajoute entre les sommets 3 et
4 une tâche fictive F1, dont la durée est nulle comme celle de toute tâche fictive, pour
assurer que la tâche D, de sommet initial 4, démarre seulement lorsque B, tout comme C,
sont parachevées.

B F1

1 A
2 4 5
C D

E admet 3 prédécesseurs immédiats: B, C et D. Les 2 premiers sont redondants puisqu'ils

précèdent D; ce sont des prédécesseurs lointains de E. On pourrait les éliminer de la liste
des prédécesseurs immédiats de E sans que le tracé du réseau en soit modifié. La phase 1
de planification du réseau se traduit par le sous-réseau suivant.
 3

B F1

1 A 6
2 4 5 E
C D

La mise en place du câblage, tâche F, démarre du sommet 6 où aboutit E. Suit le montage

des serveurs, soit la tâche G. Trois tâches émanent du sommet terminal de G.

1 A-E
6 7 8 H
F G

J
K

On doit relier les sommets terminaux des arcs H, K et J par des tâches fictives, puisque
les tâches correspondantes admettent toutes la tâche N comme successeur immédiat.
Noter que I est successeur immédiat de la seule tâche H.

H I
1 8 10
A-G

K F3
J

9 11
F2 N

Une quatrième tâche fictive, F4, allant du sommet 11 au sommet terminal de I, assure
que la tâche de documentation, L, démarre après le parachèvement non seulement de I,
mais également de J et K. L'arc F5 dénote la tâche fictive, allant des sommets terminaux
de L et de N, qui garantit que l'élaboration des procédures d'exploitation, tâche O, ne
débutera qu'après le parachèvement de L et N. L'existence d'un successeur immédiat M,
propre à la seule tâche L, interdit de donner à L et à N un même sommet terminal.
 H I L M
1 8 10 12 13
A-G

K F3 F5
J F4
O
9 11 14
F2 N

Il reste à tracer les arcs P et Q. Leur sommet initial sera le sommet terminal de leur
prédécesseur immédiat commun O. Puis, on convient de donner aux arcs M, P et Q un
même sommet terminal, qui sera le sommet terminal du réseau. Cela exige l'introduction
d'une sixième tâche fictive F6.

3
F1
B
A D F G H I L
2 4 E 8 10 12 M 17
1 5 6 7 13
C
K F3 F5
J P
F4 F6

9 11 14 15 16
F2 N O Q

Figure 2.1 - Réseau pour le projet RESO.