Accès direct au contenu


English version > Positions > Thesis

Thesis

Subject 1


Multi-agent model for integrated scheduling and routing problem

Advisor :
Jean-Charles BILLAUT, jean-charles.billaut@univ-tours.fr

Dans l'environnement économique d'aujourd'hui, défini par la mondialisation, la concurrence et la demande croissante des clients obligent les entreprises à trouver de nouvelles façons de maintenir les coûts bas et de rester compétitif, tout en fournissant une haute qualité de service pour leurs clients. La complexité et l'interconnexion de cet environnement globalisé font que la planification de la production et la logistique sont des tâches importantes qui peuvent réduire les coûts et assurer des opérations sans heurts pour une entreprise, considérant que les coûts de stockage et de transport / distribution représentent les principaux coûts d'une entreprise.
 
La gestion de la chaîne d'approvisionnement consiste à coordonner et à planifier la chaîne d'approvisionnement d'une entreprise, et considère toutes les activités impliquées dans la production d'un produit/d’un service du fournisseur jusqu’à la livraison au client. Les chaînes d'approvisionnement sont généralement des réseaux très complexes qui se composent de plusieurs étapes, de liens et d’acteurs. Toutefois, les deux principaux axes de la gestion de la chaîne d'approvisionnement sont la planification de la production et de la distribution.
 
L'objectif est d'optimiser les décisions de planification pour la production et la distribution, comme les décisions d'ordonnancement et de routage, en fonction d'un ensemble d'objectifs. Bien que ces deux domaines soient traditionnellement traités individuellement, ils sont très interconnectés et des considérations plus récentes ont montré que les approches intégrées de la chaîne d'approvisionnement, qui prennent en considération à la fois les décisions de production et de distribution, offrent des avantages aux organisations aussi bien en termes de coûts qu’en termes de gestion du temps. L'objectif de ces considérations est de trouver une solution globale optimale au problème d'ordonnancement de la chaîne d'approvisionnement pour tous les agents en intégrant les deux problèmes individuels de planification de la production et de la distribution dans un seul modèle. Ces dernières années, ces approches ont été de plus en plus couvertes dans la littérature. Cependant, l'une des difficultés associées à cela est la complexité des deux modèles individuels, ce qui aboutit souvent à des modèles trop simplifiés.
 
Le problème considéré ici est un problème de programmation de la production et de la distribution intégré au niveau opérationnel. Le problème est considéré comme un problème de décision multi-agent, consistant en deux sous-problèmes : un problème d'ordonnancement confié à un agent et un problème de routage de véhicule confié à un autre agent.
 
Le modèle inclut également les coûts de stocks qui se produisent pendant la phase de production, afin d'obtenir un modèle plus réaliste. Les coûts de stocks, même s'ils sont souvent négligés dans les modèles d’ordonnancement de la production, jouent un rôle majeur dans la planification de la production. Deux types de stocks sont considérés ici: stocks des travaux en cours et stocks des produits finis.

Le travail de thèse comportera plusieurs aspects :
  • Tout d’abord une étude de la littérature, pour se familiariser avec la problématique
  • Ensuite, une recherche sera effectuée dans le contexte de la chaîne logistique, pour identifier des coûts réalistes pour les stocks de produits, les transports (coût réel d’un transport / coût facturé d’un transport), les accords entre acteurs, etc. Cette recherche aboutira à la proposition d’un générateur d’instances, qui sera utilisé par la suite pour tester les méthodes.
  • Enfin, le candidat devra proposer des méthodes de résolution efficaces :
    • Tout d’abord pour les différents modèles de collaborations entre les acteurs, il devra proposer des modèles de programmation mathématique, les tester et les valider.
    • Ensuite, plusieurs modèles particuliers seront étudiés plus en détail, et des méthodes de résolution efficaces (de nature heuristique) seront proposées. Le premier modèle étudié sera un modèle global où les deux acteurs appartiennent à une même organisation et où le coût à optimiser est un coût global. Les modèles où un des deux acteurs domine la négociation seront également étudiés. Enfin, un modèle où les deux acteurs sont indépendants mais coopèrent sera étudié, et comparé aux autres modèles.
Un contact industriel sera recherché dans la région Centre-Val de Loire pour confronter nos hypothèses à la réalité, affiner les modèles proposés, et pour coller davantage à la réalité industrielle.

Références :
A. AGNETIS, J-C. BILLAUT, S. GAWIEJNOVICZ, D. PACCIARELLI, A. SOUKHAL. Multiagent Scheduling. Models and Algorithms, Springer-Verlag, 2014. ISBN 978-3-642-41880-8
S. ROHMER, A. BRAIN, P-A. MORIN, J-C. BILLAUT, A two-agent model for production and outbound distribution scheduling, 27th European Conference on Operational Research (EURO 2015), Glasgow, July 2015.
S. ROHMER, J-C. BILLAUT Production and outbound distribution scheduling: a two-agent approach, International Conference on Industrial Engineering and Systems Management (IESM’2015), Séville (Spain), October, 2015.
S. ROHMER, A two-agent model for production and outbound distribution scheduling, mémoire de stage (encadrement J-C. BILLAUT), Master CADS, Université de Tours, 2015.
L. BELLEGO, Heuristiques pour un scénario de collaboration entre un "producteur" et un "distributeur", mémoire de PRD (encadrement J-C. BILLAUT), Polytech Tours, 2016.
A. BRAIN, P-A. MORIN, Un modèle de négociation entre un producteur et un transporteur, Rapport Projet d’Option Logistique & Optimisation (encadrement J-C. BILLAUT), Polytech Tours, 2015.

Sujet 2


Interactive data exploration and analysis

