Pôle 2 POOPT

Pôle : Problèmes Opérationnels : Ordonnancement, Planification, Transport (POOPT)

  • Ordonnancement Déterministe

  • Ordonnancement On Line

  • Lot Sizing

  • Modèles de Gestion de Production

  • Tournées de Véhicules

  • Services de Mobilité Innovante

  • Optimisation de Procédés : Placement, Découpe…

  • Planification sur architectures Cloud Computing, GPGPU, Réseaux Informatiques…

Tendances et Priorités Scientifiques

Les grandes tendances et enjeux scientifiques pour le pôle POOPT du GDR RO tendent à être impulsées par les applicatifs. Parmi ceux-ci, on évoquera les champs suivants, sur lesquels le GDR RO s’efforcera de mettre l’accent (là encore, on pourra constater la présence anticipative de ces thèmes dans nombre de projets soutenus par le GDR RO entre 2007 et 2012):

  • Les applications de la R.O.au management de l’Energie.

Celui-ci induit grande diversité de problèmes de natures différentes (pilotage technique et opérationnel de systèmes de production de l’Energie, planification moyen terme et long terme, gestion des systèmes, modélisation des marchés, etc.). Toutes les énergies sont concernées, qu’il s’agisse du pétrole, du gaz, de l’électricité ou des nouvelles formes d’énergie. L’optimisation peut porter sur l’amélioration du fonctionnement des réseaux énergétiques existants, sur la gestion de l’énergie dans les grilles de calcul, ou encore sur la gestion thermique de grands bâtiments. Elle tend alors, au plan des méthodes, à mettre en jeu de grands réseaux dynamiques ou temporisés, dont la gestion algorithmique est complexe. La gestion des ressources énergétiques est portée par une préoccupation de société et il n’existe plus aujourd’hui d’entreprise utilisant des Data Centers qui n’affiche pas cette préoccupation. Notons que si ces préoccupations peuvent conduire à minimiser la consommation énergétique, elles peuvent aussi pousser à l’augmenter (pour produire de l’eau chaude par exemple). Le développement des énergies renouvelables peut également donner lieu à des études où la R.O. pourrait apporter des éléments d’aide à la décision, qu’il s’agisse de décisions de nature stratégique ou opérationnelle.

  • La prise en compte, dans les modèles de planification, de la notion de Durabilité.

