Nous décrivons plus précisément
dans les paragraphes suivants chacune de ces méthodes.
25
II.4.2.1 Méthodes par construction progressive
Cette catégorie de méthodes procède
à la construction d'une solution globale à partir
d'une
solution partielle complétée au fur et
à mesure de la résolution. A l'aide de règles de
placement, on ajoute à chaque itération un certain nombre de
tâches au plan de charge. La recherche est terminée quand toutes
les tâches ont été traitées. Ce placement peut
être réalisé aléatoirement, tout en respectant les
contraintes du problème, mais est plus généralement
effectué à l'aide de règles relativement simples ( ex :
placer toutes les tâches d'un job avant de passer à un autre
job).
II.4.2.2 Méthodes par voisinage
Ces méthodes consistent à explorer l'espace
des solutions d'ordonnancement en partant d'une
solution initiale complète de laquelle on
extrait une solution voisine. Cette nouvelle solution est alors
évaluée puis, si cette évaluation révèle que
la nouvelle solution est meilleure, elle devient la nouvelle solution de
référence. Le déplacement dans l'espace des solutions
s'effectue à l'aide d'une fonction de voisinage qui, à partir
d'une solution existante, génère une nouvelle solution qui est
alors réalisée par une fonction d'évaluation
f (monocritère ou multicritères). Le
calcul continue jusqu'à ce qu'une solution satisfaisant au(x)
critères(s) de recherche soit obtenue (i.e. l'évaluation par
f dépasse un seuil minimal).
Notons que ces méthodes de résolution
peuvent être assimilées à des méthodes
d'optimisation de solution (puisqu'elles supposent l'existence d'une solution
complète). Dès lors, le risque potentiel, lié à
toute méthode d'optimisation, de se retrouver bloqué dans des
optima locaux ne peut être écarté. Ce risque est
minimisé en intégrant dans la fonction de voisinage une variable
aléatoire. La méthode dite du recuit simulé
et la méthode Tabou sont
basées sur ce principe.
II.4.2.3 Méthodes par décomposition
Les méthodes par décomposition, comme leur
nom l'indique, procèdent à la décomposition du
problème d'ordonnancement afin de faciliter sa
résolution. Cette approche permet de simplifier les calculs en
restreignant à chaque décomposition l'étendue de l'espace
des solutions. Du fait du nombre et surtout de la variété de ces
méthodes nous ne présentons ici qu'une liste brièvement
décrite de ces méthodes :
? Décomposition hiérarchique :
décomposition du problème en niveaux
d'abstraction différents et
décroissants. On restreint de niveau en niveau l'espace des
solutions.
26
.. Décomposition structurelle : le principe
consiste à ne considérer le problème que du point de vue
temporel, en ignorant les contraintes de ressources. Une fois une solution
obtenue, on optimise l'utilisation des moyens, puis on rétablit les
contraintes sur les ressources et on adapte la solution à ces «
nouvelles » contraintes.
.. Décomposition de l'ensemble des solutions du
problème : l'espace des solutions est décomposé en
catégories, chacune étant évaluées
séparément des autres.
.. Décomposition temporelle : spécifique
aux problèmes d'ordonnancement dynamique, elle consiste à
décomposer le problème en intervalles de temps. Les solutions
sont calculées d'abord indépendamment pour être ensuite
adaptées aux contraintes de l'intervalle suivant.
.. Décomposition spatiale : on décompose
le problème d'atelier en regroupant les machines en îlots de
production (en essayant de les rendre les plus indépendants
possibles).
| 
