1.1.

INITIATION À LA THÉORIE DES GRAPHES 11

Remarque 1.1.7 Si xi est de niveau p ̸= 0, i.e. r(xi ) = p, p est le nombre d’arcs du plus long chemin
joignant un sommet de niveau 0 au sommet xi .

Dans l’exemple 1.1.8 précédent,

• Niveau 0 :
7 et 5 n’ont pas de précédent, r(5) = r(7) = 0.
• Niveau 1 :
. r(3) = 1, le seul chemin de longueur 1 joignant 7 ou 5 à 3 est (7, 3).
. r(6) = 1, il y a deux chemins de longueur 1 (donc contenant un seul arc) ayant pour extrémité 6 à
savoir (7, 6) et (5, 6).
. r(8) = 1, le seul chemin de longueur 1 joignant 7 ou 5 à 8 est (5, 8).
• Niveau 2 :
. r(1) = 2, les chemins (7, 3, 1), (7, 1), (7, 6, 1) et (5, 6, 1) sont constitués d’un ou deux arcs.
. r(4) = 2, les chemins (5, 4) et (7, 3, 4) sont consitués d’un ou deux arcs.
• Niveau 3 :
On a r(2) = 3. Les chemins transformant 5 ou 7 en 2 sont (7, 3, 1, 2), (7, 3, 4, 2), (7, 1, 2), (7, 6, 1, 2),
(5, 8, 2), (5, 4, 2) et (6, 5, 1, 2) et sont constitués de deux ou trois arcs.

Définition 1.1.2 Si r(xi ) = p ̸= 0, p est le nombre maximum d’arcs d’un chemin d’origine un sommet de
niveau 0, d’extrémité ce point xi .

1.1.4 Exercices
 
Exercice
 2  Huit entrepôts reliés par un réseau routier, sont mis à contribution pour fabriquer un produit
A. Le tableau ci-dessous indique les routes menant à chacun de ces entrepôts.

XXX
XXX Arrivée
XX A B C D E F G H
Départ XXX

A ⋆ ⋆
B ⋆
C ⋆
D ⋆ ⋆
E
F ⋆ ⋆ ⋆
G ⋆
H ⋆ ⋆

1. Établir le dictionnaire des précédents puis le dictionnaire des suivants des sommets du graphe.
2. Utiliser le dictionnaire des précédents pour ordonnancer le graphe par niveaux.
3. Représenter le graphe sous sa forme ordonnancée.
 12 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES

 
Exercice 3  On considère le graphe ci-dessous :

Figure 1.14 – Diagramme sagittal - Exercice 3

1. Montrer que le graphe admet des circuits tout en les précisant. Qu’est-ce que cela implique sur l’or-
donnancement par niveaux de ce graphe ?
2. On élimine l’arc (A, G)
(a) Déterminer le dictionnaire des précédents et des suivants de chacun des sommets du graphe.
(b) Ordonnancer le graphe par niveaux.
 
Exercice
 4  On se donne la relation binaire définie par l’ensemble de sommets E = {A, B, C, D, E, F }
et le graphe

G = {(A, B); (A, D); (A, F ); (B, D); (C, A); (C, D); (C, E); (D, E); (F, C); (F, E)}.

1. Caractériser cette relation binaire par

(a) sa représentation sagittale,
(b) sa représentation cartésienne,
(c) sa matrice booléenne.
2. Est-il possible selon vous, d’ordonnancer le graphe par niveaux et pourquoi ?
3. On élimine l’arc (A, F ).
(a) Déterminer le dictionnaire des précédents et des suivants de chacun des sommets du graphe.
(b) Ordonnancer le graphe par niveaux.
 
Exercice
 5 
1. Proposez un exemple de graphe contenant 4 sommets, une boucle, un circuit constitué d’au moins
trois arcs et un chemin hamiltonien. Voux exprimerez ce graphe sous la forme G = (X, R) où X est
l’ensemble constitué des sommets du graphe et R est la relation binaire définie sur X.
2. Caractérisez ce graphe par
(a) sa relation sagittale,
(b) sa représentation cartésienne,
(c) sa matrice booléenne,
(d) son dictionnaire des précédents,
(e) son dictionnaire des suivants.
 1.3. EXERCICES RÉCAPITULATIFS 21