En rapport avec la gestion d’énergie, le développement durable est aussi un domaine d’application de la R.O. très en vogue dans les pays anglo-saxons. Par exemple, comment prendre en compte les problèmes économiques et environnementaux dans la planification de la production, comment maximiser la production, tout en réduisant les émissions de gaz, et en minimisant les consommations de ressources ? Sur ce sujet du développement durable, Microsoft Research, l’Institut des sciences et technologies de l’information et de l’ingénierie (INS2I) du CNRS et l’Ecole Polytechnique ont mis en place une chaire intitulée Optimisation et Développement Durable. L’équipe en charge d’ODD réunit à la fois des spécialistes du développement durable et des chercheurs en optimisation.

  • Le pilotage de grands systèmes informatiques distribués, gérant de très grandes masses de données (Cloud Computing, réseaux de capteurs, Big Data, …). Les problèmes induits combinent des questions relatives au dimensionnement, à l’optimisation des ressources et à l’ordonnancement/routage, avec des critères et contraintes très spécifiques, liées à la Fiabilité et à la gestion de l’Energie. Certains sujets sont d’ores et déjà très abordés :

    • Ordonnancement dans le HPC (High Performance Computing) : le sujet est traité depuis de nombreuses années mais on intègre aujourd’hui de nombreuses contraintes supplémentaires comme la prise en compte des aléas, ou des coprocesseurs, l’intégration de plusieurs clusters au sein d’un gestionnaire commun (mise en place de files d’attentes communes et le traitement du problème posé par leurs interférences avec les files d’attentes locales à chaque cluster), etc.

    • L’affectation de serveurs virtualisés (Cloud Computing) : le problème d’affectation sur des serveurs (“Consolidation Server Problem“) est traité intensément depuis une dizaine d’années. Cette problématique correspond à un besoin concret : les loueurs d’infrastructures permettent à leurs clients de démarrer à la demande des machines virtuelles plus ou moins gourmandes en ressources. Les premières solutions ne se préoccupaient que des ressources processeurs. On aborde aujourd’hui des problèmes plus fins en tenant compte des différentes ressources des machines (cpu, ram, I/O, co-processeur, …).

    • Le Big Data : la problématique du traitement rapide de gros volumes de données (plusieurs Téra octets) va croitre dans les prochaines années. Elle intéresse à la fois les spécialistes de Bases de Données et les administrateurs systèmes. Différentes disciplines doivent alors collaborer pour construire une architecture matérielle et logicielle optimale pour le traitement spécifique de données d’une entreprise.

    • La conception d’architectures dédiées : La démarche des gestionnaires de Data Centers a consisté jusqu’ici à assembler des machines “standards” (i.e. des machines serveurs, plus ou moins gonflées). On constate aujourd’hui de nombreux travaux des constructeurs en association avec ces entreprises pour la conception d’infrastructures spécifiques à un traitement donné. La Recherche Opérationnelle intervient alors pour apporter des solutions à l’élaboration de logiciels dédiés à l’utilisation la plus efficace de cette architecture. Les outils habituels, construits pour des architectures standards s’avèrent en effet efficaces, et l’on assiste par ailleurs à une montée en force de la préoccupation énergétique, liée au très fort besoin en dispositifs de refroidissement de ces architectures.

  • Le pilotage de systèmes de mobilité et transport innovants : un des problèmes centraux et historiques en distribution de marchandises et, de façon générale en logistique, est le problème de tournées de véhicules (PTV), ou Vehicle Routing Problem selon la terminologie anglaise. Ce problème consiste à déterminer un ensemble optimal de circuits de distribution ou de ramassage à partir d’un ou plusieurs dépôts afin de desservir un ensemble de clients ou de fournisseurs. Plus qu’un problème unique, le PTV constitue une classe de problèmes, en constante mutation. En effet, l’évolution des contextes et des technologies (Internet, géolocalisation, communications mobiles ou embarquées, Impact des préoccupations énergétiques ou environnementales…) induisent un renouvellement permanent de cette classe de problèmes et en font sa richesse. Le PTV est l’objet d’un intérêt sans cesse renouvelé aussi bien de la part des éditeurs de logiciels que de celle des chercheurs. Dans son survol bisannuel de l’offre logicielle pour le PTV, l’article de « OR-MS Today » d’INFORMS, la société américaine de recherche opérationnelle, comparait une quinzaine de solutions et mettait en avant les nouveaux services liés à l’intégration de bases de données de traffic et aux terminaux mobiles sous smartphones. La communauté de recherche dans ce domaine est très active tant au niveau national qu’au niveau international. Ainsi le prochain congrès de la ROADEF ne comptera pas mois de 9 sessions invitées consacrées au PTV.

