Conclusion
Ce chapitre s'est focalisésur les tests
expérimentaux des méthodes que nous avons adoptées pour la
résolution du problème considéré. Après
avoir justifiéles décisions portant sur le paramétrage des
méta-heuristique, nous avons procédéà des tests
expérimentaux pour les cinq familles d'instances. Nous avons
interprétéles résultats obtenus, puis nous avons
évaluéet com-paréles différentes
méta-heuristiques en se basant sur les résultats des simulations
et enfin nous avons présentéles temps de calculs qu'on a
enregistrés pour chaque famille d'instance.
67
Conclusion générale
Dans ce travail, nous avons traitéun problème
d'ordonnancement de type flow shop hybride avec machines dédiées,
avec dates de disponibilitéet délais de livraison, cette
configuration bien que trouvée dans le milieu industriel,
n'a pas ététraitée dans la
littérature spécialisée. Le type d'atelier
considérése compose de deux étages, le premier
étage comprend une seule machine
commune et le deuxième étage se compose de
in machines dédiées, tous les jobs ont des dates de
disponibilitéauxquels ils rentrent dans l'atelier et des délais
de livraison qui correspondent à des durées à passer avant
de quitter l'atelier. Ce problème est NP-difficile au sens fort, notre
objectifs était la minimisation du temps d'achèvement
(makespan).
Nous avons dresséun état de l'art sur les
problèmes de flow shop en se concentrant sur les méthodes de
résolution approchées tels que les heuristiques
spécifiques, la recherche taboue et le Recuit Simulé. Cette revue
bibliographique nous a permis de constater le manque des travaux traitant cette
configuration malgréla concurrence des techniques d'optimisation et la
rapiditédes calculateurs de nos jours.
En absence d'une approche exacte, nous avons
élaborédes bornes inférieures afin de pouvoir
évaluer les résultats des autres méthodes
approchées. Ces bornes se sont montrées très efficaces en
particulier celle inspirée de l'ordre de Johnson. Des heuristiques
inspirées de celles présentées dans la littérature
ont étéimplémentées et adaptées à
notre problème à savoir les heuristiques de Potts, NEH, Johnson
et Palmer. En effet, après avoir testéces heuristiques nous avons
constatéque les heuristiques qui se basent sur l'ordre de Johnson ou
inspirées de l'heuristique NEH ont donnéles meilleurs
écarts par rapport à la borne inférieure. Ces derniers ont
étéimplémentées avec les méta-heuristiques
retenues (recherche taboue RT et Recuit SimuléRS) pour
leurs fournir les solutions de départ.
Opérant chacune avec une combinaison spécifique
des opérateurs de changement des méthodes de gestion de la liste
taboue, plusieurs variantes de la recherche taboue ont
étécomparées entre elles puis avec le RS, le
constat
Conclusion générale 68
était que la RT est plus performante que
le RS pour le problème considéré. Par ailleurs,
nous constatons que ce problème est facilement soluble pour des familles
d'instances données alors qu'il reste difficile pour d'autres familles,
et que plus la taille des problèmes augmente plus on a des chances pour
trou-
ver une solution optimale. Notons que le temps de calcul
était raisonnable àl'exception des familles d'instance
difficiles qui requièrent un temps de calcul plus important.
Pour des travaux futurs, il serait très intéressant
de développer une procédure par séparation et
évaluation (PSE) afin de mieux évaluer les
méta-heuristiques implémentées. De plus, ces
méta-heuristiques peuvent être testées avec d'autres jeux
de données comportant des familles d'instances différentes de
celles présentées dans ce mémoire. Par ailleurs,
l'élaboration d'heuristiques spécifiques performantes pour ce
problème sera un apport considérable surtout quand il s'agit de
résoudre des familles difficiles sachant que même les approches
exactes ont leurs limites. Finalement, une application réelle de ce
problème sera d'une grande importance et qui nous permettra de se
rapprocher de la réalitéindustrielle.
69
| 
