COLORATION DE GRAPHES MIXTES ET SON APPLICATION A L’ORDONNANCEMENT JOB SHOP Report as inadecuate




COLORATION DE GRAPHES MIXTES ET SON APPLICATION A L’ORDONNANCEMENT JOB SHOP - Download this document for free, or read online. Document in PDF available to download.

1 CTDA - Centre de Développement des Technologies Avancées 2 Université des Sciences et de la Technologie Houari 3 LCOMS - Laboratoire de Conception, Optimisation et Modélisation des Systèmes

Résumé : Dans ce papier, nous nous intéressons au problème d’ordonnancement d’atelier job-shop en considérant que toutes les opérations ont des durées unitaires, et à sa réduction à un problème de coloration de graphes. Nous modélisons le problème par la recherche de la coloration optimale d’une classe spéciale de graphes mixtes, où le graphe partiel engendré par les arcs représente une union de chemins et le graphe partiel engendré par les arêtes représente une union de cliques. Le problème étant NP-difficile, son étude nous a menés à la proposition de deux méthodes de résolution exacte et approchée et d’une borne inférieure pour le nombre chromatique mixte. La méthode exacte est basée sur la formulation mathématique sous forme d’un programme linéaire en variables mixtes. L’approche heuristique est basée sur l’algorithme du recuit simulé adapté pour la coloration du graphe mixte. Les résultats des expérimentations réalisées, en utilisant des Benchmarks adaptés de la littérature et des instances générées, montrent l’efficacité du programme linéaire, justifient également l’efficience de l’algorithme du recuit simulé et attestent de la qualité de la borne inférieure.

Mots-clés : Coloration de graphes mixtes Ordonnancement job-shop Nombre chromatique mixte Makespan





Author: Ahmed Kouider - Hacene Ait Haddadene - Samia Ourari - Ammar Oulamara -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents