Résolution D'un Problème Flow Shop Avec Temps De Latence
Résumé: Ce projet consiste à étudier et traiter un problème d'ordonnancement de type flow shop en utilisant des délais de latence. Plusieurs taches sont exécutées sur plusieurs machines selon un cheminement unique, dont l'objectif est de minimiser le makespan. Deux cas peuvent se présenter, le premier cas consiste à traiter un problème portant sur deux machines uniquement (F2), le deuxième cas consiste à généraliser le problème a machine (FM). Pour le premier cas une solution optimale est obtenue immédiatement en se basant sur un algorithme polynomial de Johnson. En ce qui concerne le deuxième cas la solution optimale est obtenue en utilisant une méthode exacte qui explore intelligemment tout l'espace de recherche, et une méthode approchée en explorant uniquement une partie de ce dernier. A propos de la méthode exacte, il s'agit de branch and bound, méthode qui procède par évaluation et séparation progressive (PSE), elle permet de construire une arborescence en se basant sur une énumération guidée jusqu'à l'arrivée à une solution optimale. Elle permet d'éviter de construire certains sous arbres en utilisant les bornes inférieures et supérieures, trouvées précédemment et qui représente le point fort de cette méthode. En ce qui concerne la méthode approchée, nous avons développé une méthode à base de population. Il s'agit d'un algorithme génétique utilisant trois éléments essentiels: une population initiale constituée de plusieurs individus, un mécanisme d'évaluation de chaque individu et un mécanisme d'évolution, composé d'opérateurs de sélection, croissement et de mutation plus une opération d'élitisme. Nous avons utilisé branch and bound pour profiter de ses résultats dans le contrôle de ceux de l'algorithme génétique en jouant sur la diversification et l'intensification" Enfin les résultats expérimentaux qu'on a eus sont vraiment encouragents. Mot clés: ordonnancement, méthode exacte, méthode approchée flow shop, temps de latence, makespan, branch and bound, algorithme génétique.
Mots-clès:
Nos services universitaires et académiques
Thèses-Algérie vous propose ses divers services d’édition: mise en page, révision, correction, traduction, analyse du plagiat, ainsi que la réalisation des supports graphiques et de présentation (Slideshows).
Obtenez dès à présent et en toute facilité votre devis gratuit et une estimation de la durée de réalisation et bénéficiez d'une qualité de travail irréprochable et d'un temps de livraison imbattable!
Aucun fichier associé
Si le fichier est volumineux, l'affichage peut échouer. Vous pouvez obtenir le fichier directement en cliquant sur le bouton "Télécharger".