on verra que l’établissement du planning relatif à la réalisation d’une tâche conduit à considérer
un graphe dans lequel tout arc (xi , xj ) représente une opération, auquel on associe le nombre vij
représentant la durée de l’opération. Tout sommet traduit la fin d’une opération. L’extrémité d’un arc
coı̈ncide avec l’origine d’un autre si et seulement si l’opération associée au premier est achevée afin
que celle associée au second puisse débuter. La durée totale de réalisation d’un programme ne peut
être inférieure à la somme des durées prises sur le chemin le plus défavorable depuis le sommet x0
début des travaux jusqu’au sommet xn fin des travaux, c’est-à-dire les chemins de longueur maximale
de x0 à xn . Un tel chemin est un chemin critique. Pour que la durée de l’opération soit minimale,
il est nécessaire que sur ce chemin critique, lorsque deux opérations se suivent, la deuxième débute
exactement lorsque la première se termine.

1.3 Exercices récapitulatifs

 
Exercice 6  La réalisation d’un chantier nécessite la réalisation des opérations ci-dessous

Opérations A B C D E F G H I J K L
Durée en semaines 32 13 4 3 6 32 20 8 13 38 42 39

D’autre part, on a constaté que l’opération B devait être précédée de l’opération A et suivie des opérations
C, D, E et F, que les opérations C et D devaient précéder l’opération G, que les opérations H et J, enfin,
devaient suivre les opérations E, F et G et précéder les opérations I, K et L.
Déterminer la durée minimale du projet.
 
Exercice 7  Une entreprise connaı̂t une croissance importante créant de gros besoins en locaux de construc-
tion et aussi de stockage. Il en résulte une grande dispersion des différents bâtiments. Le tableau ci-dessous
indique le temps en minutes que mettent les navettes pour joindre les différents points :

XXX
XXX Arrivée
XXX A B C D E F G H I J
Départ XX
A 36 20 30 16 18
B 24 16
C 28
D 16
E 14 18 26 28
F 10 12
G 8
H 4
I 12
J

1. Etablir le dictionnaire des précédents

2. (a) Ordonnancer le graphe par niveaux
(b) Représenter le graphe
 22 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES

3. Quel est le chemin que doit emprunter un employé désirant se rendre du point A au point J en un
temps minimal ? Quel est ce temps ?

 
Exercice 8 

1. En utilisant l’algorithme de Ford, déterminez le chemin minimal allant de x1 à x10 et précisez la

longueur de ce chemin. Interprétez le résultat de la question précédente dans un contexte d’entreprise
que vous inventerez.
2. En utilisant l’algorithme de Ford, déterminez le chemin maximal allant de x1 à x10 et précisez la
longueur de ce chemin. Interprétez le résultat de la question précédente dans un contexte d’entreprise
que vous inventerez.

 
Exercice
 9  Une entreprise de transport SUISSEXPORT dont le siège est situé à Berne doit effectuer
de fréquentes livraisons à Milan, en dehors de la période hivernale. Ses véhicules doivent donc traverser le
massif des Alpes : leur gabarit interdit l’usage des tunnels ferroviaires (Simplon, Saint-Gothard, Lötsch-
berg,. . . ) qui, sinon, faciliteraient le voyage.
Vus la fréquence et le coût de ces livraisons, l’entreprise désire déterminer l’itinéraire le plus court de Berne
à Milan.

On a orienté les tronçons de route et porté les distances en kilomètres.

À l’aide d’un graphe que vous aurez tracé, déterminer l’itinéraire demandé et préciser son kilométrage.
 1.3. EXERCICES RÉCAPITULATIFS 23

 
Exercice 10  On se donne le réseau routier ci-dessous où chaque sommet représente un entrepôt et chaque
arc, une route entre deux entrepôts ; chaque route est supposée à sens unique, le sens de progression étant
indiqué par la direction de l’arc.

1. Le premier problème est le suivant : tous les matins, plusieurs chauffeurs doivent acheminer le courrier
interne et les colis aux différents entrepôts de l’entreprise. On suppose que le centre de tri est l’entrepôt
B, c’est donc le point de départ des navettes.

(a) Sachant qu’une même navette ne peut emprunter deux fois le même arc (ce qui est permis pour
deux navettes différentes), combien faut-il de chauffeurs au minimum pour acheminer à chaque
entrepôt son courrier ? (certains arcs peuvent ne pas être parcourus.)

