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.3 Résultats des expérimentations

Dans cette section, nous entreprenons d'analyser les performances des différentes approches de résolution présentées précédemment. Notons que les simulations numérique ont étéfaites sur un micro-processeur de 1.46 GHz. Les heuristiques et les méta-heuristiques ont étéprogrammées en langage C++.

3.3.1 Heuristiques

Afin d'identifier les meilleurs heuristiques, on a effectuédes tests sur les cinq familles de problèmes avec 20 instances pour chaque taille. L'évaluation était basée sur la moyenne des écarts par rapport à la borne inférieur BI.

Cmax - BI

Ecart = BI × 100

Les Tableaux 3.13 et 3.14 illustrent les moyennes des écarts pour l'en-semble des heuristiques avec in = 5 et les Tableaux 3.15 et 3.16 avec in = 10.

Tableau 3.13 - Résultats des heuristiques, Familles F1, F2 et F3 (in = 5)

		F1				F2				F3
n	20	50	100	150	20	50	100	150	20	50	100	150
H1	1.08	0.23	0.09	0.04	1.76	0.47	0.11	0.08	17.21	5.96	2.06	2.00
H2	7.87	3.18	1.19	0.68	6.94	2.36	0.92	0.45	28	16	12	12
H3	3.67	1.53	0.80	0.47	5.43	1.90	0.63	0.39	8.78	5.09	2.52	3.16
H4	5.78	2.45	1.28	0.87	7.76	2.52	1.37	0.93	8.12	4.11	2.65	2.77
H5	3.00	1.13	0.65	0.58	3.03	1.21	0.90	0.62	11.00	5.48	1.98	1.85
H6	1.12	0.21	0.08	0.03	1.68	0.40	0.11	0.05	23	10	6.90	5.28
H7	0.99	0.13	0.05	0.01	1.72	0.13	0.01	0.00	18	5.55	1.97	1.45
Johnson	8.50	3.99	2.07	1.40	9.42	4.12	2.37	1.57	19	6.17	2.18	1.50
NEH	3.30	1.78	0.98	0.72	2.84	1.46	0.86	0.58	6.85	2.98	1.99	2.75
Palmer	8.64	4.26	2.38	1.58	10	4.47	2.20	1.50	12	6.01	3.00	2.91

Résultats expérimentaux 59

Tableau 3.14 - Résultats des heuristiques Familles F4 et F5 (in = 5)

		F4				F5
n	20	50	100	150	20	50	100	150
H1	6.72	1.18	0.24	0.21	7.44	2.85	1.21	0.91
H2	8.40	4.98	3.51	2.12	8.35	3.66	1.96	1.27
H3	3.73	1.98	0.70	0.47	4.98	3.01	1.11	0.86
H4	6.16	2.14	1.10	0.77	8.35	3.70	2.01	1.30
H5	4.82	1.76	0.88	0.58	6.48	3.90	2.14	1.66
H6	9.61	2.79	1.07	0.65	6.88	2.76	1.12	0.85
H7	7.07	3.46	1.75	1.27	10.04	4.63	2.57	1.65
Johnson	11.20	5.36	2.95	2.04	14.47	7.11	3.51	2.39
NEH	5.22	2.43	1.28	0.84	4.33	2.32	1.13	0.80
Palmer	8.83	3.34	1.54	1.13	11.13	4.94	2.58	1.78

Tableau 3.15 - Résultats des heuristiques, Familles F1, F2 et F3 (in = 10)

		F1				F2				F3
n	20	50	100	150	20	50	100	150	20	50	100	150
H1	1.03	0.21	0.09	0.04	1.76	0.47	0.11	0.08	20.76	10.80	3.87	2.95
H2	7.87	3.00	1.05	0.64	6.74	2.35	0.83	0.35	22.38	20.41	11.78	13.49
H3	3.67	1.53	0.80	0.47	5.43	1.90	0.63	0.39	6.41	6.44	2.48	2.56
H4	5.78	2.45	1.28	0.87	7.76	2.52	1.37	0.93	6.70	6.15	2.30	2.45
H5	3.00	1.13	0.65	0.58	3.03	1.21	0.90	0.62	18.28	9.79	3.30	2.76
H6	1.07	0.19	0.08	0.03	1.68	0.40	0.11	0.05	24.70	18.09	8.12	6.18
H7	0.99	0.13	0.05	0.01	1.72	0.13	0.01	0.00	20.26	12.54	3.50	2.18
Johnson	8.50	3.99	2.07	1.40	9.42	4.12	2.37	1.57	23.25	12.84	3.74	2.57
NEH	3.10	1.78	0.97	0.72	2.83	1.45	0.85	0.57	3.90	4.18	1.67	2.71
Palmer	8.64	4.26	2.38	1.58	10.65	4.47	2.20	1.50	8.00	7.20	2.80	2.88

