132
Recherche opérationnelle
Enfin, on n'oubliera pas que dans le cas de la recherche de chemins de valeur optimale, il
convient avant tout calcul d'examiner si le graphe comporte ou non des circuits : dans
l'affirmative, en effet, le chemin trouvé risque fort d'être de valeur infinie.
6.4. APPLICATION DE LA NOTION DE CHEMINEMENT DANS UN
GRAPHE : LES PROBLEMES D'ORDONNANCEMENT
6.4.1. Généralités
Dans cette section, nous allons examiner les problèmes posés par la réalisation d'un
objectif pouvant se décomposer en tâches élémentaires multiples. C'est par exemple le
cas de la construction d'une maison ou encore le problème très célèbre du passage de
pièces sur un certain nombre de machines.
Résoudre le problème d'ordonnancement attaché à un objectif donné, c'est déterminer
l'évolution dans le temps de la réalisation de cet objectif, c'est-à-dire, fixer à l'avance les
dates d'exécution de chacune des tâches élémentaires dont est constitué l'objectif, et cela
de façon :
- à respecter un certain nombre de contraintes auxquelles sont assujetties les
tâches élémentaires.
- à satisfaire au mieux un ou plusieurs critères précisés à l'avance : il peut s'agir
de critères de type coût minimal ou durée minimale ou encore, consommation
minimale d'un certain type de produit...
Quant aux contraintes, elles peuvent être de plusieurs sortes :
- soit il s'agit de contraintes potentielles, qui indiquent par exemple des
successions sur les tâches (la tâche
doit commencer après la fin de la tâche
) ou encore des localisations temporelles obligées ( la tâche
doit
commencer après la date ).
- soit il s'agit de contraintes disjonctives qui expriment que certaines tâches ne
peuvent s'effectuer simultanément : c'est le cas par exemple de tâches
nécessitant l'utilisation d'une même machine, disponible seulement pour l'une
d'entre elles.
- soit il s'agit encore de contraintes dites cumulatives : celles-ci expriment qu'une
certaine matière ou qu'un certain moyen de production, qui peut être utilisée
pour plusieurs tâches, n'est cependant disponible qu'en quantité limitée; ainsi si
est la quantité maximale du facteur disponible à et si
est la
quantité de requise par la tâche à l'instant , on doit avoir :
t
k
k
i
i
t
t
)
(
)
(
Un problème d'ordonnancement est, on le voit, l'exemple type de problèmes
combinatoires : dès que le nombre de tâches devient quelque peu important, il est
difficile de trouver des solutions respectant les contraintes et par ailleurs satisfaisantes
du point de vue des critères choisis.
Recherche opérationnelle
Enfin, on n'oubliera pas que dans le cas de la recherche de chemins de valeur optimale, il
convient avant tout calcul d'examiner si le graphe comporte ou non des circuits : dans
l'affirmative, en effet, le chemin trouvé risque fort d'être de valeur infinie.
6.4. APPLICATION DE LA NOTION DE CHEMINEMENT DANS UN
GRAPHE : LES PROBLEMES D'ORDONNANCEMENT
6.4.1. Généralités
Dans cette section, nous allons examiner les problèmes posés par la réalisation d'un
objectif pouvant se décomposer en tâches élémentaires multiples. C'est par exemple le
cas de la construction d'une maison ou encore le problème très célèbre du passage de
pièces sur un certain nombre de machines.
Résoudre le problème d'ordonnancement attaché à un objectif donné, c'est déterminer
l'évolution dans le temps de la réalisation de cet objectif, c'est-à-dire, fixer à l'avance les
dates d'exécution de chacune des tâches élémentaires dont est constitué l'objectif, et cela
de façon :
- à respecter un certain nombre de contraintes auxquelles sont assujetties les
tâches élémentaires.
- à satisfaire au mieux un ou plusieurs critères précisés à l'avance : il peut s'agir
de critères de type coût minimal ou durée minimale ou encore, consommation
minimale d'un certain type de produit...
Quant aux contraintes, elles peuvent être de plusieurs sortes :
- soit il s'agit de contraintes potentielles, qui indiquent par exemple des
successions sur les tâches (la tâche
doit commencer après la fin de la tâche
) ou encore des localisations temporelles obligées ( la tâche
doit
commencer après la date ).
- soit il s'agit de contraintes disjonctives qui expriment que certaines tâches ne
peuvent s'effectuer simultanément : c'est le cas par exemple de tâches
nécessitant l'utilisation d'une même machine, disponible seulement pour l'une
d'entre elles.
- soit il s'agit encore de contraintes dites cumulatives : celles-ci expriment qu'une
certaine matière ou qu'un certain moyen de production, qui peut être utilisée
pour plusieurs tâches, n'est cependant disponible qu'en quantité limitée; ainsi si
est la quantité maximale du facteur disponible à et si
est la
quantité de requise par la tâche à l'instant , on doit avoir :
t
k
k
i
i
t
t
)
(
)
(
Un problème d'ordonnancement est, on le voit, l'exemple type de problèmes
combinatoires : dès que le nombre de tâches devient quelque peu important, il est
difficile de trouver des solutions respectant les contraintes et par ailleurs satisfaisantes
du point de vue des critères choisis.