(b) En supposant que chaque route soit longue de 100 mètres, quelle distance totale parcourent
chaque matin les navettes ?

(c) Quel chemin emprunte la navette qui dessert le maximum d’entrepôts ?

2. Le second problème s’énonce comme suit : on se donne ci-dessous, pour chaque entrepôt, le temps
moyen (en minutes) nécessaire à la livraison du courrier (trajet et/ou déchargement) des entrepôts
suivants :

Entrepôt i A B C D E F G H I J K
Temps t(i) 5 6 3 8 4 5 6 20 4 4 9

Par exemple, une fois le courrier livré en A, il faut 5 minutes pour livrer le ou les entrepôts suivants.
Déterminer la durée minimale moyenne de livraison du courrier dans cette entreprise.

 
Exercice
 11  Une entreprise contacte votre société d’entreposage pour stocker des produits alimentaires.
Vos différents entrepôts sont localisés géographiquement à l’aide de la carte fournie ci-après.
24 CHAPITRE 1. QUELQUES RAPPELS SUR LES GRAPHES

Dans le cadre du contrat, l’entreprise vous demande de déterminer les chemins minimaux et maximaux du
réseau afin d’optimiser les prix de transport de leurs marchandises.

Les entrepôts sont schématisés par des points et les routes reliant ces différents entrepôts par des droites.
On supposera que les routes sont à sens unique, leur direction étant indiquée par les arcs orientés.

La valuation de chaque arc indique la distance séparant les entrepôts reliés par cet arc. Par exemple, les
entrepôts G et F sont distants de 160 mètres.
1. Établir le dictionnaire des précédents puis le dictionnaire des suivants des sommets du graphe.
2. Utiliser le dictionnaire des précédents pour ordonnancer le graphe par niveaux.
3. Représenter le graphe sous sa forme ordonnancée.
On précise que les entrepôts d’entrée sont ceux appartenant au niveau N0 et que les entrepôts de sortie sont
ceux appartenant au dernier niveau.

4. Déterminer la longueur du chemin minimal menant d’un entrepôt d’entrée à un entrepôt de sortie
tout en précisant ce chemin.
5. Déterminer la longueur du chemin maximal menant d’un entrepôt d’entrée à un entrepôt de sortie
tout en précisant ce chemin.
 26 CHAPITRE 2. PROBLÈMES D’ORDONNANCEMENT

2.3 Méthode d’ordonnancement

C’est un ensemble de méthodes qui permettent au responsable du projet de prendre les décisions
nécessaires dans les meilleures conditions possibles. Un problème d’ordonnancement est donc un problème
d’organisation du projet. On distingue différentes méthodes :
– Les méthodes du type diagramme de Gantt.
– La méthode PERT (Program Evaluation and Review Technique) mise en place pour la réalisation du
programme de recherche et de construction des fusées Polaris en 1958.
– La méthode CPM (Critical Path Method).
– La méthode MPM (Méthode des Potentiels Métra) mise au point en France par B. Roy et son équipe
de la SEMA. Cette méthode présente des avantages par rapport à la méthode américaine PERT, les
graphiques étant plus simples à élaborer et le développement plus prometteur. Son utilisation est très
importante dans la construction d’immeubles, de barrages, d’autoroutes,...

2.4 Établissement d’un ordonnancement

Dès que les contraintes sont compatibles, le critère principal est la minimisation de la durée totale de
réalisation des travaux.

2.5 Détermination du chemin critique et énumération des tâches cri-

tiques
Les tâches critiques sont celles dont l’exécution ne peut être ni retardée ni ralentie sans que la durée
totale des travaux ne soit augmentée. Le (ou les) chemin(s) critique(s) visualise(nt) l’ensemble des tâches
critiques sur le graphique de l’ordonnancement.

2.6 Exercices
 
Exercice 12  Votre société a besoin de vos services pour implanter la zone de stockage d’un entrepôt
qu’elle vient d’acquérir. Vous prenez connaissance des différentes tâches qu’il faudra réaliser :

Code des tâches Description des tâches Durée

A Livraison des racks 1h

B Rangement dans les palettiers 12h
C Réception des marchandises 3h
D Identification des emplacements 6h
E Mise en service du matériel de manutention 1h
F Réception du matériel de manutention 1h
G Commande des racks 1h
H Commande des chariots 1h
I Installation des racks 15h
J Acceptation du projet 2h

