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

Conclusion

Ce chapitre a portésur les méthodes de résolution retenues pour notre problème. En effet, nous avons adoptécinq bornes inférieurs qui serviront de repère pour l'évaluation des résultats des différentes procédures qu'on a implémenté. Nous avons aussi adaptédes heuristiques spécifiques inspirées de la littérature, ensuite nous avons présentéles notions de bases des méta-heuristiques ainsi que les procédures qu'on a retenues à savoir la recherche taboue et le Recuit Simulé.

Chapitre 3

Résultats expérimentaux

Résultats expérimentaux 44

Introduction

Après avoir présentéles différentes méthodes de résolution qu'on a adoptées pour le problème considéré, ce chapitre se focalise sur le paramétrage des ces méthodes et l'analyse des résultats expérimentaux. Nous décrivons d'abord les familles d'instances pour les tests qu'on a effectués, ensuite nous présentons les choix des paramètres pour les méta-heuristiques, enfin nous exposons et interprétons les résultats expérimentaux.

3.1 Génération des instances tests

Afin de tester les différentes heuristiques ainsi que les méta-heuristiques qu'on a implémentées, nous avons générédes instances aléatoires appartenant à des classes différentes, oùchaque classe contient quatre tailles (n = 20, 50, 100 et 150). pour chaque taille, 20 instances ont étégénérées et les jobs sont, tant que possible, équitablement divisées entre les différents types de jobs. Le nombre des machines au deuxième étage in E {5, 10} .

Les temps opératoires des différents jobs suivent une distribution uniforme. Dans la famille F1 et la famille F2, les temps opératoires a et b , les dates disponibilitér et les délais de livraison q sont générés dans les mêmes intervalles : [1, 20] pour F1 et [1, 100] pour F2.

Pour la famille F3, les temps opératoires sur la machine M_c, les dates r et les délais q sont générés dans [1, 100], et les durées opératoires sur les machines dédiées dans [1, in x 100].

Dans les familles F4 et F5, les temps opératoires sur la machine M_c, les dates r et les délais q sont générés dans [1, 20], mais les temps opératoires sur les machines du deuxième étage sont générés dans [20, 40] pour la famille F4, et pour la famille F5 elle prennent toujours les valeurs des temps opératoires a sur la machine commune M plus un temps supplémentaire 'y = 10 (a + 'y). Ainsi, pour les deux premières familles, les temps opératoires ont les mêmes ordres de grandeur, quant à F3, F4 et F5, les temps opératoires sur les machines dédiées sont plus importants que ceux sur M_c, ce qui tend à équilibrer la charge globale sur les différentes machines.

L'ensemble des familles générées, est résumédans le tableau 3.1.

Résultats expérimentaux 45

Tableau 3.1 - Familles des instances tests

Famille	r	a	b	q
F1	[1,20]	[1,20]	[1,20]	[1,20]
F2	[1,100]	[1,100]	[1,100]	[1,100]
F3	[1,100]	[1,100]	[1,m × 100]	[1,100]
F4	[1,20]	[1,20]	[20,40]	[1,20]
F5	[1,20]	[1,20]	a + 10	[1,20]

Tous les tests qu'on a effectués ont étéfait sur ces cinq familles d'ins-tances avec 20 instances pour chaque famille, quatre tailles différentes des problèmes : n E {20, 50, 100, 150} et deux valeurs pour les machines dédiées m E {5,10}.

Résultats expérimentaux 46