SCOOP

• Titre : Somme coloration minimale et applications

• Responsable : Aziz Moukrim

• Type : Projet Régional

• Dates : 2007-2011

Résumé :

L’optimisation du fonctionnement des systèmes logistiques constitue un enjeu majeur dans notre société. Dans le cadre de ce projet, nous nous intéressons aux problèmes de planification sous contraintes de charges. Lors de précédentes collaborations entre l’équipe de Compiègne et l’équipe d’Amiens, nous avons acquis de réelles compétences sur certains problèmes de gestion de ressources en travaillant précisément sur des problèmes de gestion de personnels en collaboration avec un Centre d’Appels amiénois (Coriolis Service) et un établissement d’enseignement privé amiénois (La Providence). Les problèmes de planification d’emploi du temps sous contraintes de charges comme certains problèmes d’ordonnancement peuvent être modélisés par un problème central en Optimisation Combinatoire, la coloration de graphe.

Une extension de ce problème (somme coloration pondérée minimale) permet de modéliser de nouveaux problèmes de planification (Bar-Noy, Shachai, Tamir, 1996) (Salavatipour, 2003). D’autres applications comme l’allocation de fréquences en téléphonie mobile, l’affectation de vols en plannings aériens, l’ordonnancement de processus, l’analyse d’images médicales, etc, peuvent être modélisés par ces problèmes de coloration.

La difficulté de résolution augmente de manière exponentielle en fonction de la taille des instances, ce qui signifie qu’il n’existe pas de méthode exacte efficace, quelle que soit la configuration des données initiales, et que de nombreuses procédures de résolution restent à explorer. Nous souhaitons dans le cadre de ce projet poursuivre nos travaux de recherches sur ce problème central en optimisation combinatoire et l’étude de ses applications.