134
Recherche opérationnelle
Remarque importante : on n'a affaire ici qu'à des contraintes potentielles. Ne sont
introduites ni des contraintes disjonctives, ni des contraintes cumulatives.
La première question que nous allons nous poser sera la suivante : comment ordonner les
différentes tâches en respectant les contraintes de succession ci-dessus pour minimiser le
temps total de réalisation du projet ?
Nous allons exposer les deux méthodes citées ci-dessus permettant de résoudre ce
problème simple d'ordonnancement, ne faisant intervenir que des contraintes de
succession.
6.4.2.1. Réduction des relations de succession.
Auparavant, il convient de simplifier au maximum ces contraintes, en supprimant les
contraintes redondantes, telles que :
Contraintes qui figurent dans le tableau ci-dessus. La troisième contrainte est
évidemment redondante.
Pour éliminer ces contraintes pour chaque tâche, on dresse la liste des tâches
antécédentes (c'est celle dont on dispose déjà) puis la liste des antécédentes de ces
antécédents etc... Dès qu'une tâche se trouve à la fois dans la liste des antécédentes
immédiates et dans la liste d'antécédentes plus éloignées, on peut la supprimer.
Tâches
1ère
antécédente
Antécédents
seconds
Antécédents
troisièmes
Antécédents
quatrièmes
A
-
-
-
-
B
A
-
-
-
C
A
-
-
-
D
A, C
A
-
-
E
D
A, C
A
-
F
A,B
A
-
G
D, F, K,L
A, C, B, J
A
-
H
B, F, G
A, B, D, F, K, L
A, C, B, J
A
I
G, M, N
D, F, K, L, B, J, M
C, B, J, B, A
A
J
A
-
-
K
J
A
-
L
A,B
A
-
M
B, J, K, L
A, J, B
A
-
N
K, L, M
J, B, K, L
A
-
O
E
D
C