Séminaires

Liste des Séminaires MOGISA

2012 

  • Maria Angélica Salazar Aguilar (Universidad Autónoma de Nuevo León, México)  - Vehicle routing problems with synchronization constraints
    Date : 18 janvier 2013 à 10h30 - salle Hourgade  
    In this talk, two problems arising from road maintenance operations will be described. A solution procedure based in the ALNS metaheuristic will be! presented as well as some computational results over a set of artificial instances and a real case from Dieppe City.
  • Leo Liberti (Ecole Polytechnique) - Symmetry in Mathematical Programming
    Date : 2 octobre 2012 à 10h30 - salle Feynman 
    We present techniques for automatically detect symmetries in mathematical programming formulations, and discuss some approaches to exploit them in order to reduce the number of nodes in Branch-and-Bound type algorithms.
  • Shoshana Anily (Tel Aviv University) - Capacity sharing: capacity or labor division? A cooperative game approach
    Date : 7 septembre 2012 à 14h00 - salle Feynman 
    In this talk we discuss two types of capacity sharing approaches to model various service/production system! s as cooperative games with transferrable utility, and we analyze their core.  The literature on cooperative games usually assumes that total capacity is divisible and allocable additively. This premise is reasonable in some settings, but in others it may yield unacceptable solutions. We suggest another approach, which is aligned with the concept of division of labor, where total processing time, rather than total capacity over all resources, is allocated additively.
  • Cyril Briand (LAAS-CNRS, UPS) - Ordonnancement de projet multi-agent : recherche de stratégies efficaces et stables
    Date : 9 mai 2012 à 14h00 - salle Europe 
    Cet exposé s’intéresse à l'organisation de projets coopératifs, où un ensemble d’agents, c! hacun prenant en charge une partie des activités du projet, doivent s’entendre pour mener à bien l'exécution d'un projet pour le compte d'un client. Nous supposons que chaque agent est capable de contrôler la durée de ses activités, et donc d'influencer la durée totale du projet, ces durées étant spécifiées par des intervalles. En outre, lorsque les agents parviennent à finir le projet plus tôt que prévu, le client offre une récompense proportionnelle à la réduction de durée obtenue. Nous supposons que la récompense est partagée entre les agents selon une politique pré-définie par le client. Chaque agent est intéressé par la maximisation de son profit (correspondant à sa part de récompense de laquelle est déduit le coût lié à la réduction de la durée de ses activités). En lien avec l'optimisation multiobjectif et la théorie des jeux, nous nous intéressons aux stratégies de décision des agents et à la politique de partage choisie par le client. Nous montrons en particu! lier que déterminer une stratégie stable (équilibre de Nash) m! inimisan t la durée du projet est un problème difficile et nous proposons un programme mathématique à variables mixtes pour le résoudre. Nous montrons également comment déterminer une politique de partage qui soit la plus favorable pour le client. Plusieurs perspectives d'extension de ce travail seront également décrites.
  • Angel A. Juan (Open University of Catalonia) - Using Biased Randomization and Simulation to solve Stochastic Vehicle Routing Problems
    Date : 6 avril 2012 à 11h15 - salle Europe 

    This seminar discusses a hybrid approach combining randomized heuristics, Monte Carlo simulation (MCS), and parallel computing for solving the Vehicle Routing Problem with Stochastic Demands (VRPSD). Our approach deals with uncertainty in the customer demands by considering safety stocks, i.e. when designing the routes, part of the vehicle capacity is reserved to deal with potential emergency situations caused by unexpected demands. Thus, for a given VRPSD instance, different levels of safety stocks are considered and, for each of these levels, a different scenario is defined. Then, each scenario is solved by integrating MCS inside a heuristic-randomization process. This way, expected variable costs due to route failures can be naturally estimated even when customer demands follow a non-normal probability distribution. Use of parallelization strategies is then considered to run multiple instances of the algorithm in a concurrent way. The resulting concurrent solutions are then compared and the one with the minimum total costs is selected.

  • Alexandre Gondran (ENAC) - Coloration de graphes : méthodes de résolution et applications
    Date : 5 mars 2012 à 14h00 - salle Feynman 

    La coloration de graphe est un problème d'optimisation combinatoire difficile qui compte de très nombreuses applications : emplois du temps, allocation de! fréquence radio, ordonnancement, allocation de registres en informatique,... Je rappellerai dans une première partie le problème, ses variantes et ses applications. Je détaillerai également les principales stratégies et algorithmes utilisés pour le résoudre. Dans une seconde partie, je présenterai mes expériences de coloration dans le trafic aérien et en télécommunications. Je tacherai d'expliquer comment tenir compte des interférences multiples dans les réseaux mobiles c'est-à-dire de contraintes n-aires et in fine la notion de T-coloration d'hypergraphe.

  • Nicolas Jozefowiez (LAAS-CNRS, INSA) - Solution de problèmes multi-objectif : Principes et nouvelles méthodes
    Date : 16 Janvier 2012 à 10h30 - salle Bardeen 

    Dans une première partie de cette présentation, les concepts clefs de l'optimisation mult! iobjectif seront présentés. Des approches existantes types seront présentées dans cette partie. Les motivations pour l'étude de problèmes multiobjectif seront aussi discutées ainsi qu'une manière d'utiliser ces méthodes pour résoudre des problèmes complexes et de grandes tailles malgré la difficulté intrinsèque des problèmes multiobjectif. Dans la seconde partie, des méthodes originales et nouvelles seront décrites. Ces méthodes illustrent les points de recherche actuels dans l'optimisation multiobjectif telle que l'optimisation basée sur la recherche d'ensembles ou la définition de méthodes exactes. Plus précisément deux méthodes seront présentées : un algorithme génétique et un algorithme de séparations et coupes.

