Chapitre III : Spécification et
modélisation d'une solution à base de SMA
METAHEURISTIQUES
Les temps de calcul des métaheuristiques en
général nécessitent
de nombreux calculs, en particulier au niveau de la fonction
d'évaluation. De plus, ils sont le plus souvent difficiles à
mettre en oeuvre. Des paramètres comme la taille de la population ou le
taux de mutation sont parfois difficiles à déterminer.
Il faut aussi noter l'impossibilité d'être
assuré, même après un nombre important de
générations, que la solution trouvée soit la meilleure. On
peut seulement être sûr que l'on s'est approché de la
solution optimale (pour les paramètres et la fonction
d'évaluation choisie), sans la certitude de l'avoir atteinte.
Un autre problème important est celui des optima
locaux. En effet, lorsqu'une population évolue, il se peut que certains
individus qui, à un instant occupent une place importante au sein de
cette population, deviennent majoritaires. À ce moment, il se peut que
la population converge vers cet individu et s'écarte ainsi d'individus
plus intéressants mais trop éloignés de l'individu vers
lequel on converge
8.3. Pertinences des méthodes exactes
Les ressources sont généralement en nombre et
capacité limités, les contraintes nombreuses (respect des
délais, précédences entre tâches, etc.). Ceci
expliquant pourquoi les problèmes d'ordonnancement sont des
problèmes combinatoires souvent très difficiles à
résoudre en pratique.
En revanche l'utilisation de méthode exacte est, non
seulement possible en vue des contraintes de temps de résolution (assez
larges), mais aussi, puisqu'ils permettent une meilleure perception des agents
de leur environnement. Cet aspect est lié en grande partie aux
structures de données utilisées et qui seront éclaircies
dans les sections suivantes.
8.4. Phases de résolution
Nous avons décomposé le comportement de l'agent
en trois « activités». Chaque activité est
constituée d'un ensemble de procédures : construction,
évaluation et exécution. Ces procédures sont
elles-mêmes constituées d'un ensemble de procédures et de
fonctions.
83
Chapitre III : Spécification et
modélisation d'une solution à base de SMA
Construction
· Construction des tables de compatibilité
· Génération des affectations
· Génération des ordonnancements
Evaluation
· Evaluation des seuquences.
· Evaluation des sequence
· Validation de l'ordonncement
Execution
· Execution et suivie de l'ordonncement
Figure 61: Les trois activités du
modèle de résolution proposé
Afin de mieux démontrer notre solution nous allons traiter
le cas suivant : - Deux machines HPLC notées H1 et H2.
- Deux échantillons du produit P1 pour
analyse.
- Un échantillon du produit P2.
TABLE DES COMPATIBILITES :
Du fait de la contrainte de compatibilité
produit-ressource, il est indispensable de dégager en premier lieu toute
les combinaisons possibles. Nous obtenons alors la table de
compatibilité suivante :
Tableau 10: Table de compatibilité pour les
tests d'HPLC
Ligne 1 correspond aux compatibilités du produit P1
avec les HPLC 1 et 2 nous avons deux compatibilités; nous posons la
fonction Fcomp (produit, ressource) qui est égale à 1 lorsque la
ressource peut exécuter le test :
Fcomp (P1, H1) =1; Fcomp (P1,
H2) =1
Ligne 2 correspond aux compatibilités du produit P2 avec
les HPLC 1 & 2 nous avons deux compatibilités. Alors Fcomp prend les
valeurs suivantes :
Fcomp (P2, H1) =1; Fcomp (P2,
H2) =1
Cette structure de données est l'une des premières
que va construire l'agent en récoltant des données de son
environnement.
84
|