Problèmes de chemins
133
Jusqu'à une époque relativement récente (1957), on ne disposait d'algorithmes que dans
des cas très limités, et pour le cas général, on se servait d'un outil assez fruste destiné
d'avantage à la visualisation qu'à la résolution du problème, à savoir le diagramme de
Gantt.
En abscisse de ce diagramme, on représente les temps
de début des tâches , en
ordonnée le numéro des tâches. Une barre de longueur égale à la durée de la tâche
est dessinée avec pour extrémité initiale le point de coordonnées
On peut ainsi, par tâtonnements successifs, constituer la ''visualisation'' d'un
ordonnancement compatible avec les contraintes. Mais ce diagramme ne permet guère
d'optimiser l'ordonnancement et par ailleurs, toute modification dans les contraintes
nécessite en général la reconstruction totale du graphique.
Depuis, se sont développées des méthodes plus perfectionnées, quoique souvent fondées
sur des principes simples, qui font un large usage de la théorie des graphes. Il s'agit
essentiellement de la méthode américaine PERT (Project Evaluation and Review
Technique) et de la méthode française dite méthodes de potentiels. Nous allons donner
une illustration de ces deux méthodes sur un exemple simple.
6.4.2. Un exemple de problème d'ordonnancement
Soit la réalisation d'un certain projet que l'on peut décomposer en 15 opérations
élémentaires. Le tableau suivant donne la durée de chacune de ces tâches ainsi que les
tâches qui doivent la précéder.
Tâches
Durée
Tâches antécédentes
A
6
-
B
4
A
C
5
A
D
4
A, C
E
6
D
F
7
A, B
G
8
D, F, K, L
H
2
B, F, G
I
5
G, M, N
J
2
A
K
7
J
L
6
A, B
M
5
B, J, K, L
N
7
K, L, M
O
3
E