Proposition de th
Forum 'Emplois' - Sujet créé le 2007-06-19
/Proposition de thèse/
Somme coloration pondérée et applications, problèmes d'ordonnancement et planification sous contraintes de charges.
Il s'agit d'étudier quelques extensions du problème de coloration de graphe (comme la somme coloration pondérée) ainsi que les applications concernant les problèmes de planification sous contraintes de charge. L'idée majeure du projet est d'étendre les méthodes de résolution que nous avons développées pour le problème central de coloration et d'adapter notre méthodologie de résolution des problèmes d'optimisation combinatoire.
Nous procéderons d'abord à une étude bibliographique complémentaire pour bien situer le problème traité par rapport à d'autres extensions du problème de coloration de base. Bien que les résultats des premiers algorithmes testés dans le cadre d'une étude préliminaire sont très encourageants, ils montrent que seules des familles particulières de graphes sont résolues efficacement (qualité des bornes supérieures par rapport aux bornes inférieures). Il s'agira de proposer de nouvelles techniques d'évaluation et des schémas de branchement efficaces dans le cadre des procédures de séparation et évaluation. Notre objectif est de proposer ensuite des approches hybrides où les procédures de séparation et évaluation intègrent des évaluations heuristiques. Ensuite, il s'agira d'identifier des cas particuliers où le problème peut être résolu de manière optimale. Le travail sera validé sur des instances classiques de la littérature qui proviennent du problème de coloration mais aussi de différentes applications. En parallèle, nous poursuivrons notre étude d'un problème de planification sous contraintes de charge qui émane d'un centre d'appels.
Profil : Recherche Opérationnelle, Informatique.
Financement : bourse Région Picardie.
Laboratoire de rattachement : Heudiasyc/UTC.
Encadrement : Yu LI (LaRIA/UPJV) et Aziz MOUKRIM (Heudiasyc/UTC).
La candidature (CV détaillé, lettre de motivation, résultats et classements, etc.) est à envoyer à Aziz.Moukrim@utc.fr
--
------------------------------------------
Aziz MOUKRIM
Université de Technologie de Compiègne
HeuDiaSyC, UMR CNRS 6599
Génie Informatique, BP 20529
60205 Compiègne cedex France
Tel: 33 (0)3 44 23 49 52
Fax: 33 (0)3 44 23 44 77
E-mail Aziz.Moukrim@utc.fr
http://www.hds.utc.fr/~moukrim
------------------------------------------
Somme coloration pondérée et applications, problèmes d'ordonnancement et planification sous contraintes de charges.
Il s'agit d'étudier quelques extensions du problème de coloration de graphe (comme la somme coloration pondérée) ainsi que les applications concernant les problèmes de planification sous contraintes de charge. L'idée majeure du projet est d'étendre les méthodes de résolution que nous avons développées pour le problème central de coloration et d'adapter notre méthodologie de résolution des problèmes d'optimisation combinatoire.
Nous procéderons d'abord à une étude bibliographique complémentaire pour bien situer le problème traité par rapport à d'autres extensions du problème de coloration de base. Bien que les résultats des premiers algorithmes testés dans le cadre d'une étude préliminaire sont très encourageants, ils montrent que seules des familles particulières de graphes sont résolues efficacement (qualité des bornes supérieures par rapport aux bornes inférieures). Il s'agira de proposer de nouvelles techniques d'évaluation et des schémas de branchement efficaces dans le cadre des procédures de séparation et évaluation. Notre objectif est de proposer ensuite des approches hybrides où les procédures de séparation et évaluation intègrent des évaluations heuristiques. Ensuite, il s'agira d'identifier des cas particuliers où le problème peut être résolu de manière optimale. Le travail sera validé sur des instances classiques de la littérature qui proviennent du problème de coloration mais aussi de différentes applications. En parallèle, nous poursuivrons notre étude d'un problème de planification sous contraintes de charge qui émane d'un centre d'appels.
Profil : Recherche Opérationnelle, Informatique.
Financement : bourse Région Picardie.
Laboratoire de rattachement : Heudiasyc/UTC.
Encadrement : Yu LI (LaRIA/UPJV) et Aziz MOUKRIM (Heudiasyc/UTC).
La candidature (CV détaillé, lettre de motivation, résultats et classements, etc.) est à envoyer à Aziz.Moukrim@utc.fr
--
------------------------------------------
Aziz MOUKRIM
Université de Technologie de Compiègne
HeuDiaSyC, UMR CNRS 6599
Génie Informatique, BP 20529
60205 Compiègne cedex France
Tel: 33 (0)3 44 23 49 52
Fax: 33 (0)3 44 23 44 77
E-mail Aziz.Moukrim@utc.fr
http://www.hds.utc.fr/~moukrim
------------------------------------------