146
Recherche opérationnelle
Sur l'exemple étudié, le calcul des marges libres et des marges totales donne :
A B C
D E F
G H
I
J
K L M N O
marge
libre
0
0
0
0
0
0
0
6
0
0
1
0
0
0
9
marge
totale
0
0
5
5
9
3
3
6
0
1
1
0
0
0
9
Le tableau suivant donne le résumé des notions introduites ci-dessus.
6.4.2.5. Modification des contraintes.
Il peut se faire qu'un problème d'ordonnancement évolue dans le temps, par suite de
modifications dans les données. Prenons par exemple le cas simple que nous avons
étudié dans les paragraphes précédents et supposons que le planning étant établi par la
méthode PERT et la méthode des potentiels, les transformations suivantes soient à
intégrer :
a) l'opération F ne peut commencer que 12 unités de temps après le début des opérations,
b) une nouvelle tâche V est introduite : elle doit être précédée par G et E et précéder I.
Sa durée est 7.
c) l'opération N peut commencer dès que les 2/5 de la tâche M sont accomplis.
d) l'opération O ne peut commencer que si 5 unités de temps se sont passées depuis la fin
de l'opération E et 2 depuis la fin de G.
Examinons les transformations qu'induisent ces nouvelles contraintes sur le tracé du
graphe PERT. On est obligé de créer de nouvelles opérations :
- une opération F', de durée 12 représentant l'attente entre le début du projet et la
tâche F.
- une opération O' de durée 5 représentant l'attente entre la fin de E et le début de
O, et une opération O'' représentant l'attente entre la fin de G et le début de O.
- deux opérations M' de durée de 2 et M'' de durée 3 pour représenter la
contrainte c),
PERT
Potentiels
Date au plus tôt
t i i : évènement
t i i : tâche
Date au plus tard
t i * i : évènement
t i * i : tâche
Marge libre
m ij = t j – t i – t ij
t ij : durée de la tâche ij
m i = min (t j – t i – ij )
j
(i)
ij : contrainte de temps
entre tâche i et tâche j
Date limité
ij = t j - t ij
ij = t i - m i
Marge totale
M ij = t
*
j – t i – t ij
M i = t
*
i – t i