Méthodes d'optimisation pour la gestion de stocks multi-échelon

In this thesis we are interested in several multi-level lot-sizing problems taking into account production capacities. We first study a 2-level in series lot-sizing problem with identical and stationary capacities at both levels, for which we propose an exact dynamic algorithm running in polynomial time under some hypothesis. Next chapter extends this result on two main lines: we consider the multi-level in series lot-sizing problem with batch deliveries and with a number of level which is part of the input. We provide a very efficient exact algorithm for this problem, which is polynomial in the number of levels and in the number of periods, based on an original decomposition into induced connected components. Then, we consider more general versions of this problem, for which we provide NP-hardness results when batch sizes or capacities are level-dependent. We propose 2-approximation algorithms for these problems, based on the sandwiching of the objective function by two affine functions. Finally, we study a single-level lot-sizing problem in a system composed of identical machines working in parallel. The originality of this study is to consider a periodic energy limitation. At each period it must be decided how many machines to switch on or off and the volume to be produced and stored. Complexity results are provided, showing that this problem is NP-hard, even under some restrictive assumptions, and an exact dynamic algorithm running in polynomial time is proposed for the case of stationary energy parametersDans cette thèse nous nous intéressons à plusieurs problèmes de gestion de stocks, à travers des modèles de dimensionnement de lots sur plusieurs niveaux, en tenant compte de capacités de production. Nous étudions tout d’abord un problème de dimensionnement de lots à deux niveaux en série avec des capacités de production identiques et stationnaires aux deux niveaux, pour lequel proposons un algorithme dynamique exact pouvant résoudre le problème en temps polynomial sous certaines hypothèses. Dans le chapitre suivant nous étendons ce résultat dans deux directions : nous considérons le problème de gestion de stocks sur un nombre quelconque de niveaux en série, et nous considérons des livraisons par lots. Nous présentons un algorithme exact de résolution, polynomial et très efficace, basé sur une décomposition originale en composantes connexes induites. Nous considérons ensuite des versions plus générales de ce problème, en établissant des résultats de NP-complétude lorsque chaque niveau à une capacité ou une taille de lot différentes. Nous proposons pour ces problèmes une 2-approximation, basé sur l’encadrement de la fonction objectif par deux fonctions affines. Pour finir nous étudions un problème sur un seul niveau mais dans un système de production composé de machines identiques fonctionnant en parallèle. L’originalité de ce problème est de considérer une limitation de la consommation énergétique. A chaque période, on doit décider combien de machines allumer ou éteindre, et quel volume produire et stocker. Des résultats de complexité sont proposés, montrant que ce problème est NP-difficile même sous des hypothèses fortes, et un algorithme dynamique exact est présenté pour le cas de paramètres d’énergie stationnaire