Votre mission (si vous l’acceptez) est d’optimiser l’aménagement de l’entrepôt

1. Etablir le tableau des antériorités (ou dictionnaire des précédents).
 2.6. EXERCICES 27

2. Vérifier qu’il n’y a pas de circuit dans le graphe défini par le dictionnaire de la question précédente.
3. Ordonnancer les tâches du graphe par niveaux.
4. Visualiser les différentes tâches à accomplir.
5. Evaluer la durée totale du projet.
 
Exercice 13  Votre société désire faire construire un nouvel entrepôt commercial dont vous devez réaliser
la mise en chantier. Vous prenez connaissance des différentes tâches qu’il faudra réaliser :

Code des tâches Description des tâches Durée

A Préparation du terrain 2 semaines

B Creusement des fondations 1 semaine
C Commande des matériaux 1 semaine
D Commande des portes et fenêtres 2 semaines
E Livraison des matériaux 1 semaine
F Coulage des fondations, de la dalle et des quais 2 semaines
G Livraison des portes et fenêtres 9 semaines
H Pose des murs, de la charpente et du toit 8 semaines
I Mise en place des portes et fenêtres 1 semaine

Votre mission (si vous l’acceptez) est d’optimiser la mise en chantier de l’entrepôt
1. Etablir le tableau des antériorités (ou dictionnaire des précédents).
2. Vérifier qu’il n’y a pas de circuit dans le graphe défini par le dictionnaire de la question précédente.
3. Ordonnancer les tâches du graphe par niveaux.
4. Visualiser les différentes tâches à accomplir.
5. Evaluer la durée totale du projet.
 3.7. EXERCICES 45

Tâches A B C D E F G H I J K L M N
Tâches
immédiatement D B,H A A D B,D,F B,I,E D,E F,G,H G,H H,I,E J,G K,J
antérieures
Durées 10 14 14 8 12 22 25 18 6 9 13 8 10 9

1. (a) Ordonnancer les tâches de ce projet par niveaux.

(b) Tracer le graphe.
(c) i. Donner une définition de la date de début au plus tôt.
ii. Déterminer les dates de début au plus tôt de chacune des tâches.
iii. En déduire la durée minimale du projet ainsi que le chemin critique.
(d) i. Donner une définition de la date de début au plus tard.
ii. Déterminer les dates de début au plus tard de chacune des tâches et retrouver ainsi les tâches
critiques.
(e) i. Donner les définitions de la marge totale et de la marge libre.
ii. Déterminer les marges totales et les marges libres de chacune des tâches du projet.
iii. On considère la tâche B , donner une interprétation des résultats obtenus.
(f) On démarre la tâche B à la date 24. Quelle en est l’influence sur la date de fin au plus tôt de la
tâche L ?

2. Afin de diminuer la durée minimale du projet, on propose à l’étudiant différentes améliorations, les
durées initiales des tâches ne sont pas modifiées mais certaines d’entre-elles peuvent commencer avant
l’achèvement des tâches précédentes.
* La tâche F peut commencer 4 jours après le début de D.
* La tâche G peut commencer 15 jours après le début de F et 10 jours après le début de B.
* La tâche H peut commencer 7 jours après le début de B et 2 jours après le début de I.
* La tâche K peut commencer 15 jours après le début de G et 12 jours après le début de H.
* La tâche N peut commencer 5 jours après le début de J.

Apporter ces différentes modifications au graphe.

 
Exercice
 16  Une entreprise souhaite augmenter sa capacité d’accueil de marchandises et commande pour
cela la construction d’un entrepôt spécialisé supplémentaire. La société responsable de ce projet dépêche un
spécialiste qui fournit la liste des tâches à réaliser et l’évaluation de leur durée. Les conditions d’antériorité
liant ces tâches et les durées en jours de celles-ci, sont données dans le tableau ci-dessous :

Tâches A B C D E F G H I J K L M N P
Tâches
immédiatement A B A A B,E A,D,E C,F F,H,K K E,F,G I,J D,G K,G,M J,M,N
antérieures
Durées 5 4 7 6 3 8 4 13 4 4 7 5 6 4 4

1. (a) Ordonnancer les tâches de ce projet par niveaux.

(b) Tracer le graphe.
 46 CHAPITRE 3. LA MÉTHODE MPM

