Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE MINISTERE DE L’ENSEIGNEMENT SUP

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE Université Mohamed Boudiaf de M’sila Faculté des Mathématiques et de l’Informatique Département des Mathématiques Mémoire de Master Domaine : Mathématiques et Informatique Filière : Mathématiques Option : Analyse Mathématique et Numérique Thème Etude d’un problème d’ordonnancement avec des exemples Présentée par : LEBOUKH Amira Devant le jury composé de : Dr SELT Omar MCA Université Mohamed Boudiaf de M’sila Encadreur Dr GAGUI Bachir MCA Université Mohamed Boudiaf de M’sila Président Dr DILMI Mustapha MCB Université Mohamed Boudiaf de M’sila Examinateur Année universitaire 2019/2020 Remerciement Ce mémoire marque une étape très importante dans ma vie couronnant mes années d’études universitaires, je voudrais remercier ici les personnes qui m’ont accompagné au cours de mon parcours, et qui ont participé de prés ou de loin à la réalisation de ce projet Je remercie avant tout Allah, tout puissant pour la volonté, la santé et la patience qu’il j’ai donnée durant toutes ces langues années d’études afin que je peux arriver à ce stade En second lieu, je tiens à remercier le professeur SELT Omar mon encadreur pour son encadrement, disponibilité et patience, Aussi je les remercie pour son encouragement, conseils et orientations et pour son soutien tout au long de cette période Un grand Mercie à mes parents qui m’ont données la chance de pour suivre mes études et qui m’ont appris à surpasser les moments difficiles Enfin, je ne oublie pas de remercier mes chères amies et mes collègues et à toutes les personnes qui auront contribué de prés ou de loin à l’élaboration de ce mémoire ainsi qu’un la réussite de cette formidable année universitaire Dédicace Mon voyage universitaire s'est terminé Après la fatigue et les epreuves, et aujourd’hui je Termine mes recherches de fin d'études Avec toute la vigueur et l'activité Je dédie ce mémoire A ma très chère ma Mère pour tout le courage et l’amour et le patience qui ma donnée durant tout cette période et qui ma supporter et mon père Pour son effort et son soutien et Encouragement A mes frères et ma sœur A mes amies qui m’ont soutenu et aidé et tous ceux qui ont participé à ce travail Introduction générale : Les mathématiques sont une science très large qui contient de nombreuses difficultés et concepts et qui développe encore à ce jour, et parmi les concepts que les scientifiques étudient encore L’ordonnancement et ses problèmes. Les problèmes d’ordonnancement formulés en problèmes d’optimisation sont souvent classées NP –Difficiles, en particulier ceux liés aux systèmes de production la résolution de tels problèmes nécessitent des méthodes dédiées, tandis que les méthodes exactes ne peuvent pas résoudre ce types de problème vu le temps de calcul énorme les méthodes approchées offrent la possibilité de trouver une solution réalisable en un temps raisonnable. Parmi les méthodes approchées les plus utilisées pour la résolution des problèmes NP-Difficiles on trouve les méta heuristiques. Durant des années plusieurs méta heuristiques ont été construits et appliquées pour la résolution de tels problèmes Mon travail est composé de 3 chapitres : Le premier chapitre est consacré la présentation des notions générales liées à mon travail, j’ai apprendre ce que cela signifie L’ordonnancement et leur fonctions techniques de l'industrie et on va expliquer les données d’un problème d’ordonnancement et leur classification. Le deuxième chapitre a pour but d’introduire les méthodes de résolutions des problèmes L’ordonnancement, commençant par les méthodes approchés allant aux heuristiques et méta heuristiques, avec la présentation des principes et des algorithmes de certaines techniques. Le troisième chapitre est une présentation générale sur quelques types des problèmes d’ordonnancement. Je finirais ce document par une conclusion générale qui résumé les différents phases de travail et ouvre la porte devant certaines perspectives Table des matières 1 Génnéralité sur l’ordonnancement 3 1.1 introduction : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 déﬁnition : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 L’Ordonancement dans l’etude : . . . . . . . . . . . . . . . . . . 4 1.2.2 L’Ordonancement dans la production : . . . . . . . . . . . . . . . 4 1.2.3 L’Ordonancement dans la maintenance : . . . . . . . . . . . . . . 5 1.3 Mission de l’ordonancement : . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Les trois étapes de l’ordonancement : . . . . . . . . . . . . . . . . . . . . 5 1.4.1 la planiﬁcation : . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4.2 L’exécution : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4.3 Le controle : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Analyse de temps en maintennance : . . . . . . . . . . . . . . . . . . . . 6 1.5.1 préparation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5.2 Ordonnancement : . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5.3 intervention : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 Les données d’un problème d’ordonnancement : . . . . . . . . . . . . . . 6 1.6.1 Les tâches : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6.2 Les ressources : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.6.3 Les contraintes : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.6.4 les critéres ( fonction objectif) : . . . . . . . . . . . . . . . . . . . 9 1 1.7 Classiﬁcation des problèmes d’ordonnancement : . . . . . . . . . . . . . 11 1.7.1 ordonnancement admissible : . . . . . . . . . . . . . . . . . . . . 11 1.7.2 ordonnancement semi-actif : . . . . . . . . . . . . . . . . . . . . . 11 1.7.3 ordonnancement actif : . . . . . . . . . . . . . . . . . . . . . . . 12 1.7.4 ordonnancement sans délais : . . . . . . . . . . . . . . . . . . . . 12 1.8 Notion de complexité de problèmes : . . . . . . . . . . . . . . . . . . . . 12 1.8.1 La classe NP : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.8.2 La classe P : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.8.3 La classe NP-Complet : . . . . . . . . . . . . . . . . . . . . . . . 13 1.8.4 La classe NP-Diﬃcile : . . . . . . . . . . . . . . . . . . . . . . . . 14 1.9 Problème d’optimisation : . . . . . . . . . . . uploads/Litterature/ memoire-fin-d-x27-etude-leboukh-amira.pdf