Soutenance d'HDR - Christian Artigues
Forum 'Annonces' - Sujet créé le 2004-11-26 par Christian Artigues
Chers Collègues,
J'ai le plaisir de vous annoncer que je soutiendrai mon habilitation à diriger des recherches
intitulée "Optimisation et Robustesse en Ordonnancement sous Contraintes de Ressources"
le vendredi 3 décembre 2004. Les membres du jury sont :
- Rapporteurs:
Jacques CARLIER, Professeur, Université de Technologie de Compiègne
Willy HERROELEN, Professeur, Université Catholique de Leuven (Belgique)
Stéphane DAUZÈRE-PÉRÈS, Professeur, Ecole des Mines de Saint-Etienne
- Examinateurs:
Philippe CHRÉTIENNE, Professeur, Université de Paris-VI
Marc EL-BÈZE, Professeur, Université d’Avignon et des Pays de Vaucluse
Narendra JUSSIEN, Maître-Assistant – HDR, Ecole des Mines de Nantes
- Membre invité:
François ROUBELLAT, Directeur de Recherche, LAAS-CNRS, Toulouse
La soutenance aura lieu à 14 heures dans l'amphithéatre "Blaise Pascal" de l'IUP
Génie Mathématique et Informatique d'Avignon.
Vous pourrez trouver des indications pour vous y rendre à l'adresse,
http://www.iup.univ-avignon.fr/presentation/plan.html
Vous êtes évidemment conviés au pot qui suivra !
A très bientôt !
Christian Artigues
Christian Artigues, Maître de Conférences
Université d'Avignon / Laboratoire d'Informatique / IUP
BP1228 84911 Avignon Cedex 9 / www.lia.univ-avignon.fr
TEL 04 90 84 35 52 / FAX 04 90 84 35 01
---------------------------------------------------------------------- -------------------------------------------------------
RESUME
---------------------------------------------------------------------- -------------------------------------------------------
"Optimisation et Robustesse en Ordonnancement sous Contraintes de Ressources"
L'ordonnancement consiste à organiser dans le temps l'exécution d'un ensemble de tâches au moyen d'un ensemble de ressources. Ce problème se trouve au coeur de nombreuses problématiques industrielles. En gestion de projet, ordonnancer, c'est déterminer les dates d'exécution des activités constituant le projet.
En informatique, ordonnancer revient à décider de l'ordre d'exécution des processus et de leur attribution à des processeurs parallèles. En gestion de production, l'ordonnancement consiste à déterminer les séquences d'opérations à réaliser sur les différentes machines de l'atelier. Chacun de ces contextes pratiques définit ainsi les caractéristiques propres des tâches et des ressources, le type des décisions à prendre, les modalités d'exécution des tâches par les ressources qui déterminent des contraintes sur les décisions et aussi les différents critères qui mesurent la qualité d'une solution. Un contexte particulier définit en fait un problème d'optimisation combinatoire en termes de variables de décision, de contraintes et de fonction objectif. Nous appelons ainsi problème d'ordonnancement un problème d'optimisation combinatoire dont la solution donne des indications sur les dates de début d'un ensemble de tâches à ordonnancer ou sur des relations d'ordre total ou partiel à respecter dans l'exécution de ces tâches afin de respecter un ensemble de contraintes et/ou d'optimiser une fonction objectif.
Notre contribution à la résolution des problèmes d'ordonnancement évolue selon deux axes.
Le premier axe concerne l'étude et la résolution de nouveaux problèmes d'ordonnancement issus de la prise en compte de l'incertitude sur les données, fréquente en pratique. En ordonnancement, l'incertitude sur les données concerne les durées et les dates de disponibilité des tâches, la présence de tâches imprévues à réaliser, la disponibilité incertaine des ressources. Pour traiter ces incertitudes, notre approche consiste à rester dans le cadre de l'optimisation combinatoire déterministe, mais en faisant intervenir les concepts de flexibilité, de robustesse et de stabilité. Cette approche suppose que des données sont connues au moment où un l'ordonnancement initial est calculé par un premier algorithme, dit statique. Les aléas (ou modification des données) surviennent alors que l'ordonnancement ainsi pré-calculé est partiellement réalisé. Il devient alors nécessaire de calculer rapidement un nouvel ordonnancement compatible avec les nouvelles données avec un second algorithme, dit dynamique. La robustesse mesure alors la capacité du processus d'enchaînement des deux algorithmes à faire face de manière satisfaisante aux aléas. Dans cet objectif de robustesse, nous suivons deux voies distinctes.
La première voie de recherche consiste à proposer des algorithmes dynamiques, dits réactifs ou de réparation, qui adaptent la solution précalculée au changement survenant dans les données. Cette approche définit en fait un nouveau problème d'ordonnancement dont la solution initiale constitue une donnée, associée généralement à des contraintes ou à un objectif de stabilité qui vise à ne pas trop s'éloigner de cette solution initiale. La deuxième voie de recherche, complémentaire avec la précédente, consiste à faire en sorte que la solution initiale proposée par l'algorithme statique contienne a priori suffisament de flexibilité, c'est-à-dire de possibilités de modifications pour faire face aux aléas. Ces contraintes ou objectifs de flexibilité définissent également de nouveaux problèmes d'ordonnancement.
Le second axe concerne l'amélioration des méthodes de résolution exactes et approchées de problèmes d'ordonnancement connus mais NP-difficiles. Nous nous sommes dans ce cadre essentiellement intéressé au problème d'ordonnancement de projet sous contraintes de ressources (RCPSP) et au problème de job-shop avec temps de préparation dépendant de la séquence (SDST-JSP) issus respectivement de la gestion de projet et de la gestion de production.
Notre contribution concerne d'une part la modélisation et l'étude de la structure de ces problèmes afin de proposer des méthodes de résolutions ad-hoc et, d'autre part, la mise en oeuvre de méthodes d'optimisation qualifiées d'hybrides.
En ce qui concerne le premier point, nous étudions pour le RCPSP un modèle de flot qui sert de base à plusieurs méthodes heuristiques, nous déterminons de nouvelles inégalités valides pour renforcer des formulations de programmation linéaire en nombres entiers et nous proposons une nouvelle relaxation lagrangienne. Pour le problème de SDST-JSP, nous déterminons des ensembles dominants de solutions dont nous dérivons des algorithmes constructifs, nous étudions la modélisation par graphe-disjonctif afin d'étendre une méthode tabou proposée pour le job-shop classique et nous étudions également la décomposition du problème en sous-problèmes de voyageur du commerce pour la conception d'une méthode exacte.
Notre étude des méthodes d'optimisation hybrides est appliquée à la résolution du RCPSP. Elle concerne d'une part l'intégration de méthodes exactes et heuristiques au sein de méthodes de grand voisinage, et d'autre part l'étude des interactions et des coopérations possibles entre la programmation par contrainte (PPC) et la programmation linéaire en nombres entiers (PLNE). Dans ce dernier cas, l'objectif est de tirer partie à la fois des avancées de la recherche opérationnelle pour la résolution des PLNE et des mécanismes d'inférence et de résolution intelligente issus de la programmation par contraintes. Nous appliquons différents principes de coopération pour le calcul de bornes inférieures et au sein de méthodes exactes de résolution.
---------------------------------------------------------------------- ------------------------------------------------------
J'ai le plaisir de vous annoncer que je soutiendrai mon habilitation à diriger des recherches
intitulée "Optimisation et Robustesse en Ordonnancement sous Contraintes de Ressources"
le vendredi 3 décembre 2004. Les membres du jury sont :
- Rapporteurs:
Jacques CARLIER, Professeur, Université de Technologie de Compiègne
Willy HERROELEN, Professeur, Université Catholique de Leuven (Belgique)
Stéphane DAUZÈRE-PÉRÈS, Professeur, Ecole des Mines de Saint-Etienne
- Examinateurs:
Philippe CHRÉTIENNE, Professeur, Université de Paris-VI
Marc EL-BÈZE, Professeur, Université d’Avignon et des Pays de Vaucluse
Narendra JUSSIEN, Maître-Assistant – HDR, Ecole des Mines de Nantes
- Membre invité:
François ROUBELLAT, Directeur de Recherche, LAAS-CNRS, Toulouse
La soutenance aura lieu à 14 heures dans l'amphithéatre "Blaise Pascal" de l'IUP
Génie Mathématique et Informatique d'Avignon.
Vous pourrez trouver des indications pour vous y rendre à l'adresse,
http://www.iup.univ-avignon.fr/presentation/plan.html
Vous êtes évidemment conviés au pot qui suivra !
A très bientôt !
Christian Artigues
Christian Artigues, Maître de Conférences
Université d'Avignon / Laboratoire d'Informatique / IUP
BP1228 84911 Avignon Cedex 9 / www.lia.univ-avignon.fr
TEL 04 90 84 35 52 / FAX 04 90 84 35 01
---------------------------------------------------------------------- -------------------------------------------------------
RESUME
---------------------------------------------------------------------- -------------------------------------------------------
"Optimisation et Robustesse en Ordonnancement sous Contraintes de Ressources"
L'ordonnancement consiste à organiser dans le temps l'exécution d'un ensemble de tâches au moyen d'un ensemble de ressources. Ce problème se trouve au coeur de nombreuses problématiques industrielles. En gestion de projet, ordonnancer, c'est déterminer les dates d'exécution des activités constituant le projet.
En informatique, ordonnancer revient à décider de l'ordre d'exécution des processus et de leur attribution à des processeurs parallèles. En gestion de production, l'ordonnancement consiste à déterminer les séquences d'opérations à réaliser sur les différentes machines de l'atelier. Chacun de ces contextes pratiques définit ainsi les caractéristiques propres des tâches et des ressources, le type des décisions à prendre, les modalités d'exécution des tâches par les ressources qui déterminent des contraintes sur les décisions et aussi les différents critères qui mesurent la qualité d'une solution. Un contexte particulier définit en fait un problème d'optimisation combinatoire en termes de variables de décision, de contraintes et de fonction objectif. Nous appelons ainsi problème d'ordonnancement un problème d'optimisation combinatoire dont la solution donne des indications sur les dates de début d'un ensemble de tâches à ordonnancer ou sur des relations d'ordre total ou partiel à respecter dans l'exécution de ces tâches afin de respecter un ensemble de contraintes et/ou d'optimiser une fonction objectif.
Notre contribution à la résolution des problèmes d'ordonnancement évolue selon deux axes.
Le premier axe concerne l'étude et la résolution de nouveaux problèmes d'ordonnancement issus de la prise en compte de l'incertitude sur les données, fréquente en pratique. En ordonnancement, l'incertitude sur les données concerne les durées et les dates de disponibilité des tâches, la présence de tâches imprévues à réaliser, la disponibilité incertaine des ressources. Pour traiter ces incertitudes, notre approche consiste à rester dans le cadre de l'optimisation combinatoire déterministe, mais en faisant intervenir les concepts de flexibilité, de robustesse et de stabilité. Cette approche suppose que des données sont connues au moment où un l'ordonnancement initial est calculé par un premier algorithme, dit statique. Les aléas (ou modification des données) surviennent alors que l'ordonnancement ainsi pré-calculé est partiellement réalisé. Il devient alors nécessaire de calculer rapidement un nouvel ordonnancement compatible avec les nouvelles données avec un second algorithme, dit dynamique. La robustesse mesure alors la capacité du processus d'enchaînement des deux algorithmes à faire face de manière satisfaisante aux aléas. Dans cet objectif de robustesse, nous suivons deux voies distinctes.
La première voie de recherche consiste à proposer des algorithmes dynamiques, dits réactifs ou de réparation, qui adaptent la solution précalculée au changement survenant dans les données. Cette approche définit en fait un nouveau problème d'ordonnancement dont la solution initiale constitue une donnée, associée généralement à des contraintes ou à un objectif de stabilité qui vise à ne pas trop s'éloigner de cette solution initiale. La deuxième voie de recherche, complémentaire avec la précédente, consiste à faire en sorte que la solution initiale proposée par l'algorithme statique contienne a priori suffisament de flexibilité, c'est-à-dire de possibilités de modifications pour faire face aux aléas. Ces contraintes ou objectifs de flexibilité définissent également de nouveaux problèmes d'ordonnancement.
Le second axe concerne l'amélioration des méthodes de résolution exactes et approchées de problèmes d'ordonnancement connus mais NP-difficiles. Nous nous sommes dans ce cadre essentiellement intéressé au problème d'ordonnancement de projet sous contraintes de ressources (RCPSP) et au problème de job-shop avec temps de préparation dépendant de la séquence (SDST-JSP) issus respectivement de la gestion de projet et de la gestion de production.
Notre contribution concerne d'une part la modélisation et l'étude de la structure de ces problèmes afin de proposer des méthodes de résolutions ad-hoc et, d'autre part, la mise en oeuvre de méthodes d'optimisation qualifiées d'hybrides.
En ce qui concerne le premier point, nous étudions pour le RCPSP un modèle de flot qui sert de base à plusieurs méthodes heuristiques, nous déterminons de nouvelles inégalités valides pour renforcer des formulations de programmation linéaire en nombres entiers et nous proposons une nouvelle relaxation lagrangienne. Pour le problème de SDST-JSP, nous déterminons des ensembles dominants de solutions dont nous dérivons des algorithmes constructifs, nous étudions la modélisation par graphe-disjonctif afin d'étendre une méthode tabou proposée pour le job-shop classique et nous étudions également la décomposition du problème en sous-problèmes de voyageur du commerce pour la conception d'une méthode exacte.
Notre étude des méthodes d'optimisation hybrides est appliquée à la résolution du RCPSP. Elle concerne d'une part l'intégration de méthodes exactes et heuristiques au sein de méthodes de grand voisinage, et d'autre part l'étude des interactions et des coopérations possibles entre la programmation par contrainte (PPC) et la programmation linéaire en nombres entiers (PLNE). Dans ce dernier cas, l'objectif est de tirer partie à la fois des avancées de la recherche opérationnelle pour la résolution des PLNE et des mécanismes d'inférence et de résolution intelligente issus de la programmation par contraintes. Nous appliquons différents principes de coopération pour le calcul de bornes inférieures et au sein de méthodes exactes de résolution.
---------------------------------------------------------------------- ------------------------------------------------------