Advisors :
Arnaud GIACOMETTI : arnaud.giacometti@univ-tours.fr
Patrick MARCEL : patrick.marcel@univ-tours.fr

Contexte général et motivation
L’analyse interactive de données [6,7] est une activité consistant en la manipulation, l’exploration et l’analyse de large volumes de données. Cette activité peut concerner des utilisateurs de profil très différents, néophytes ou non. Les données en question peuvent également être de natures diverses : structurées (données transactionnelles, séquentielles, relationnelles ou spatio-temporelles), semi-structurées (bases de documents XML, données du Web Sémantique) ou plus faiblement structurées (documents textuels). Dans toutes les situations, l’objectif recherché par l’utilisateur est d’extraire du sens des masses de données analysées, afin d’acquérir une connaissance approfondie de la réalité dont celles-ci rendent compte.

Afin d’améliorer la qualité des analyses, l’objectif général de cette thèse est de contribuer au développement d’outils d’analyse centrés utilisateurs, donnant un statut privilégié à leurs attentes et préférences. Ces attentes comme ces préférences sont à modéliser et à découvrir à partir du processus d’analyse. Pour relever ce défi, la piste choisie est de proposer des méthodes d’analyse qui soient interactives, permettant ainsi de prendre en compte au plus tôt les attentes et préférences des utilisateurs, qu’elles soient explicites ou implicites, mais aussi des méthodes permettant d’évaluer automatiquement la qualité d’une analyse interactive en cours de réalisation.

Objectifs de la thèse
Dans ce cadre, l’objectif de la thèse est de développer des travaux dans deux grandes directions :
  • Le développement d’algorithmes et de méthodes permettant la découverte interactive de contrastes dans des données non-étiquetées. Ce type d’approche est notamment utile dans les tâches d’exploration de données visent à caractériser une partie des données par rapport à une autre. C’est par exemple le cas pour identifier des comportements frauduleux en comparant les données des fraudeurs aux autres. Ce type d’approche, déjà amorcé pour les données transactionnelles dans [5], consiste à extraire des motifs ou modèles locaux qui au fur et à mesure des interactions avec l’utilisateur se focalisent de plus en plus sur la classe cible tout en la caractérisant. Dans le cadre de cette thèse, nous souhaitons étendre à des classes de motifs dits structurés (permettant notamment d’analyser des données séquentielles) les récentes avancées en échantillonnage de motifs [1, 4].
  • Le développement de méthodes et outils permettant d’évaluer automatiquement la qualité d’une analyse interactive de données. Le travail s’appuiera sur l’hypothèse suivante : la qualité peut être mesurée en analysant les traces laissées par l’analyste, notamment ses productions (les analyses faites) et ses explorations (les requêtes faites sur les données, les documents consultés, etc.), et en observant l’évolution des compétences de l’utilisateur lors de son activité d’analyse. Ce travail se situe donc à la croisée de la modélisation de l’activité de recherche (par exemple pour de la recherche exploratoire [8]), de la modélisation d’intérêt utilisateur (par exemple pour des assistants intelligents [9]), et de la modélisation d’apprenants (par exemple pour de l’évaluation de compétences [2]). La définition de métriques, leur évolution et leur agrégation constitueront la piste de travail privilégiée.
Les principales contributions attendues sont :
  • La proposition d’une méthode d’analyse interactive de données pour l’identification et la caractérisation des données pertinentes pour un analyste.
  • La définition d’un cadre général pour l’évaluation de la qualité d’une analyse interactive de données.
  • Le développement d’un prototype permettant d’évaluer les différentes propositions.

Références
[1]    Boley, M., Lucchese, C., Paurat, D., & Gärtner, T. (2011). Direct local pattern sampling by efficient two-step random procedures. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 582-590).
[2]    Corbett A. T., Anderson J. R. (1995). Knowledge Tracing: Modelling the Acquisition of Procedural Knowledge. User Model. User-Adapt. Interact. 4(4), pp. 253-278.
[3]    Djedaini M., Furtado P., Labroche N., Marcel P., Peralta V. (2016). Benchmarking exploratory OLAP, TPCTC 2016.
[4]    Giacometti, A., & Soulet, A. (2016, April). Frequent Pattern Outlier Detection without Exhaustive Mining. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 196-207). Springer International Publishing.
[5]    Hewasinghage, M., Isaj, S., Giacometti, A., Soulet A. (2017). Caractérisation interactive des transactions préférées d’un utilisateur par l’échantillonnage de motifs. EGC’2017. A paraître.4]
[6] Giacometti, A., & Soulet, A. (2016, April). Frequent Pattern Outlier Detection without Exhaustive Mining. In Pacific-Asia Conference on Knowledge Discovery and Data Mining (pp. 196-207). Springer International Publishing.
[7]    Idredos S., Papaemmanouil O. Olga, Chaudhuri S. (2015). Overview of Data Exploration Techniques. SIGMOD Conference 2015, pp. 277-281.
[8]    Morton K., Balazinska M., Grossman D., Mackinlay J. D. (2014). Support the Data Enthusiast: Challenges for Next-Generation Data-Analysis Systems. PVLDB 7(6), pp. 453-456.
[9]    White R. W., Roth R. A. (2009). Exploratory Search: beyond the Query-Response Paradigm. Synthesis Lectures on Information Concepts, Retrieval, and Services, Morgan & Claypool Publishers 2009.
[10] Yang L., Guo Q., Song Y., Meng S., Shokouhi M., McDonald K., Bruce Croft W. (2016). Modeling User Interests for Zero-Query Ranking. ECIR 2016, pp. 171-184.

  • Facebook
  • twitter
  • google
  • imprimer
  • version PDF
  • Envoyer cette page

Retour au site institutionnel