Master SEMS – RCP104 – Optimisation en Informatique Fiche No2
ORDONNANCEMENT DE PROJET
EXERCICE 1
Un projet a été décomposé en 11 tâches. Ces tâches ont entre elles des contraintes de précédence
représentées par le tableau ci-dessous :
Tâches Durée Tâches préalables
A 4 -
B 6 A
C 2 2 jours après le début du projet
D 6 -
E 1 B
F 4 C
G 3 B et D
H 5 E et G
I 6 B et F
J 3 I et H
K 4 I et H
1. Tracer un graphe PERT (événement opération) relatif à ce projet.
2. Calculer les dates au plus tôt des événements.
3. Calculer les dates au plus tard des événements.
4. Calculer les marges libres des tâches.
5. Calculer les marges totales des tâches.
6. Quelles sont les tâches critiques ?
7. On suppose que lors de l’exécution du projet les deux tâches D et G ont été retardées
respectivement de 4 et 1 journées. Quelles sont les conséquences de ces retards sur le
déroulement du projet ?
EXERCICE 2
On désire déterminer l’ordonnancement optimal d’un projet dont les tâches, leurs durées et leurs
contraintes d’antériorité sont données dans Tableau 1.
1. Construire le graphe MPM associé à cet ordonnancement. Calculer la date au plus tôt ti et la
date au plus tard ∗ associées au début de la tâche i.
2. Calculer les marges totales des tâches. Donner les tâches et les chemins critiques.
3. Calculer les marges libres des tâches non critiques. La marge libre mi de l’activité i se calcule
de la manière suivante : mi min t j d ij t i
j successeur de i
où dij : temps d’attente imposé entre le début de i et le début de j (en général la durée de i).
4. La situation au début du 80ème jour, mise en évidence par un contrôle d’exécution, se
présente de la manière suivante :
• les tâches A et H sont terminées mais la tâche A a dû être prolongée de 5 jours ;
• les tâches E et F sont en cours (commencées respectivement depuis 30 et 5 jours) ;
• la tâche I ne pourra pas commencer avant la date 120.
Quelles conséquences ont ces retards sur les délais de réalisation ? Sur les chemins critiques ?
Tâches Durée (en Tâches préalables
jours)
A 70 -
B 15 -
C 25 ne peut commencer que 20 jours après le début de A
D 10 ne peut commencer que 50 jours après le début du projet
E 60 B et C
F 15 A et D
G 70 E
H 15 D
I 5 F
J 5 H et N
K 30 I et N
L 30 I et M
M 40 E et J
N 10 F
O 15 G, K, L
Tableau 1
EXERCICE 3
On considère un projet formé de 6 tâches élémentaires. Des coûts pour chacune des tâches sont
fixés en tenant compte des surcoûts liés aux raccourcissements possibles. Le tableau qui suit indique
leur durée, leurs contraintes d’antériorités et leurs coûts.
Tâches Tâches Durée Durée Coût Coût Coût
préalables normale crash normal Crash par jour de réduction
(en jours) (en jours)
A - 2 1 30 50 20
B - 2 2 30 30 0
C A 2 1 25 50 25
D A 4 2 60 80 10
E B,D 1 1 20 20 0
F D 2 1 20 50 30
1. Construire le graphe MPM associé à cet ordonnancement.
Calculer les dates au plus tôt et au plus tard des débuts des tâches.
2. Calculer les marges totales des activités.
3. Procéder étape par étape au raccourcissement du projet, en minimisant jour après jour les
surcoûts qui en résultent.
EXERCICE 4
On considère un projet formé de 6 activités élémentaires. Le tableau qui suit indique leur durée,
leurs contraintes d'antériorité et leur utilisation de ressources par jour.
Tâches Durée Tâches préalables Ressources
nécessaires par jour
A 2 - 2
B 2 - 2
C 2 A 4
D 4 A 6
E 1 B, D 1
F 2 D 2
1. Calculer les dates au plus tôt et au plus tard des débuts des tâches.
2. Calculer les marges totales des activités.
3. Donner le diagramme de GANTT "calé à gauche" de l'ordonnancement.
4. Préciser, pour l'ordonnancement au plus tôt, la courbe donnant l'histogramme des
ressources utilisées en fonction du temps.
5. Proposez des dates d'ordonnancement des tâches, respectant la durée minimale du projet
avec un histogrammes des ressources "plus équilibré".
EXERCICE 5
Un contrat a été signé pour un projet informatique à réaliser dans une durée maximale de 13 mois.
Ce projet a été décomposé en tâches confiées à des ingénieurs. Ces tâches ont entre elles des
contraintes de précédence représentées par le tableau ci-dessous. Ce tableau indique également la
durée prévue des tâches ainsi que le nombre des ingénieurs qui doivent être affectés à chaque
tâche.
Tâches Durée en mois Tâches préalables Nombre d’ingénieurs
A 3 - 8
B 8 A 4
C 5 A 4
D 1 C, G 2
E 4 D 6
F 2 C 6
G 6 - 4
1) En faisant abstraction du nombre d'ingénieurs disponibles :
a. Donnez la durée minimale du projet dans le meilleur des cas en appliquant la
méthode du graphe potentiel-tâches (méthode MPM de B. ROY) directement sur le
graphe. Indiquez les dates de début au plus tôt et au plus tard de chacune des tâches.
Précisez les tâches critiques.
b. Calculez les marges totales et marges libres des tâches B, C et G.
2) En réalité, la société ne dispose que de 12 ingénieurs pour ce projet :
a. En appliquant la méthode "sérielle", dans laquelle on donne la priorité à la tâche
disponible de plus petite date au plus tard, peut-on obtenir une solution qui respecte
le délai du contrat (13 mois) ? Illustrer la solution par un diagramme de GANTT (en
abscisse le temps, en ordonnée le nombre d'ingénieurs). Résumez clairement la
solution donnée par la méthode sérielle en indiquant pour chaque tâche sa date de
début.
b. Donnez la solution obtenue en appliquant la méthode sérielle uniquement sur les
tâches non critiques, après avoir placé les tâches critiques de telle sorte qu'elles
débutent à leur date au plus tôt. Comparez la solution ainsi obtenue à la
précédente. Que peut-on en conclure ?