2. (a) Déterminer les dates de début au plus tôt de chacune des tâches du projet en précisant pour une
tâche quelconque, la signification de cette date.
(b) En déduire la durée minimale du projet ainsi que le chemin critique.
(a) Déterminer les dates de début au plus tard de chacune des tâches en précisant pour une tâche
quelconque, la signification de cette date.
(b) Que peut-on déduire des tâches pour lesquelles les dates au plus tôt et au plus tard sont égales ?
3. (a) Déterminer les marges totales et les marges libres de chacune des tâches du projet.
(b) On démarre la tâche G quatre jours après sa date au plus tôt, que se passe-t-il alors ?

 
Exercice
 17  Vous travaillez actuellement sur un projet de construction d’un atelier de finition. Le début
des travaux est prévu pour le 1er mai. Le détail et le durée des travaux de chaque corps de métier vous sont
donnés ci-après. Afin de déterminer la date d’achèvement de l’atelier et d’éviter les retards qui seraient dus
à l’imprévision, vous êtes chargés de visualiser le projet.

À partir du tableau des antériorités ci-après (donnant les tâches précédentes et antécédentes),
1. Trouver les tâches immédiatement antérieures à chaque tâche.
2. Ordonnancer les tâches du projet par niveaux.
3. Déterminer les dates au plus tôt de chacune des tâches du projet en précisant pour l’une d’entre-elles
le calcul réalisé. Quelle est la date au plus tôt de réalisation du projet ?
4. Faire apparaı̂tre sur le graphe le chemin critique. Que peut-on dire sur les tâches qui composent ce
chemin ?
5. Déterminer les dates au plus tard de chacune des tâches du projet en précisant pour l’une d’entre-elles
le calcul réalisé.
6. Déterminer pour chacune des tâches qui composent le projet sa marge totale et sa marge libre.

Durée Tâches
Symboles Tâches
(en semaines) antérieures

A Gros œuvre maçonnerie 12 −−

B Charpente 1 A
C Zinguerie 1 B
D Couverture 1 C
E Electricité 1ère étape 2 D
F Sanitaire 1ère étape 1 D
G Vitreries extérieures 1 D
H Plâtrerie 4 G
I Sanitaire 2ème étape 1 H
J Electricité 2ème étape 1 H
K Carrelage 6 I,J
L Volets roulants 1 I
M Menuiseries intérieures 2 L
N Serrurerie 1 L
 3.7. EXERCICES 47

Durée Tâches
Symboles Tâches
(en semaines) antérieures

O Peintures 5 N
P Electricité 3ème étape 1 O
Q Revêtements des sols 5 P
R Crépissage extérieur 3 O

 
Exercice
 18  L’entreprise où vous travaillez a reçu commande d’une nouvelle machine-outil très perfec-
tionnée. Le délai de livraison est absolument impératif. Vous êtes chargé(e) d’établir les prévisions de durée
de fabrication.

À partir du tableau des antériorités ci-dessous (donnant les tâches précédentes et antécédentes),
1. Trouver les tâches immédiatement antérieures à chaque tâche.
2. Ordonnancer les tâches du projet par niveaux.
3. Déterminer les dates au plus tôt de chacune des tâches du projet en précisant pour l’une d’entre-elles
le calcul réalisé. Quelle est la date au plus tôt de réalisation du projet ?
4. Faire apparaı̂tre sur le graphe le chemin critique. Que peut-on dire sur les tâches qui composent ce
chemin ?
5. Déterminer les dates au plus tard de chacune des tâches du projet en précisant pour l’une d’entre-elles
le calcul réalisé.
6. Déterminer pour chacune des tâches qui composent le projet sa marge totale et sa marge libre.

Durée Tâches
Symboles Tâches
(en mois) antérieures

A Fabrication de l’élément 1 3 −−
B Fabrication de l’élément 2 2 A
C Assemblage a des éléments 1 et 2 1 A,B
D Fabrication de l’élément 3 2 C
E Assemblage b (assemblage a avec l’élément 3) 2 C,D
Fabrication de l’élément 4 quand les
F 3 A,B
éléments 1 et 2 sont terminés
Fabrication de l’élément 5 en même temps
G 24 A
que la fabrication de l’élément 4
Fabrication de l’élément 6 quand la fabrication de
H 4 G
l’élément 5 est terminée
I Fabrication de l’élément 7 6 H
J Assemblage d des éléments 5 et 6 1 G,H
K Assemblage c (assemblage b avec l’élément 4) 2 E,F
L Assemblage e (assemblage c,d avec l’élément 7) 7 I,J,K
 48 CHAPITRE 3. LA MÉTHODE MPM

 