2011 
  • Gilles Simonin (LAAS-CNRS) - Impact de la contrainte d’incompatibilité sur la complexité et l’approximation des problèmes d’ordonnancement en présence de tâches-couplées
    Date : 13 décembre 2011 à 9h45 - salle Feynman 
    Depuis quelques années les véhicules sous-marins autonomes sont en plein essor, les torpilles sous-marines d'exploration en sont le parfait exemple. Les roboticiens du Lirmm travaille sur un modèle de torpille nommé TAIPAN. Cette torpille a pour objectif d'exécuter deux types de tâches : celles d'acquisition et celles de traitement. Les tâches d'acquisition sont semblables à des tâches-couplées, et les tâches de traitement sont des tâches classiques. La torpille utilise différents capteurs pour réaliser les acquisitions, certains capteurs ne peuvent pas être utilisés en même temps pour cause d'interférences. Nous introduisons donc un graphe de compatibilité permettant de représenter les tâches d'acquisition pouvant avoir leurs exécutions qui se chevauchent. La torpille possède un monoprocesseur embarqué permettant d'exécuter toutes la tâches. Nous nous ! intéresserons dans un premier temps à une modélisation du problème, puis dans un second temps je présenterai une étude de la complexité et de l'approximation des différents problèmes que nous pourrons rencontrer selon le type des tâches d'acquisition étudiées. Cette étude sera décomposée en trois parties, où nous prendrons en compte la présence de la contrainte d'incompatibilité et/ou celle des tâches de traitement.
  • Teodor Gabriel Crainic (CIRRELT et ESG-UQAM) - Planification des systèmes de logistique urbaine et l'incertitude de la demande
    Date : 5 décembre 2011 à 10h00 - salle de conférences 
    City Logistics, ou logistique urbaine, est à la fois un concept plutôt révolutionnaire dans la façon d’envisa! ger le transport de marchandise en ville, un ensemble de propositions, visions, projets, réalisations et rêves, ainsi que des possibilités et défis importants pour la recherche opérationnelle. C’est dans ce contexte que nous nous intéressons aux problèmes de planification des systèmes de logistique urbaine, notamment à la planification tactique des systèmes à deux échelons et au traitement de l’incertitude, particulièrement relativement à la demande de transport, dans ce contexte. Nous discuterons ces concepts, décrirons un cadre de modélisation du problème de planification tactique, pour ensuite présenter deux modèles, un déterministe et un deuxième de programmation stochastique à deux étapes prenant explicitement en compte l’incertitude sur le niveau réel de demande à satisfaire par un plan déterminé à priori sur la base de prévisions. Nous regarderons, en particulier, la question de la capacité additionnelle qu’il faudra, probablement, prévoir, ai! nsi que qu’un certain nombre de politiques de modificati! on du pl an, les « recours », suite à l’observation de la demande « réelle ».  Dans tous les cas, il s’agit non seulement de chercher la « meilleure solution » d’un point de vue conceptuel et mathématique, mais aussi de ne pas oublier les objectifs de société de la logistique urbaine – moins d’impacts négatifs sur la ville et ces citoyens –,  ainsi que les questions relatives à la gestion du système et de ses ressources. Ce séminaire a lieu dans le cadre de la journée du groupe de travail Transport et Logistique du GdR Recherche Opérationnelle du CNRS.
  • Přemysl Šůcha - A Multistage Approach for an Employee Timetabling Problem with a High Diversity of Shifts as a Solution for a Strongly Varying Workforce Demand
    Date : 20 Octobre 2011 a 15h00 - salle Feynman
    This work deals with the employee rostering problem at the airport. Such problems, related to the time varying demand of the transport services, use many (e.g. about a hundred) diverse shifts to cover the workforce demand during the day. Together, with the strict constraints, given by the collective agreement, the problem becomes difficult to solve. In our case, one stage algorithms, used to solve the usual employee rostering problems, produce an unusable roster in practice. This work suggests a three stage approach for the employee rostering problem where a set of different shifts is needed to satisfy the coverage requirements. The solution is based on the problem transformation to a simpler problem which is used to determine a rough position of the shifts in the roster. The maximal weighted matching in the bipartite graph is used as the inverse transformation of the problem and the final roster is obtained by the optimization based on a Tabu Searc! h algorithm.
  • Alessandro Agnetis -  
    Date : 19 Mai 2011 -14h00 - Salle Feynman 

    In this talk we address a relatively novel class of scheduling problems, arising in various different contexts, in which jobs are characterized by a certain revenue (if successfully carried out) and a certain chance of success. If a job fails, the corresponding machine is blocked and no further job can be executed. The problem is to allocate and sequence the jobs on m parallel, identical machines in order to maximize expected revenue. For this problem, which is strongly NP-hard, we give some approximation results for the case m=2, and discuss the special case in which machines fail according to an exponentially distributed random process.

  • Alessandro Agnetis -  Multi-agent scheduling problems
    Date : 13 Mai 2011 -14h00 - Salle Feynman 

    Multi-agent scheduling refers to a class of multi-objective scheduling problems in which the objectives correspond to different decision makers (agents), each owning a subset of jobs. Each agent is only concerned with how his/her jobs are scheduled, so a compromise schedule must be sought, accounting for each agent's performance criterion. Multi-agent scheduling problems arise in several contexts, including transportation logistics, telecommunications and distributed computing systems. The multi-agent nature of these problems can be addressed by a wide range of methodological tools, including combinatorial optimization, game theory, bargaining models. In this talk we review the main approaches and results, pointing out open problems and venues for future research.

  • Sandra U. Ngueveu - Algorithmes efficaces basés sur la génération de colonnes: application aux tournées de véhicules m-péripatétiques
    Date : 8 avril 2011 -10h30 - Salle Europe
    La génération de colonnes est aujourd'hui largement répandue/utilisée pour la résolution de problèmes d'optimisation combinatoire. Cet exposé passera en revue les principes, avantages et inconvénients de cette approche avant de présenter l'adaptation et l'application au problème de tournées de véhicules m-péripatétiques (m-PVRP). Le m-PVRP modélise par exemple le transport de fonds régulier, les tournées de gardiennage, … où par sécurité, la séquence de visite des clients doit varier d'une période à l'autre. L'exposé illustrera l'intérêt des méthodes proposées, en particulier pour obtenir des bornes inférieures de bonne qualité (entre 1 et 3% de l'optimum) pour des temps de calculs raisonnables (quelques secondes).
  • Pierre Jean Meyer - Simulation de la gestion des bagages dans un aériport international
    Date : 29/03/2011 -16h00 - Salle Feynman
    Cet exposé présente les résultats d'un projet tutoré de l'ENSEEIHT, effectué en collaboration avec Florian Bonneau et Antoine Prost, en relation avec le sujet de thèse de Markus Frey (doctorant de l'Université de Munich). Une démonstration du simulateur réalisé avec le logiciel ARENA a été effectuée.
  • Julien Darlay -  Méthodes de la recherche opérationnelle pour l'analyse de données
    Date : 27/01/2011 - 11h30 - Salle de Direction
    L'analyse de données (ou datamining) a pour but d'extraire des informations originales à partir d'un grand volume de données. On peut trouver de nombreuses applications dans le domaine médical, dans l'ingénierie... Les problèmes d'analyse de données peuvent se ramener à des problèmes d'optimisation, la plupart du temps difficiles au sens de la complexité. Nous donnerons une illustration avec une modélisation en programmation linéaire d'un problème de catégorisation d'observations. Dans un deuxième temps, nous verrons une méthode particulière, l'analyse combinatoire de données. Cette méthode a la spécificité d'être développée par des chercheurs en recherche opérationnelle et repose sur des fondements théoriques forts (l'extension de fonctions booléennes partiellement définies). Elle se base sur des techniques classiques d'optimisation: algorithme glouton, programmation linéaire en nombres entiers, recherche exhaustive pour fournir des modèles performants et facilement interprétables.

2010
  • Nicolas Barnier -  Automatisation de la gestion du trafic aérien en Europe
    Date : 30/11/2010 - 14h00 - Salle Vignemale
    Malgré les récessions temporaires qui ont suivis les années 2001 et 2008, le trafic aÈrien connait une progression importante depuis  plusieurs décennies, ce qui mène fréquemment l'espace aérien à saturation et génère des retards de plus en plus importants. Contrairement à l'automatisation des systèmes embarqués dans les aéronefs, l'optimisation de la gestion du trafic aérien (Air Traffic Management - ATM) n'a connu que très peu d'Èvolutions depuis trenteans, si bien que la plupart des tâches du contrôle aérien et de l'ATM reposent toujours sur l'expertise d'opérateurs humains. Pourtant, l'automatisation de l'ATM fait l'objet de nombreux projets de recherche et une pression de plus en plus importante de la part des compagnies aériennes et de la Commission Européenne incite à l'amélioration de la capacité de l'espace aérien à l'Èchelle continentale. Le projet SESAR (Single European Sky ATM Research) a ainsi pour objectifs d'augmenter la capacité, améliorer la sécurité, diminuer l'impact environnemental des vols ainsi que le coût du contrôle. Mais l'ATM est un système complexe et de grande taille, sujet à de nombreuses sources d'incertitude et qui nécessite des transitions continues . Sur le plan théorique, la recherche en ATM est un domaine relativement récent, et nombreux sont les projets qui ont dû être abandonnés car ils sous-estimaient les difficultés techniques liées à l'un ou l'autre de ces paramètres. Ainsi, les systèmes automatisés qui permettent aujourd'hui d'améliorer opérationnellement l'ATM sont relativement anecdotiques et peu  optimisés. Deux voies principales se distinguent néanmoins pour tenter d'absorber la croissance du trafic en Europe dans la prochaine décennie : une approche centralisée fondée sur la gestion précise de trajectoires 4D et destinée aux espaces à forte densité, et une approche distribuée rendant les avions autonomes en utilisant des solveurs embarqués pour les zones de plus faible trafic. Pour répondre à ces attentes, les partenaires industriels de SESAR tentent de développer des systèmes de gestion de vol toujours plus précis, tandis que la recherche en ATM propose d'optimiser la structure du réseau de routes, la répartition du trafic, voire la gestion dynamique de trajectoires 4D, tout en conservant le rôle central de l'opérateur humain dans la décision
    finale.

  • Markus Frey -  Scheduling and planning the outbound baggage process at international airports
    Date : 29/09/2010 - 11h00 - Salle du conseil
    The planning of outbound baggage at international airports is a challenging task in the airport industry. The issue is to control the incoming baggage flow in order to balance the workload over the baggage handling system. The resource consumption of the the di fferent activities, which have to be scheduled, are depending on the arrival process of baggage. Because of high complexity we suggest a decomposition heuristic to tackle this problem.
  • Rainer Kolisch -  An efficient hybrid metaheuristic for integrated scheduling and
    staffing IT--projects based on a generalized minimum cost flow network
    Date : 03/06/2010 - 14h00 - Salle de Conférences
    Scheduling IT--projects and assigning the project work to human resources is an important and common task in almost any IT service company. It is particularly complex because human resources usually have multiple skills. Up to now only little work has considered IT-specific properties of the project structure and human resources.  In this paper we present an optimization model which simultaneously schedules the activities of multiple IT-projects with serial network structures and assigns the project work to multi-skilled internal and external human resources with static and heterogeneous efficiencies. The goal is to minimize costs. We solve the mixed--binary linear program with ILOG CPLEX and a hybrid metaheuristic which employs an efficient evaluation function exploiting the network structure of the staffing subproblem. The impacts of characteristic problem parameters on computation time and solution gaps are assessed in an experimental study. Our results show that by exploiting the network structure we can solve the staffing subproblem up to 7 times faster than CPLEX. Hence, the hybrid metaheuristic is superior to standard solvers especially for large problem instances.
  • Julien Moncel -  Problèmes d'ordonnancement avec usure ou apprentissage
    Date : 22/04/2010 - Salle Europe
    Jusque dans les années 90, la théorie classique de l'ordonnancement n'a considéré que des problèmes où les temps opératoires des tâches étaient considérés comme étant des paramètres statiques. Cependant, dans certaines situations, une telle modélisation est insuffisante car les temps opératoires des tâches dépendent essentiellement du moment où la tâche est réalisée. C'est par exemple le cas pour les incendies, qui peuvent s'étendre et donc prendre un temps plus important à maitriser si l'on tarde à les traiter.  Les problèmes d'ordonnancement avec usure ou apprentissage concernent donc des cas où les durées des tâches dépendent fortement du moment où ces tâches sont réalisées. On distingue de façon classique deux cas, celui de l'apprentissage (les tâches réalisées en fin d'ordonnancement sont réalisées plus rapidement qu'au début) et celui de l'usure (cas inverse : plus on attend, plus cela prend du temps).  Dans cet exposé on fera une brève revue de la littérature sur ce sujet, et on proposera quelques résultats théoriques sur l'existence d'algorithmes efficaces pour les problèmes à une machine.
  • Emmanuel Hébrard -  Contraintes molles d'égalité et de différence
    Date : 18/03/2010 - Salle de Conférences
    Les contraintes "AllDifferent" ou "Global Cardinality" sont
    essentielles dans de nombreux modeles de problemes combinatoires. Par
    exemple pour les problemes de "sport scheduling" ou de "car sequencing"
    ou elles permettent d'obtenir des resultats meilleurs que la PLNE.
    Nous avons etudie cette famille de contraintes qui permettent de
    favoriser la diversite ou la similarite entre variables. Apres avoir
    aborde les applications possibles de cette famille de contraintes, je
    montrerai les resultats algorithmiques que nous avons obtenu, en
    partculier sur la contrainte "SoftAllEqual".
  • Claire Hanen - Ordonnancements périodiques de graphes d'événements généralisés temporisés
    Date : 15/01/2010 - Salle Vignemale
    Les graphes d'évènements temporisés constituent un modèle intéressant et facilement analysable pour des problèmes d'ordonnancement cycliques sans conflits de ressource.
    Nous nous intéressons ici à l'extension de ce modèle construite en valuant les arcs du réseau de Petri sous-jacent. Ce modèle permet d'exprimer de manière concise des contraintes d'assemblage ou de limitation de buffers. Mais bien que les conflits de ressource en soient exclus, il apparait que l'analyse de faisabilité et de performance d'un tel modèle pose des problèmes difficiles qui pour beaucoup restent ouverts. Nous évoquerons quelques unes de ces difficultés, et monterons que les ordonnancements périodiques peuvent se calculer en temps polynomial, mais que, contrairement au modèle simple, ils ne sont pas dominants.
2009
  • Fawzi Bessaih - Validation de la charge utile d'un satellite de télécommunication
    Date : 26/11/2009 - Salle Moore
  • William Mangoua Sofack - Ordonnancement sous contraintes de consommation énergétique
    Date : 15/10/2009 - Salle de Conférences
  • Pauline Desseaux - Méthode de recherche arborescente pour un problème d'ordonnancement bi-objectif
    Date : 15/10/2009 - Salle de Conférences
  • Jean Charles Billaut - Doit-on croire le classement de Shangaï ? Une approche par l'analyse multicritères
    Date : 22/6/2009 - Salle Vignemale 
    Présentation
  • Philippe Laborie - Modéliser et résoudre les problèmes d'ordonnancement avec IBM ILOG CP Optimizer
    Date : 24/4/2009 - Salle Vignemale 
    Présentation
  • Christian Artigues - Présentation du challenge ROADEF
    Date : 3/4/2009 - Salle Moore 
    Présentation
  • Pierre Lopez - Recherche à divergences limitées pour des problèmes d'ordonnancement d'atelier flexibles
    Date : 3/4/2009 - Salle Moore 
    Présentation
  • David Allouche - Sélection de TagSNP par réseau de contraintes pondérées
    Date : 6/3/2009 - Salle Tourmalet 
    Présentation
2008

  • Murat Afsar - Partitionnement d'un graphe orienté acyclique par la génération de colonnes
    Date : 18/12/2008 - Salle Bardeen 
    Présentation
  • Alain Berro - Algorithmes évolutionnaires pour l'optimisation multiobjectif
    Date : 4/11/2008 - Salle Bardeen 
    Présentation
  • Roel Leus - Ordonnancement de projet avec échec des activités
    Date : 11/09/2008 - Salle Vignemale 
    Présentation
  • François Galasso - Aide à la décision pour la planification de chaînes logistiques dyadiques
    Date : 12/06/2008 - Salle Vignemale 
    Présentation
  • Nicolas Jozefowiez - A branch-and-bound algorithm for a traveling salesman problem with colors and two objectives
    Date : 12/06/2008 - Salle Vignemale 
    Présentation
  • Rémy Dupas - Routage de véhicules en dynamique
    Date : 20/05/2008 - Salle Feynman 
    Présentation
  • Julien François - Planification des chaines logistiques - Modélisation du système décisionnel et performance
    Date : 12/03/2008 - Salle Vignemale 
    Présentation
  • Laurent Houssin - Commande de systèmes (max,+)-linéaires
    Date : 10/01/2008 - Salle Vignemale
    Présentation
2007

  • Djamel Berkoune - Optimisation de l'ordonnancement en milieu prévisionnel incertain
    Date : 29/11/2007 - Salle Vignemale
    Présentation
  • Thierry Garaix - Optimisation et qualité de service pour le transport à la demande
    Date : 01/10/2007 - Salle Bardeen
    Présentation