Heuristiques pour les problèmes d'affectation sous contraintes par l'approche de la coloration des sommets d'un graphe

الموضوعات

علوم بحتة وطبيعية

الملخص

Notre travail est donc, une contribution a la resolution des d'affectation sous contraintes. Cependant, notre recherche nous a permis de concevoir une procedure de coloration polynomiale que nous avons P.. Pour quelques graphes ayant certaines propriétés, notre procédure nous permet d’avoir une solution qui converge vers la solution optimale, en l’absence de ces propriétés, les solutions procurées sont d’assez bonnes qualités. Nous avons structuré notre mémoire en cinq chapitres où : Le premier chapitre est consacré essentiellement, aux définitions préliminaires et aux notions les plus utilisées. Nous exposerons, dans celui-ci, des rappels qui seront nécessaires pour la suite. Nous introduirons un certain nombre de notions fondamentales en optimisation combinatoire. On y trouvera en particulier les principaux concepts et résultats, de la théorie des graphes, des heuristiques et des utilisés dans ce travail et enfin les éléments de bases de la théorie de la complexité algorithmique. Dans le second chapitre, nous traiterons les principales méthodes heuristiques et qui peuvent être adaptées à la résolution du problème abordé dans ce mémoire. Nous nous pencherons principalement sur les méthodes tabou, recuit simulé, les algorithmes génétiques et la méthode de colonie de fourmis. Le troisième chapitre sera consacré à l’approche heuristique pour la résolution du problème de la coloration des sommets d'un graphe quelconque, donc les problèmes d’affectation sous contraintes. Deux résultats fondamentaux, seront présentés, un algorithme polynomial de coloration(P. ) et une de coloration tabou et la méthode de colonie de fourmis. Il est important de signaler à ce niveau la particularité de cette heuristique hybride, en terme de rapidité d'exécution, en l’absence des propriétés souhaitables des graphes modélisant les problèmes d’affectation sous contraintes. Le quatrième chapitre est dédié à la caractérisation des graphes d’une classe que nous avons . . Nous établirons une démonstration de la perfection des . , nous donnerons ainsi une justification de façon polynomiale par P. et nous étudierons les relations d'inclusion de cette classe de graphe parfait avec celles déjà existantes

روابط وملفات

التعريف والنوع

رقم الوثيقة

0a36e3c5-f251-4a00-9006-12593514a03a

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل ماجيستير

نوع الملف

word

أسماء الملفات

1377055_1.docx, 1377055_2.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":" Assia Gueham","title_ar":"اعداد","title_en":"Preparation"},{"name_ar":"Ait Haddadene","title_ar":"اشراف","title_en":"Supervision"}]

اللغة

French

المصدر والدورية

اسم المصدر

Heuristiques pour les problèmes d'affectation sous contraintes par l'approche de la coloration des sommets d'un graphe

المحتوى والصفحات

عدد الصفحات

0

كلمات الباحثين

Coloriage de graphes , Graphes, Heuristique, Optimisation combinatoire

إشراف وإعداد

الإشراف

Ait Haddadene

الإعداد

Assia Gueham

الاقتباسات الببليوغرافية