GSCOP-RUB-GCSP

Soutenance de thèse de Guillaume Massonnet - jeudi 04/04/2013

La soutenance de thèse de Guillaume Massonnet aura lieu le jeudi 04 avril 2013 à 14h en amphi Gosse (Grenoble-INP site Viallet, 46 avenue Félix Viallet 38000 Grenoble).

Titre :
Algorithmes d'approximation pour la gestion de stocks

Résumé :
La gestion de stocks a toujours été une composante majeure de la recherche opérationnelle et de nombreux modèles issus de problèmatiques industrielles concrètes présentent un intérêt à la fois théorique et pratique. Dans ce cadre, nos travaux se concentrent sur plusieurs problèmes classiques du domaine, pour lesquels on ne connaît pas à ce jour de méthode efficace permettant de calculer une solution optimale. Plus précisément, nous étudions plusieurs modèles déterministes, dans lesquels les demandes des clients sont connues à l'avance, et nous proposons pour chacun d'entre eux des techniques d'approximation qui permettent de construire des solutions approchées en un temps de calcul raisonnable.

Nous considérons d'abord des modèles à temps continu composés d'un entrepôt, dont la demande et les coûts relatifs au stockage des produits dépendent du temps. Nous présentons une technique simple basée sur l'équilibrage des différents coûts encourus par le système pour obtenir des approximations pour une large classe de problèmes de ce type.

Dans un deuxième temps, nous étudions un problème à temps discret NP-difficile, dans lequel un entrepôt central approvisionne plusieurs détaillants faisant face à la demande de leurs clients. Nous introduisons une nouvelle technique de décomposition du problème en sous-systèmes plus simples, faciles à résoudre grâce à des techniques classiques de la littérature. Enfin, nous présentons une méthode de recombinaison originale permettant d'obtenir une politique réalisable pour le problème d'origine à partir des sous-solutions obtenues. L'algorithme ainsi défini peut être adapté à plusieurs extensions du modèle de base incluant des structures de coûts plus générales ou encore offrant la possibilité de servir certaines demandes en retard.

Membres du jury :
  • M. Mathieu Van Vyve, professeur à l'Université Catholique de Louvain - Rapporteur
  • M. Imed Kacem, professeur à l'Université de Lorraine - Rapporteur
  • M. Gautier Stauffer, professeur à Grenoble-INP - Examinateur
  • M. Tim Nonner, Research Staff Member at IBM Zürich research Laboratory - Examinateur
  • M. Christophe Rapine, professeur à l'Université de Lorraine, directeur de thèse
  • M. Jean-Philippe Gayon, maître conférence (HDR) à Grenoble-INP, co-directeur de thèse
Abstract:
Inventory management has always been a major component of the field of operations research and numerous models derived from the industry aroused the interest of both the researchers and the practitioners. Within this framework, our work focuses on several classical inventory problems, for which no tractable method is known to compute an optimal solution. Specifically, we study deterministic models, in which the demands of the customers are known in advance, and we propose approximation techniques for each of the corresponding problems that build feasible approximate solutions while remaining computationally tractable.

We first consider continuous-time models with a single facility when demand and holding costs are time-dependent. We present a simple technique that balances the different costs incurred by the system and use this concept to build approximation methods for a large class of classical single-echelon problems.

The second part of our work focuses on a discrete time model, in which a central warehouse supplies several retailers facing the final customers demands. This problem is known to be NP-hard, thus finding an optimal solution in polynomial time is unrealistic unless P=NP. We introduce a new decomposition of the system into simple subproblems, for which an optimal solution can be computed easily. We then present a recombination method that builds a feasible policy for the original problem from the solutions to these subsystems. The resulting algorithm has a constant performance guarantee and can be adapted to several extensions of the model, including more general cost structures and problems with backlogging or lost-sales.