L’étude algorithmique du PTV relève, dans sa version statique, de l’Optimisation Combinatoire. Toutefois un point essentiel tient au caractère dynamique et globalement incertain des systèmes réels, qui confère aux modèles de décision et évaluation sous-jacents une texture très spécifique. Si, par le passé, focus a été mis sur le traitement statique, exact ou très finement approché, de problèmes de grandes tailles, des versions plus complexes sont à présent abordées, qui intègrent davantage la dynamicité de ces systèmes et la possibilité de contrôle qu’offrent les récentes avancées technologiques. On mettra plus particulièrement l’accent dans les années à venir, au niveau du GDR R.O, sur les points suivants :

  1. Résoudre des PTV « encapsulés » d’un point de vue de la chaîne logistique: Il s’agit ici de considérer des variantes dans lesquelles le PTV apparaît comme sous-problème d’un problème logistique plus global. Cette classe d’extension du PTV reste très largement à défricher.

  2. Résoudre des variantes riches du PTV : de telles variantes sont des versions du PTV où un nombre important de contraintes hétérogènes sont considérées simultanément. Plus proches de la réalité, les solutions méthodologiques efficaces pour traiter de telles variantes ne sont encore pas bien maîtrisées.

  3. Considérer des variantes stochastiques du PTV : le PTV est défini comme un problème déterministe. Toutefois, les paramètres sont le plus souvent stochastiques surtout lors d’une planification tactique. Les travaux dans ce domaine, s’ils existent, sont encore aujourd’hui trop peu nombreux.

  4. Considérer des variantes dynamiques ou collaboratives du PTV, associés à de nouveaux services de mobilité réactifs ou collaboratifs (co-voiturage, véhicule partagé, transport à la demande…)

  • Les problèmes de planification liés au management de l’Hôpital et du Système de Santé. Celui-ci recèle une grande diversité de processus de décision qui interpellent le spécialiste de Recherche Opérationnelle et d’Aide à la Décision. Que ce soit au regard de l’objectif d’efficacité (progression de la qualité des soins) ou de l’efficience (assurer la mission au moindre coût), de nombreuses améliorations sont possibles. Plusieurs travaux ont déjà démarré ponctuellement dans le secteur hospitalier sur des problématiques d’optimisation de flux (flux logistiques, circuits de stérilisation, flux de patients, …) ou d’optimisation de ressources (gestion des blocs opératoires, planification du personnel, …). Des collaborations ont aussi vu le jour avec des associations par exemple liées à l’Hospitalisation à Domicile (définition des tournées, …). Sur le plan décisionnel et organisationnel dans le système de santé, la Recherche Opérationnelle et l’Aide à la Décision ont énormément à apporter. Les retombées dans ce domaine peuvent avoir un fort impact au niveau du confort du patient ou du personnel de santé, au niveau de la qualité des soins, mais aussi sur un plan purement économique.

Si les applicatifs tendent à fixer le tempo dès lors qu’il s’agit d’identifier les grandes tendances scientifiques au niveau de cet pôle du GDR, certaines problématiques de nature fondamentales se font jour, dont l’étude sera a priori impulsée au niveau du GDR :

    • La prise en compte de l’incertitude (notion de robustesse) ;

    • La prise en compte de la dynamicité et l’intégration des méthodes de R.O. au sein de systèmes fortement robotisés (véhicules autonomes .. .) ;

    • Les défis posés par le besoin d’intégration et de généricité : les logiciels propres aux applicatifs OPT sont le plus souvent complexes, et doivent être régulièrement adaptés aux changements de contextes. Par ailleurs, les gains en capacité des ordinateurs et des systèmes d’information tendent à rendre davantage possible l’intégration, au sein d’un seul modèle, de différents niveaux décisionnels (routage et chargement, routage et ordonnancement, tarification et dimensionnement…) Un enjeu concerne alors la mise en évidence de modèles génériques, et la conception de schémas algorithmiques de décomposition qui épousent la structure des processus de décision.

Stratégie.

Dans cette perspective, l’pôle POOPT concentrera une partie de ses actions à venir sur le renforcement de ses groupes de travail et sur l’émergence de nouveaux groupes de travail, correspondant à des tendances scientifiques nouvelles. Il le fera en synergie avec les autres pôles du GDR, avec certains GDR partenaires naturels, tels que, notamment le GDR MACS, et aussi avec la ROADEF, qui parraine certains groupes de travail.

Il cherchera à se définir comme un support de veille technologique et scientifique, ainsi que comme un vecteur de tendances, en termes à la fois scientifiques et socio-économiques. Dans cette perspective, il travaillera en étroite interaction avec les industriels et avec la ROADEF.

Il s’efforcera aussi d’impulser la mise en œuvre de manifestations de proximité (Journées Thématiques…) et d’Ecole Thématiques ciblées sur les jeunes chercheurs et doctorants. Il cherchera enfin, en articulation avec l’ensemble des acteurs du GDR, à promouvoir des liens à l’International avec les pays proches au sein de l’UE et en pointe sur ces problématiques (on pensera à l’Italie, à l’Espagne, à l’Allemagne), ainsi qu’avec le Quebec, (leader sur la problématique « Transport »).