Exercice 19  Une importante société de magasins alimentaires à grande surface diversifie son activité
en créant des commerces dans de petites villes. La société crée le fonds de commerce qui est ensuite géré de
façon autonome par un commerçant franchisé.

La société réalise tout d’abord une étude d’implantation : étude de marché sur un certain rayon d’ac-
tion et choix de la localité où sera installé le commerce.

À partir du tableau des antériorités de la page suivante (donnant les tâches précédentes et antécédentes),

1. Trouver les tâches immédiatement antérieures à chaque tâche.

2. À l’aide du tableau 1, retrouver

– les niveaux de l’ordonnancement,
– les dates au plus tôt de chaque tâche ainsi que la date au plus tôt de réalisation du projet,
– le chemin critique (en soulignant les tâches en faisant partie).
3. À l’aide du tableau 2, retrouver
– les dates au plus tard de chaque tâche,
– le chemin critique (en soulignant les tâches en faisant partie).

Durée Tâches
Symb. Tâches
(jours ouvr.) antérieures

A Recherche d’un local 50 −−

B Recherche d’un franchisé 45 A
C Constitution du dossier bancaire du franchisé 15 A,B
Constitution du dossier à la Chambre de
D 10 A,B,C
Commerce pour les inscriptions obligatoires
E Formation du franchisé 30 B
F Aménagement, plâterie, peinture du magasin 20 A
G Réfection, façade, enseigne 25 A
H Equipement chambre froide et rayonnages 15 A,F
I Implantation du magasin (disposition des articles) 6 A,B,E,F,H
K Tirage en imprimerie des feuillets publicitaires 6 A,G
L Distribution des feuillets publicitaires 2 A,G,K
M Liste et envoi des invitations pour l’inauguration 6 A,B,D
N Inauguration du magasin 1 Toutes les autres
 3.7. EXERCICES 49

 
Exercice 20  On souhaite réaliser un projet dont les principales tâches sont données ci-dessous et pour
lesquelles on précise les suivants ainsi que la durée :

Étape No Nom de la tâche Suivant(s) Durée (jours)

Lancement du projet 1 2 0
2 Caractéristiques des charges 3, 4 5
3 Caractéristiques des flux entrants 8 4
Recueil des données
4 Caractéristiques des flux sortants 5, 8 4
5 Caractéristiques des commandes 8 4
6 Fonctionnalités générales 8 8
7 Contraintes diverses 8 3
8 Dimensionnement statique 10 7
9 Dimensionnement dynamique 10 8

Conception 10 Conception de 3 solutions 11 42

11 Implantations 12 14
12 Élaboration des dossiers techniques 13 10
13 Établissement des budgets 14 5
14 Comparaison des solutions 15 7
15 Choix de la meilleure solution 16 5
Fin du projet 16 – 0

1. Quelle est la condition nécessaire pour qu’un graphe quelconque puisse être ordonnancé par niveaux ?
Prouver que cette condition est vérifiée dans le cadre de l’exercice.

2. Ordonnancer les tâches par niveaux. Tracer le graphe associé.

3. On utilise dans les questions suivantes la méthode MPM.

(a) Indiquer les dates de début au plus tôt ainsi que les dates de début au plus tard de chaque tâche.

(b) En déduire le(s) chemin(s) critique(s) ainsi que la durée minimale du projet.

(c) Calculer les marges libres et les marges totales de toutes les tâches. Donner la signification des
marges trouvées pour les tâches 3 et 13 uniquement.

 
Exercice
 21  La société Dupont S.A. spécialisée dans l’étude et la composition d’unités industrielles a
