3.3.2 Méta-heuristiques
Après avoir sélectionnéles meilleures
heuristiques qu'on a implémentées, nous avons effectués
des tests sur les différentes méta-heuristiques.
Pour chaque familles d'instance, le test consiste en premier
lieu à calculer les cinq bornes inférieures et en tirer la
meilleure borne BI. Ensuite on exécute les sept meilleures
heuristiques puis on retient la séquence ayant la meilleure valeur de
makespan. Cette séquence sera injectée dans la procédure
du Recuit Simulé(RS) ainsi que dans les cinq procédures
de recherche taboue (RT1, RT2, RT3, RT4 et
RT5),la meilleure séquence provenant de l'une des cinq
dernières sera introduite dans la procédure RTG.
Notons que si une méta-heuristiques tient une
séquence dont le makespan est égale à BI alors
elle arrête la recherche, sinon on calcul l'écart entre la
solution provenant des méta-heuristiques et la borne BI.
Les tests ont étéeffectués sur 20
instances avec quatre tailles des problèmes (n = 20,
50, 100 et 150) pour chaque famille.
Les Tableaux 3.19, 3.20, 3.21, 3.22 et 3.23
synthétisent les résultats des différentes
méta-heuristiques pour chaque famille, les moyennes des écarts
ainsi que le nombre de fois oùles procédures
avaient des solutions égales àla borne BI sur
les 20 instances.
Tableau 3.19 - Résultats méta-heuristiques pour
F1, in = 5
|
Famille F1
|
|
n = 20
|
n=50
|
n = 100
|
n = 150
|
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
|
RT1
|
0.05
|
18
|
0.02
|
18
|
0.01
|
17
|
0.00
|
20
|
|
RT2
|
0.02
|
19
|
0.01
|
19
|
0.01
|
18
|
0.00
|
20
|
|
RT3
|
0.02
|
19
|
0.02
|
18
|
0.01
|
18
|
0.00
|
20
|
|
RT4
|
0.02
|
19
|
0.02
|
18
|
0.01
|
18
|
0.00
|
20
|
|
RT5
|
0.02
|
19
|
0.02
|
18
|
0.01
|
18
|
0.00
|
20
|
|
RTG
|
0.02
|
19
|
0.02
|
18
|
0.01
|
18
|
0.00
|
20
|
|
RS
|
0.11
|
17
|
0.20
|
11
|
0.15
|
8
|
0.28
|
2
|
Résultats expérimentaux 63
Tableau 3.20 - Résultats méta-heuristiques pour
F2, in = 5
|
Famille F2
|
|
n = 20
|
n=50
|
n = 100
|
n = 150
|
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
|
RT1
|
0.28
|
13
|
0.04
|
17
|
0.00
|
19
|
0.00
|
19
|
|
RT2
|
0.21
|
17
|
0.01
|
18
|
0.00
|
20
|
0.00
|
20
|
|
RT3
|
0.21
|
17
|
0.01
|
18
|
0.00
|
20
|
0.00
|
20
|
|
RT4
|
0.21
|
17
|
0.01
|
17
|
0.00
|
20
|
0.00
|
20
|
|
RT5
|
0.21
|
17
|
0.01
|
17
|
0.00
|
20
|
0.00
|
20
|
|
RTG
|
0.21
|
17
|
0.01
|
18
|
0.00
|
20
|
0.00
|
20
|
|
RS
|
0.21
|
17
|
0.25
|
9
|
0.18
|
2
|
0.40
|
1
|
Tableau 3.21 - Résultats méta-heuristiques pour
F3, in = 5
|
Famille F3
|
|
n = 20
|
n=50
|
n = 100
|
n = 150
|
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
|
RT1
|
2.63
|
1
|
1.05
|
3
|
0.38
|
1
|
0.57
|
0
|
|
RT2
|
1.59
|
2
|
0.48
|
6
|
0.15
|
6
|
0.13
|
3
|
|
RT3
|
1.58
|
2
|
0.54
|
6
|
0.16
|
7
|
0.17
|
3
|
|
RT4
|
1.91
|
1
|
0.52
|
6
|
0.18
|
4
|
0.25
|
2
|
|
RT5
|
1.92
|
1
|
0.58
|
5
|
0.17
|
5
|
0.27
|
1
|
|
RTG
|
1.51
|
3
|
0.45
|
7
|
0.14
|
7
|
0.13
|
3
|
|
RS
|
1.75
|
1
|
0.92
|
1
|
0.70
|
1
|
0.75
|
0
|
Tableau 3.22 - Résultats méta-heuristiques pour
F4, in = 5
|
Famille F4
|
|
n = 20
|
n=50
|
n = 100
|
n = 150
|
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
|
RT1
|
1.02
|
9
|
0.41
|
7
|
0.12
|
9
|
0.07
|
11
|
|
RT2
|
0.02
|
19
|
0.03
|
17
|
0.02
|
17
|
0.01
|
18
|
|
RT3
|
0.22
|
16
|
0.03
|
17
|
0.04
|
17
|
0.02
|
17
|
|
RT4
|
0.04
|
18
|
0.02
|
18
|
0.01
|
19
|
0.00
|
20
|
|
RT5
|
0.04
|
18
|
0.01
|
19
|
0.01
|
19
|
0.00
|
19
|
|
RTG
|
0.02
|
19
|
0.01
|
19
|
0.01
|
19
|
0.00
|
20
|
|
RS
|
0.18
|
17
|
0.26
|
8
|
0.34
|
1
|
0.34
|
1
|
Résultats expérimentaux 64
Tableau 3.23 - Résultats méta-heuristiques pour
F5, in = 5
|
Famille F5
|
|
n = 20
|
n=50
|
n = 100
|
n = 150
|
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
Ecart
|
BI
|
|
RT1
|
1.43
|
6
|
0.71
|
3
|
0.38
|
2
|
0.20
|
5
|
|
RT2
|
0.46
|
13
|
0.20
|
11
|
0.08
|
12
|
0.06
|
9
|
|
RT3
|
0.47
|
13
|
0.23
|
9
|
0.14
|
7
|
0.11
|
6
|
|
RT4
|
0.42
|
14
|
0.20
|
9
|
0.06
|
13
|
0.06
|
8
|
|
RT5
|
0.45
|
13
|
0.23
|
8
|
0.11
|
7
|
0.09
|
5
|
|
RTG
|
0.35
|
14
|
0.16
|
12
|
0.06
|
13
|
0.04
|
12
|
|
RS
|
0.48
|
13
|
0.58
|
4
|
0.46
|
0
|
0.44
|
0
|
Nous remarquons tout d'abord que la procédure RTG
a les écarts les plus faible notamment en la comparant avec les
autres procédures de recherche taboue.
Bien que le Recuit simuléa fait un écart au pire
des cas qui soit meilleur que celui de RT1 pour certaines instances
(pour F3, RS donne un écart de 1.75% alors
RT1 donne 2.63%), il s'avère que la recherche taboue
notamment la RTG est plus performante que le RS et ce pour
toutes les familles d'instances et toutes les tailles des problèmes.
Un résultat similaire a
étédonnépar Houari et al. [36] qui ont
effectuéune étude comparative entre ces deux
méta-heuristiques et oùla recherche taboue était la plus
performante.
On remarque aussi que pour les familles F1 et
F2, une solution optimale est vite trouvée et cela dans la
majoritéécrasante des instances testées et pour toutes les
tailles des problèmes. D'autre part, on constate que plus la taille du
problème augmente plus il est facile d'avoir une solution optimale et
cela en tenant une solution égale à la borne BI
(àl'exception de la famille F3). Ces résultats
confirment le constat déjàétabli pour des problèmes
similaires par H. Hadda [34] et Xi et al. [69] qui affirment que plus
la taille des instances augmente, plus ils sont facilement solubles.
En revanche, les familles F3 et F5 se sont
montrées très difficile à résoudre avec un nombre
très faible de solutions optimales et des écarts relativement
importants.
En se penchant sur les cinq procédures de la recherche
taboue, on remarque que la RT1 est la moins performante avec le plus
grand écart et le plus faible nombre de solutions optimales, on peut
expliquer ce résultat par
Résultats expérimentaux 65
l'opérateur de changement utiliséà savoir
le a-opt qui n'offre pas une exploitation importante de
l'espace de recherche. De plus, la permutation des jobs voisins n'a pas un
effet considérable sur la performance de la solution du fait que la
majoritéde ces mouvements sont inutiles car ils ont une forte chance de
ne pas agir sur le chemin critique. Par ailleurs, les procédures
RT2 et RT3 ont donnéde bons résultats notamment
pour la famille F3, mis à part cette famille spécifique,
on constate que ces deux procédures n'ont pas dépasséun
écart de 0.47% dans le reste des familles d'instances. Nous
pouvons conclure d'une part quant à la performance de l'opérateur
de changement na - opt que même s'il détruit la
structure de la séquence il s'est avérétrès
efficace, et d'autre part quant à la gestion de la liste taboue par la
méthode d'inter-diction des mouvements qui a dominél'autre
méthode du fait que la RT2 est plus performante que la
RT3.
En ce qui concerne RT4 et RT5, on remarque
une légère dominance de la RT4 par rapport à la
RT5 pour les familles F5 et F3, pour le reste des
familles les deux procédures ont donnédes résultats
très similaires.
En ce qui concerne les bornes inférieures, on peut
conclure qu'elles ont étébien efficaces étant
donnéqu'elle ont coïncidéavec des makespans optimaux.
Dans ce contexte, les bornes BI4 et BI5
données par les équations (2.4) et (2.5) ont
étéles plus performantes.
Nous avons enregistréle temps de calcul moyens pour
toutes les heuristiques et les méta-heuristiques retenues à la
fois pour chaque famille. Le Tableau 3.24 illustre ces temps de calcul.
Tableau 3.24 - Temps de Calcul pour m =
5
n
|
20
|
50
|
100
|
150
|
|
F1
|
0.2 sec
|
5.55 sec
|
48.8 sec
|
8.6 sec
|
|
F2
|
1.5 sec
|
6.55 sec
|
3.8 sec
|
12.6 sec
|
|
F3
|
8.7 sec
|
1.4 min
|
5.2 min
|
18.5 min
|
|
F4
|
0.3 sec
|
6.3 sec
|
46.7 sec
|
1.6 min
|
|
F5
|
2.9 sec
|
25.3 sec
|
3.1 min
|
12.1 min
|
Comme on peut le constater, à l'exception des familles
F3 et F5, le temps de calcul était très
raisonnable ne dépassant pas 1.6 minutes pour la famille
F4 pour n = 150. Notons ici que les temps de
calcul pour les familles F3 et
F5 sont important du fait qu'on ne touche pas souvent la
borne inférieure.
Résultats expérimentaux 66
Par ailleurs, en passant de m = 5 à m
= 10 machines au deuxième étage, on n'a pas
constatéune différence considérable concernant le temps de
calcul et les écarts des méta-heuristiques, en revanche, plus la
taille de l'instance augmente, sa résolution requière un temps de
calcul plus important.
| 
