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.2.2 Variantes de recherche taboue

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

Algorithme 2.2: Recherche Taboue

Soit _Scourante une solution de départ.

Fixer Nbriteration ;

Initialiser MeilleurC_max, MeilleurSolution, ListeTaboue;

i ? 1;

tant que (i = Nbriteration) faire

- Chercher _Ssuivante Tel que

( F(Ssuivante) = F(Svoisine) ) Et ( Svoisine ?? ListeTaboue ) ? Svoisine ? VScourante

- Mettre à jour ListeTaboue

- Scourante ?- Ssuivante

- si F(Ssuivante) = F(Scourante) alors MeilleurC_max ?- F(Ssuivante) MeilleurSolution ?- Ssuivante)

i ? i + 1;

retourner MeilleurSolution

On a implémentécinq variantes de recherche taboue dont chacune opère avec une combinaison spécifique des opérateurs de changement et des méthodes de gestion les listes taboue. Le Tableau 2.10 résume ces variantes.

Tableau 2.10 - Procédures de recherche taboue

Opérateurs de changement ??????????????????????? Liste taboue	a - opt	na - opt	opta
Gestion par mouvement	RT1	RT2	RT4
Gestion par makespan	.	RT3	RT5

Ainsi par exemple, la première procédure RT1 consiste à générer le voisinage à l'aide de l'opérateur de changement a - opt et à gérer la liste taboue en utilisant la méthode d'interdiction des mouvements déjàeffectués.

2.3.2.3 Procédure RTG

Après avoir testéles cinq procédures précédentes et étudiéleurs comportement pour faire le bon choix notamment en ce qui concerne la gestion taboue et les opérateurs de changement, on les a réunie dans une même procédure afin de pouvoir exploiter tous leurs avantages, cette procédure s'appelle RTG. L'idée consiste en premier lieu à exécuter les cinq procédures RT1, RT2, RT3,

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

RT4 et RT5 avec la même solution de départ, puis évaluer les cinq résultats obtenus, ensuite la meilleur séquence sera introduite dans les cinq procédures de manière à maximiser la probabilitéde trouver une solution meilleure (un résultat provenant de la RT1 a plusieurs chances d'être améliorési on l'in-troduit dans RT2, RT3, RT4 ou encore RT5).

Une approche semblable a étéutilisédans [36] qui consiste à générer en premier lieu un voisinage à l'aide de l'opérateur de changement a - opt pour en retenir la meilleur solution, puis un deuxième voisinage sera généréà partir de cette meilleur solution à l'aide de l'opérateur de changement ma - opt, cette approche a pour but d'augmenter la probabilitéd'améliorer le résultat. la RTG s'arrête si on a atteint un nombre d'itération sans amélioration. Le résultat est évaluéen calculant l'écart par rapport la borne inférieure, si cet écart est inférieur à 1% ou si le nombre d'itération fixéa étéatteint alors on arrête la recherche.

L'Algorithme 2.3 décrit la procédure RTG.

Algorithme 2.3: Algorithme RTG

Soient F : La fonction objectif, _Scourante une solution de départ.

Fixer Nbriteration

Fixer T = 1% (Taux d'amélioration)

Calculer BI (Borne inférieure)

i --- 1;

tant que (i _Nbriteration ) Et (Taux ~ T) faire

- Lancer RT1, RT2, RT3, RT4 et RT5 avec Scourante

- Déterminer la Meilleure solution SMeilleure

- Scourante --- SMeilleure

- Calculer Taux = F(SMeilleure)-BI x 100

BI

i -- i + 1

retourner SMeilleure

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