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

3.2 Paramétrage des méta-heuristiques

Le paramétrage des méta-heuristiques est une tâche critique car elle influence le comportement des procédures et par conséquence les résultats. Une méta-heuristique se base sur plusieurs paramètres parmi les suivants :

- Critère d'arrêt

- Longueur des listes taboue et leurs modes de gestion

- Application de l'aspiration

- Application de la descente

- Schéma de refroidissement

Les décisions concernant ces paramètres doivent ainsi être justifiées et prises avec soin. On a effectuéplusieurs tests sur les procédures de la recherche taboue ainsi que le recuit simulépour justifier les choix qu'on a fait.

3.2.1 Recherche Taboue

3.2.1.1 Longueur des listes taboue

Comme dans [36], une liste Taboue de longueur fixe L = 10 a étémainte-nue. Cette longueur semblait offrir le meilleur compromis entre la nécessit^éd'éviter le phénomène de l'allure cyclique et le temps de calcul qui augmente avec la longueur de L.

3.2.1.2 Application de l'aspiration

Après l'implémentation des différents procédures de la recherche taboue, on a testéleurs comportements en essayant de détecter les traces d'un cyclage possible. Pour le faire on a associéà chaque solution ir une emprunte W_ð calculée comme suit :

Wð =

?n i=1

(iri) × j

Bien que cette emprunte peut ne pas être unique pour une solution donnée, elle a étéretenue pour sa facilitéd'utilisation.

RT1

La Figure 3.1 présente les empruntes des solutions examinées par cette procédure pour une seule instance avec 200 itérations :

Résultats expérimentaux 47

FIGURE 3.1 - Empruntes des solutions de la RT1

On constate que les solutions suivent un cycle de 66 itérations, ce qui veut dire que chaque 66 itérations, la procédure revient au même point puis elle passe par les même solutions donnant ainsi une allure cyclique.

D'autre part, on a établie dans la Figure 3.2 la courbe de l'évolution du makespan pendant 200 itérations.

FIGURE 3.2 - Évolution du makespan de la RT1 pour 200 itérations

On constate que le makespan reste figédès les toutes premières itérations, d'oùla stagnation de la courbe. En d'autre terme, après les premières itérations, la procédure n'a pas pu améliorer ses résultats et par conséquence, la majo-ritédominante des itérations n'étaient qu'une perte de temps de calcul.

Ces constations ont mis l'accent sur le phénomène de l'allure cyclique que l'on peut justifier par le comportement des opérateurs de changement notamment le a - opt qui n'offre pas une exploration importante de l'espace de recherche (ce qui justifie d'ailleurs la stagnation de la courbe du makespan) et par l'absence d'un caractère de diversification dans notre procédure.

La solution était d'appliquer une aspiration pour éviter ce phénomène d'al-lure cyclique et pour donner plus de chance à la procédure afin qu'elle puisse

Résultats expérimentaux 48

RT3

Vu que cette procédure utilise le même opérateur de changement que la RT2

explorer de nouvelles zones de l'espace de recherche.

Le problème alors devient la détermination du nombre d'itérations au bout duquel on peut appliquer l'aspiration.

Pour avoir la réponse nous avons cherchéà savoir au bout de quelle itération la valeur de makespan reste figée, et cela en testant la RT1 sur les cinq familles d'instances pour n = 50 et n = 100 jobs avec in = 5. Le Tableau 3.2 résume ces résultats.

Tableau 3.2 - Nombres moyens d'itérations pour avoir la stagnation pour

RT1, 20 instances

	RT1
	n= 50		n= 100
	Moyenne	Ecart Type	Moyenne	Ecart Type
Famille 1	12.2	14.2	10.8	12.3
Famille 2	9.6	8.9	12.8	9.7
Famille 3	13.2	12.7	24.2	20
Famille 4	10.4	8.1	11.8	7.8
Famille 5	11.5	11.7	10.6	8.3

RT2

Bien que la RT2 ne présente pas vraiment un phénomène d'allure cyclique, on a bien remarquéune stagnation des valeurs des makespans.

Comme pour la RT1, le Tableau 3.3 illustre le nombre moyen d'itération au bout duquel on obtient une stagnation du makespan (on obtient le meilleur makespan pour la première fois).

Tableau 3.3 - Nombres moyens d'itérations pour avoir la stagnation pour

RT2, 20 instances

	RT2
	n= 50		n= 100
	Moyenne	Ecart Type	Moyenne	Ecart Type
Famille 1	3.5	1.6	3.9	3.3
Famille 2	9.6	8.9	4.6	2
Famille 3	16.5	29.6	19.1	31.2
Famille 4	6.5	9.1	3.6	1.6
Famille 5	3.7	2.1	4.1	3.5

Résultats expérimentaux 49

(ma - opt), elle aura le même paramétrage que cette dernière.

RT4

Comme pour la procédure RT2, la RT4 ne présente pas un phénomène d'al-lure cyclique.

De même, on a testéles numéros d'itérations au bout des quelles la procédure obtient sa meilleure solution ( voir Tableau 3.4 ).

Tableau 3.4 - Nombres moyens d'itérations pour avoir la stagnation pour RT4, 20 instances

	RT4
	n= 50		n= 100
	Moyenne	Ecart Type	Moyenne	Ecart Type
Famille 1	4.1	2	3.9	2.6
Famille 2	4.5	3.7	5.4	4
Famille 3	6.8	4.2	7.6	5.9
Famille 4	5.7	4.4	3.9	1.9
Famille 5	5.8	2.6	5.5	2.5

RT5

Vu que cette procédure utilise le même opérateur de changement que la RT4 (opt3), elle aura le même paramétrage que cette dernière.

En se basant sur les Tableaux 3.2, 3.3 et 3.4 on a fait le choix d'appliquer une aspiration dans chacune des procédures de recherche taboue et cela après un nombre d'itérations comme décrit dans le Tableau 3.5.

Tableau 3.5 - Nombre d'itération pour appliquer l'aspiration

	RT1	RT2 & RT3	RT4 & RT5
F1	28	8	6
F2	24	19	10
F3	45	50	14
F4	20	15	10
F5	24	8	9

L'Algorithme 3.1 décrit la démarche adoptée pour les procédures de recherche taboue.

Résultats expérimentaux 50

Algorithme 3.1: Recherche Taboue avec aspiration

Fixer _Nbriteration pour aspiration;

Initialiser MeilleurC_max, MeilleurSolution ; Asp - 0;

tant que (Critère d'arrêt non atteint) faire - Chercher Meilleur voisin Meilleurvoisin - Mettre à jour la liste taboue

- si F(Meivoisin) < MeilleurC_max alors

MeilleurC_max +- F(Meilleurvoisin)

MeilleurSolution ?- Meilleurvoisin - si Asp = Nbriteration alors

- Appliquer Aspiration - Asp - 0

Asp - Asp + 1;

retourner MeilleurSolution

À titre de confirmation, on a essayéde voir l'apport d'une telle approche. On a comparéla RT1 avant et après l'application d'une aspiration sur une seule instance appartenant à la famille F3 avec n = 100 jobs et in = 5 machines. Les Figures 3.3 et 3.4 comparent son comportement avec et sans aspiration.

FIGURE 3.3 - Évolution du makespan de la RT1 sans aspiration

Résultats expérimentaux 51

FIGURE 3.4 - Évolution du makespan de la RT1 avec aspiration

Sachant que la borne inférieure BI = 6007 on peut constater que l'aspi-ration a ététrès bénéfique et a améliorél'écart entre la solution de la RT1 et la valeur de BI de 3.44 % (sans aspiration) à 1.16 % (avec aspiration).