148
Recherche opérationnelle
tâches. Ainsi, entre le début de E et celui de O, 11 unités de temps doivent s'écouler, ce
qui est consigné dans la colonne correspondant à O.
On voit que les modifications apportées au tableau des potentiels sont nettement plus
aisées que celles qui ont permis de dessiner le nouveau graphe de PERT. En particulier,
l'addition d'arcs fictifs dans le graphe PERT complique assez rapidement le problème.
D'une façon générale, la méthode des potentiels est d'une plus grande souplesse que la
méthode de PERT. Cela dit, le graphe PERT fournit une bonne visualisation du
déroulement des tâches, ce que permet moins le tableau des potentiels. On peut d'ailleurs
utiliser conjointement les deux méthodes, en résolvant d'abord le problème par les
potentiels et en représentant ensuite la solution trouvée par un graphe PERT (on peut
aussi visualiser par un GANTT).
6.5. LES AUTRES TYPES DE PROBLEME
Nous n'avons résolu ici que des problèmes d'ordonnancement simples, dans la mesure où
ils ne comportaient que des contraintes potentielles (contraintes de succession). Ils
donnent cela dit de nombreuses applications effectives, notamment au niveau de la
gestion du projet, un mode de gestion qui reçoit un engouement certain actuellement. Il
n'y a pas un projet de quelque importance, qu'il s'agisse de la construction d'une
infrastructure ou de la conception d'une nouvelle voiture, qui ne commence pas par
l'élaboration d'un PERT.
L'introduction de contraintes autres, disjonctives ou cumulatives par exemple, peut
compliquer notablement le problème. Les méthodes PERT et potentiels étant de simples
adaptations des algorithmes de plus court chemin sont clairement polynomiales. Il n'en
est plus de même lorsque l'on introduit des contraintes disjonctives, qui, pourtant,
renvoient à des problèmes très réels, comme celui d'ordonnancement d'atelier
(interdiction d'usage simultané de la même ressource par des pièces différentes). Les
méthodes combinatoires qui ont été proposées ici ou là et qui recherchent l'optimum ne
sont plus polynomiales. On a souvent recours à des heuristiques (cf. plus loin).
Une autre complication survient lorsque l'on considère des durées de tâches qui ne sont
plus définies à l'avance, mais aléatoires. Là aussi, il est difficile de traiter formellement
les problèmes correspondants. La plupart du temps, on se contente de durées moyennes,
mais on peut démontrer que ce faisant on biaise vers le bas la durée totale attendue du
projet.
Enfin, un autre problème se pose lorsque l'on veut introduire un compromis entre la
durée et le coût. Si l'on n'est pas satisfait du délai total trouvé d'effectuation des travaux,
on peut penser accélérer certaines tâches, mais en dépensant plus (embauches
supplémentaires par exemple). Sous certaines hypothèses (augmentation linéaire des
coûts en fonction de la diminution de la durée sur chaque tâche), on dispose d'un
algorithme polynomial -le PERT-COST- permettant une réduction donnée du délai au
coût minimal.
Recherche opérationnelle
tâches. Ainsi, entre le début de E et celui de O, 11 unités de temps doivent s'écouler, ce
qui est consigné dans la colonne correspondant à O.
On voit que les modifications apportées au tableau des potentiels sont nettement plus
aisées que celles qui ont permis de dessiner le nouveau graphe de PERT. En particulier,
l'addition d'arcs fictifs dans le graphe PERT complique assez rapidement le problème.
D'une façon générale, la méthode des potentiels est d'une plus grande souplesse que la
méthode de PERT. Cela dit, le graphe PERT fournit une bonne visualisation du
déroulement des tâches, ce que permet moins le tableau des potentiels. On peut d'ailleurs
utiliser conjointement les deux méthodes, en résolvant d'abord le problème par les
potentiels et en représentant ensuite la solution trouvée par un graphe PERT (on peut
aussi visualiser par un GANTT).
6.5. LES AUTRES TYPES DE PROBLEME
Nous n'avons résolu ici que des problèmes d'ordonnancement simples, dans la mesure où
ils ne comportaient que des contraintes potentielles (contraintes de succession). Ils
donnent cela dit de nombreuses applications effectives, notamment au niveau de la
gestion du projet, un mode de gestion qui reçoit un engouement certain actuellement. Il
n'y a pas un projet de quelque importance, qu'il s'agisse de la construction d'une
infrastructure ou de la conception d'une nouvelle voiture, qui ne commence pas par
l'élaboration d'un PERT.
L'introduction de contraintes autres, disjonctives ou cumulatives par exemple, peut
compliquer notablement le problème. Les méthodes PERT et potentiels étant de simples
adaptations des algorithmes de plus court chemin sont clairement polynomiales. Il n'en
est plus de même lorsque l'on introduit des contraintes disjonctives, qui, pourtant,
renvoient à des problèmes très réels, comme celui d'ordonnancement d'atelier
(interdiction d'usage simultané de la même ressource par des pièces différentes). Les
méthodes combinatoires qui ont été proposées ici ou là et qui recherchent l'optimum ne
sont plus polynomiales. On a souvent recours à des heuristiques (cf. plus loin).
Une autre complication survient lorsque l'on considère des durées de tâches qui ne sont
plus définies à l'avance, mais aléatoires. Là aussi, il est difficile de traiter formellement
les problèmes correspondants. La plupart du temps, on se contente de durées moyennes,
mais on peut démontrer que ce faisant on biaise vers le bas la durée totale attendue du
projet.
Enfin, un autre problème se pose lorsque l'on veut introduire un compromis entre la
durée et le coût. Si l'on n'est pas satisfait du délai total trouvé d'effectuation des travaux,
on peut penser accélérer certaines tâches, mais en dépensant plus (embauches
supplémentaires par exemple). Sous certaines hypothèses (augmentation linéaire des
coûts en fonction de la diminution de la durée sur chaque tâche), on dispose d'un
algorithme polynomial -le PERT-COST- permettant une réduction donnée du délai au
coût minimal.