1.2 Méthodes de résolution
Plusieurs spécialistes à savoir P. Lopez [51] et G.
Cavory [11] ont distinguéessentiellement deux classes de
méthodes de résolution :
- Les méthodes de résolution exactes permettant de
donner des solutions optimales en un temps polynomial avec une taille
limitédu problème. - Les méthodes approchées dont
les heuristiques et les méta-heuristiques qui donnent des solutions
approchées en un temps raisonnable.
Pour les méthodes exactes, I.Kacem [42] a
distinguétrois sous classes dont la procédure par
séparation et d'évaluation (Branch &
Bound), la programmation dynamique et la programmation linéaire.
Bien que ces méthodes fournissent des solutions optimales, leurs
performances notamment en ce qui concerne le temps de calcul diminue
proportionnellement avec la taille des problèmes.
Les méthodes approchées toutefois ne donnent
aucune garantie d'opti-malitémais elles demeurent les plus
utilisées pour la majoritédes problèmes d'ordonnancement
et «la plus part des spécialistes ont orientéleurs recherche
vers le développement des méthodes heuristiques» [51,
37].
Les méthodes approchées englobent les
heuristiques et les méta-heuristiques, Y. Harrath [37] définie
ces termes comme suit : «Une heuristique est une méthode de calcul
pour un problème générique d'optimisation produisant une
solution non nécessairement optimale. Par contre, une
méta-heuristique est un ensemble de concepts applicables à un
large ensemble de problèmes d'optimisation combinatoire pour
créer de nouvelle heuristiques.»
Une classification des différents types de
méta-heuristiques est présentépar Widmer et al.
[68], les auteurs considèrent qu'ils existe trois types de
méta-heuristiques, les méta-heuristiques
constructives basées sur l'idée de la diminution progressive de
la taille du problème, les méta-heuristiques évolutives
inspirées des phénomènes réels telles que
l'algorithme génétique et les colonies de fourmis et les
méta-heuristiques de recherche locale dont la recherche taboue et le
Recuit Simulé.
La recherche taboue a étéprésentée
pour la première fois par Glover [22], la formulation finale de cette
méta-heuristiques est apparue en deux partie [23, 24], cette
méthode se base sur deux principe. le premier principe consiste à
crée le voisinage de la solution courante à chaque
itération et choisir le meilleur voisin et le deuxième principe
consiste à garder en mémoire les dernières solutions
visitées afin d'interdire le retour vers des régions
visitées pour un nombre d'itérations fixé.
Le recuit simuléest une méthode de recherche
locale dont le mécanisme de recherche est calquésur l'algorithme
de Metropolis et al. [53] et les principes du recuit thermodynamique.
L'idée se base sur une analogie entre l'énergie du système
physique et la fonction objectif du problème d'optimisation et entre les
états de ce système physique et les solutions réalisable
du problème. Kirkpatrick et al. [44] et Cerny [12] ont
étéles premiers à s'inspirer d'une telle technique pour
résoudre des problèmes d'optimisation combinatoire.
Plusieurs problèmes de flow shop sont traités
par ces deux méta-heuristiques (voir section état de l'art).
Problèmes d'ordonnancement 10
FIGURE 1.2 - Sous permutation au second
étage
| 