obtenu la maı̂trise d’œuvre pour l’installation d’une usine chimique. L’analyse du projet a permis de distin-
guer 14 phases de travaux différents : maçonnerie, plomberie, électricité, conditionnement d’air, traitement
des déchets, installations et essais machines, etc. Ces travaux sont désignés par les lettres de A à N.
La société responsable de cette implantation dispose de moyens (moyens propres en équipes spécialisées,
machines. . . auxquels s’ajoutent quelques sous-traitants) permettant l’exécution des travaux en parallèle,
sous réserve toutefois du respect des relations d’ordre montrées dans le tableau suivant. Ces relations sont
imposées par un ensemble de contraintes techniques.
Ce tableau montre également la durée prévue (en jours) de chacune des phases des travaux.
 50 CHAPITRE 3. LA MÉTHODE MPM

Liste des travaux Durée prévue (en jours) Travaux antérieurs Suivants Marge totale

A 10 – B,G,N 10
B 25 A C,K 10
C 25 B,E,G J 0
D 20 – G 0
E 35 – C,F,H,K 10
F 20 E,G J 5
G 25 A,D C,F,K 0
H 15 E J 20
I 40 – – 100
J 30 C,F,H L 0
K 20 B,E,G M 25
L 40 J,M – 0
M 10 K,N L 25
N 15 A M 65

1. Quelle est la durée (en jours ouvrés) minimale de réalisation de ce projet ? Indiquer la séquence des
travaux qui détermine cette durée (travaux critiques).
2. Déterminer la marge totale pour chacune des phases du projet.

 
Exercice 22  La société SGTB (Société des Grands Travaux de la Bièvre) a reçu la maı̂trise d’œuvre
de la construction d’une piscine olympique sur un campus universitaire. Le tableau des antériorités des
tâches est le suivant :

Codes Tâches Antériorités Durée (en jours) Suivants

A Excavation – 5 B,F
B Fondation A 2 C
C Pose de canalisations B 4 D
D Essais en pression C,G 8 E
E Etanchéité D 9 J
F Mise en place de la station d’épuration A 6 G
G Mise en place du chauffage F 5 D,H
H Raccordement électrique G 4 I
I Sonorisation sous-marine H 5 J
J Dallage E,I 6 K,L
K Construction des vestiaires J 8 M
L Construction du solarium J 2 M
M Mise en eau K,L 3 –
 3.7. EXERCICES 51

Les travaux débutent le 1er avril. Chaque mois comporte 20 jours ouvrables.
1. Déterminer si l’inauguration peut avoir lieu comme prévu le 15 juin.
2. Lors de la pose des canalisations, on apprend que, suite à un incident technique, cette opération durera
6 jours de plus que prévu. Cela aura-t-il une influence sur le délai prévu ?
 
Exercice
 23  Dans le cadre de la réforme hospitalière, les conseils d’administration de 3 centres hospi-
taliers voisins ont élaboré en commun un plan de rationnalisation de leurs activités. Tout en maintenant les
3 sites existants, ils ont décidé de fusionner en une seule entité appele HOPITAL NORD. La réorganisation
des unités de soins et de leur gestion implique l’interconnexion des réseaux informatiques des 3 sites. Deux
des 3 hôpitaux, désigns H1 et H2, sont déjà interconnectés ; vous participez à l’étude et à la mise en place
de la connexion du troisième hôpital, désigné H3.

L’évolution du réseau local du site H3 a été planifiée. Les tâches nécessaires à la réalisation de ce pro-
jet, leurs durées ainsi que les conditions d’antériorité qui les relient figurent dans le tableau ci-dessous :

Code de la tâche Désignation de la tâche Durée en jours Tâches antérieures Suivants

A Définition des contraintes du réseau 2 B,E J

B Mise en place du projet 6 – A
C Mise à jour des droits d’accès 2 F –
D Achat des composants matériels 8 J I,L
E Définition du budget 3 – A
F Mise à jour des groupes utilisateurs 2 K C
G Formation de l’administrateur réseau 5 J M
H Cablage 10 J M
I Commande de Novell Netware 5 4 D M
J Choix des fournisseurs et des intervenants 5 A D,G,H
K Mise à jour logicielle des postes clients 1 M F
L Mise à jour matérielle des postes 2 D M
M Installation Novell Netware 5 2 L,I,G,H K

1. Construire le graphe d’ordonnancement du projet.

2. Déterminer le chemin critique et indiquer la durée minimale de réalisation du projet.
3. Le responsable redoute maintenant des difficultés techniques sur la mise à jour matérielle des postes,
difficultés qui porteraient de 2 à 8 jours la durée de la tâche L. Indiquer l’incidence sur la durée globale
du projet d’allongement de la durée de la tâche L.