I.? Méthodes de résolutions de
problème d'ordonnancement :
Historiquement, c'est la Recherche Opérationnel
qui a commencé à élaborer des modèles
d'optimisation programmables. Depuis, d'autre techniques,
développées dans le cadre de la résolution de
problèmes en I.A sont venues s'y joindre. Le choix d'une méthode
de résolution répond toujours à une certaines
problématique que l'on peut tenter de caractériser à
travers quatre questions-clés [ESQU 99] :
? L'existence d'un modèle
d'optimisation.
? L'exactitude des solutions.
? Le mode résolution
(automatique/interactif).
? Le coût de la méthode.
Présenter la totalité des
méthodes et de leurs variantes apparaît difficile au vu du nombre
de travaux existants. Aussi nous présentons uniquement les grandes
orientations de ces méthodes. Les méthodes de résolution
se répartissent en deux catégories principales : les
méthodes exactes et les méthodes approchées ou Les
métas heuristiques.
24
II.4.1 Méthodes exactes
Les termes « méthodes exactes »
recouvrent un ensemble de méthodes d'ordonnancement issues de la
Recherche Opérationnelle. Ces méthodes sont
dénommées exactes du fait qu'elles sont prouvées
théoriquement convergentes vers une solution optimale à un
problème donné. Elles se basent pour cela sur des calculs
mathématiques complexes et coûteux rendant difficiles leur mise en
oeuvre et leur utilisation en dehors de cas très spécifiques en
nécessitant des ressources calculatoires (i.e. machines informatiques)
importantes [GOTH 93]. De par leur recherche d'optimum, ces méthodes
sont confrontées au problème de l'optimum local. Ce risque, bien
que présent également dans les méthodes approchées
(mais avec une importance moindre), est omniprésent dans toutes les
méthodes exactes.
La méthode dite de « Branch
and Bound » est un exemple caractéristique des
méthodes exactes et illustre ce propos. Elle fonctionne selon un
principe de recherche générale de solution dans une perspective
d'optimisation combinatoire [BLAZ1 96].
Remarquons que les méthodes exactes ne
permettent pas de représenter d'une part toutes les contraintes pouvant
exister sur les jobs dans un contexte d'atelier de production, ni d'autre part
de prendre en compte les préférences contextuelles (i.e. fonction
objectif multi variables) du responsable d'atelier.
II.4.2 Méthodes Approchées
Les méthodes d'ordonnancement dites
approchées, s'attachent davantage au moyen d'obtenir une solution
satisfaisante plutôt qu'optimale. La solution recherchée doit
vérifier un certain nombre de caractéristiques avec un coût
calculatoire raisonnable. Une classification en cinq catégories de ces
méthodes a été proposée [GOTH 93] :
? Les méthodes par construction
progressive.
? Les méthodes par voisinage.
? Les méthodes par
décomposition.
? Les méthodes par relaxation des
contraintes.
? Les méthodes liées à
l'intelligence Artificielle.
| 
