Contribution à la résolution des problèmes de flow shop avec machines dédiées, avec dates de disponibilité et délais de livraison

2.3 Méta-Heuristiques

Les méta-heuristiques sont des approches de résolution globale que l'on peut adapter à différents problèmes. Elles sont souvent le seul moyen disponible pour chercher des solutions satisfaisantes au problèmes NP-difficile. Cependant, elle prennent nettement plus de temps de calcul que les heuristiques spécifiques.

Les méta-heuristiques qu'on a implémentées se basent sur la notion de voisinage et les opérateurs de changements.

2.3.1 Notions de base

Étant donnéune solution S0 ; on définit l'opérateur de changement comme étant toute transformation qui génère une autre solution réalisable S'. L'en-semble des solutions obtenues par cet opérateur est appeléVoisinage de S0 (notéVS₀). On peut établir plusieurs opérateurs de changement et ainsi construire pour chaque solution de départ son voisinage spécifique.

Nous avons utilisétrois opérateurs de changement² : 2.3.1.1 Opérateur de changement (a - opt)

Le principe de cet opérateur consiste à permuter deux jobs voisins, l'en-semble des solutions voisines qui constituent le voisinage de la solution de départ S0 est égale à (n - 1) voisins (avec n est le nombre des jobs de la solution S0 )

Exemple : Pour n = 4 et S0 =-< _J2J3J1J4 >- on a : :

VS0 =

? ?? ??

S' 1 =-< J3J2J1J4 >- S' 2 =-< J2J1J3J4 >-S^'3 =-< J2J3J4J1 >-

Selon Houari et Mhallah [36], le but de l'utilisation de cette opérateur est d'éviter de détruire la structure de la solution de départ en la modifiant légèrement à chaque étape.

2. Ces opérateurs ont étéutilisés dans [36, 16, 2].

Présentation des méthodes de résolution 37

2.3.1.2 Opérateur de changement (na - opt)

Le principe de cet opérateur consiste à permuter deux Jobs non nécessairement

voisins. Cet opérateur donne un voisinage de n(n-1)

₂ solutions réalisables.

Exemple : Pour n = 4 et S0 =-< _J2J3J1J4 >- on a :

VS0 =

{ Si =-< J3J2J1J4 >- S2 =-< J1J3J2J4 >- S3 =-< J4J3J1J2 >- S4 =-< J2J1J3J4 >- S5 =-< J2J4J1J3 >- S^'6 =-< J2J3J4J1 >-

Notons que le voisinage générépar l'opérateur a - opt est entièrement contenu dans le voisinage générépar l'opérateur na - opt.

2.3.1.3 Opérateur de changement (opt3)

Le principe de cet opérateur consiste à insérer un job en une position donnée et à décaler les autres jobs en gardant leur ordre de départ. Cet opérateur donne un voisinage de n(n - 2) + 1 solutions réalisables.

Exemple : pour n = 3 et S0 =-< _J1J2J3 >-, le voisinage de S0 est :

VS0 =

{ S1. =-< J2J1J3 >- S2 =-< J3J1J2 >- S3 =-< J1J3J2 >- S4 =-< J2J3J1 >-