Résultats expérimentaux 60

Tableau 3.16 - Résultats des heuristiques Familles F4 et F5 (m = 10)

		F4				F5
n	20	50	100	150	20	50	100	150
H1	5.20	0.66	0.17	0.12	6.69	2.07	0.63	0.42
H2	7.24	3.84	2.31	1.44	7.96	3.24	1.80	1.19
H3	3.58	1.41	0.59	0.39	4.84	2.15	1.01	0.69
H4	5.56	1.82	1.00	0.71	7.96	3.28	1.85	1.23
H5	3.89	1.44	0.83	0.48	5.07	2.21	1.43	0.96
H6	6.07	2.19	0.54	0.32	5.93	1.74	0.56	0.40
H7	6.75	2.85	1.60	1.17	10.04	4.49	2.49	1.59
Johnson	10.70	4.83	2.75	1.91	14.32	6.63	3.43	2.39
NEH	3.31	1.55	0.96	0.64	3.29	1.77	0.81	0.61
Palmer	8.39	3.04	1.53	1.12	11.13	4.94	2.58	1.78

En se basant sur les tableaux précédents, on peut évaluer les heuristiques qu'on a testépour en tirer les plus performantes.

Pour les familles d'instances F1 et F2, m E {5,10} et pour toutes les tailles des problèmes (20, 50,100 et 150 jobs) on remarque que les heuristiques H1, H6 et H7 on étéles meilleures parmi les dix heuristiques implémentées. Pour les familles F3 et F4 on remarque une diversification des heuristiques en passant de m = 5 à m = 10, en effet pour m = 5 les meilleures heuristiques étaient H1, H3, H4, H5 et NEH pour n E {20, 50}, pour n E {100,150} on constate l'apparition des heuristiques H7 et Johnson.

Pour la famille F5, les meilleurs heuristiques sont H1, H3, H5, H6, H7 et NEH.

Les Tableaux 3.17 et 3.18 illustrent les meilleurs heuristiques par famille d'instances pour m = 5 et m = 10.

Tableau 3.17 - Meilleurs heuristiques pour m = 5

	H1	H2	H3	H4	H5	H6	H7	Jonhson	NEH	Palmer
F1	X					X	X
F2	X					X	X
F3			X	X	X		X		X
F4	X		X		X				X
F5	X		X		X	X	X		X

Résultats expérimentaux 61

Tableau 3.18 - Meilleurs heuristiques pour m = 10

	H1	H2	H3	H4	H5	H6	H7	Jonhson	NEH	Palmer
F1	X					X	X
F2	X					X	X
F3			X	X			X	X	X
F4	X		X		X	X			X
F5	X		X		X	X			X

Les tableaux précédents indiquent les meilleures heuristiques (dont l'écart avec la borne inférieure BI est faible par rapport autres heuristiques). En effet, on constate que l'adaptation de la règle de Johnson à notre problème a ététrès efficace notamment pour les familles F1 et F2 oùles heuristiques H1 et H6 et H7 avaient les écarts les plus faibles.

En revanche, pour les familles F3, F4 et F5 on constate que l'heuristique NEH avait l'écart le plus faible et cela pour presque toutes les tailles des problèmes.

Par ailleurs, la différence entre les tests effectués avec un nombre de machine au second étage m = 5 et m = 10 n'était pas très considérable d'oùle choix qu'on fait était le même pour ces deux valeurs.

En se basant sur ces résultats on va sélectionner sept heuristiques afin de fournir les solutions de départ pour les méta-heuristiques. Notre choix s'est portésur les heuristiques H1, H3, H4, H5, H6, H7 et NEH.

Résultats expérimentaux 62