Ce travail porte sur la résolution exacte d'un problème d'optimisation combinatoire multi-objectif. Nous cherchons d'une part à confirmer l'efficacité de l'algorithme dit en deux phases, et d'autre part à poser une généralisation des procédures de séparation et évaluation, populaires dans le cadre mono-objectif mais presque absentes en multi-objectif. Notre étude s'appuie sur le problème multi-objectif de sac à dos unidimensionnel en variables binaires. Ce dernier est un classique de l'optimisation combinatoire, présent comme sous problème dans de nombreux problèmes d'optimisation. La première partie de nos travaux porte sur un pré-traitement permettant de réduire la taille d'instances de ce problème. Nous mettons en évidence plusieurs propriétés permettant de déterminer a priori une partie de la structure de toutes les solutions efficaces. Nous nous attachons ensuite à décrire une procédure performante de type deux phases pour ce problème, tout d'abord dans le cas bi-objectif. Nous étendons ensuite cette procédure pour des instances ayant trois objectifs ou plus. Les résultats obtenus sont comparés aux meilleurs algorithmes existants pour ce problème et confirment l'efficacité de l'approche en deux phases. La dernière partie de notre travail concerne la généralisation au cas multi-objectif d'une procédure de séparation et évaluation. Nous identifions plusieurs difficultés auxquelles nous répondons en proposant deux nouvelles procédures. Les expérimentations numériques indiquent que ces dernières permettent de résoudre des instances en des temps raisonnables, bien qu'elles n'atteignent pas les performances d'une procédure de type deux phases.

Nous abordons dans cette thèse des problèmes de flowshop de permutation soumis des contraintes de délais minimaux et maximaux avec deux types de travaux principaux : 1. Nous avons modélisé, en utilisant l'algèbre MaxPlus, des problèmes de flowshop de permutation m-machines soumis une famille de contraintes : de délais minimaux, de délais maximaux, de sans attente, de délais fixes, de temps de montage indé- pendant de la séquence, de temps de démontage indépendant de la séquence, de blocage, de dates de début au plus tæt ainsi que de durées de latence. Des matrices caractérisant complètement leurs travaux associés ont été élaborées. Nous avons fait apparaître un problème central soumis des contraintes de délais minimaux et maximaux. 2. Nous avons élaboré des bornes inférieures pour le makespan et pour la somme (pondérée ou non) des dates de fin. Ces bornes inférieures ont été incorporées dans des procédures par séparation et évaluation. Nous avons généralisé les bornes inférieures de Lageweg et al. pour des contraintes quelconques et amélioré une borne inférieure de la littérature. L'utilisation de chacune de ces bornes inférieures ainsi que de leurs combinaisons ont été testées. Une famille de bornes inférieures pour la somme (pondérée ou non) des dates de fin a été élaborée basée sur la résolution d'un problème une machine et sur la résolution d'un problème de voyageur de commerce. Une politique de sélection de bornes inférieures a été proposée pour combiner les bornes inférieures. Bien qu'il s'agisse d'un problème de NP-difficile, l'efficacité de ces bornes inférieures a été vérifiée l'aide de tests. / In this thesis, permutation flowshop problems with minimal and maximal delay constraints were considered through two following principal tasks were particularly tackled. 1. In the first task, m-machine permutation flowshop problems with a family of constraints (minimal delays, maximal delays, no-wait, fixed delays, sequence-independent setup times, sequence-independent removal times, blocking, ready dates, duration of latency) were modeled using MaxPlus algebra. Job associated matrices which totally characterize these jobs were elaborated. The modeling led to reveal a central problem with constraints of minimal and maximal delays. 2. In the second task, lower bounds for makespan and for total (weighted or unweighted) completion times were elaborated. These lower bounds were incorporated in branchand-bound procedures. The lower bounds of Lageweg et al. were generalized for any constraint and a existed lower bound was improved. The usage of each of these lower bounds as well as that of their combinations was tested. A family of lower bounds for total (weighted or non-weighted) completion times was elaborated thanks to the solution of a one-machine problem and the solution of a traveling salesman problem. A lower bound selection strategy was proposed in order to combine these lower bounds. Despite necessity to solve a NP-hard problem, the effectiveness of these lower bounds was verified by numerical tests.

Dans le contexte actuel marqué par l’instabilité des marchés, les clients sont de plus en plus exigeants. un client qui n’est pas approvisionné à une date souhaitée peut soit remettre son achat à plus tard, soit aller chercher le produit chez un concurrent. de plus, l’entreprise doit faire face à de multiples imprévisibilités internes, de la concurrence ou d’événements extérieurs. ces aléas induisent de l'incertitude dans la planification de la production et génèrent des sources nombreuses de retard, de désynchronisation et de pertes de productivité. ce travail de thèse s’intègre dans la problématique de la planification de la production dans un environnement incertain. nous étudions des problèmes de la planification des réapprovisionnements pour un système d’assemblage à plusieurs niveaux, quand les délais d’approvisionnement sont incertains. nous avons choisi comme indicateur de performance l’espérance du coût total moyen qui est égal à la somme du coût de stockage des composants, le coût de rupture du produit fini et le coût de stockage du produit fini. des propriétés théoriques, des modèles analytiques ainsi que des méthodes d’optimisation ont été proposés. nous avons montré que la résolution du problème ne dépend pas seulement de la méthode de résolution et du nombre de niveaux, mais aussi du coût de rupture en produit fini et de la structure du système d’assemblage. / In the current industrial context, the offer is largely higher than the demand. Therefore, the customers are more and more exigent. To distance themselves, companies need to offer to their customers the best quality products, the best costs, and with controlled lead times as short as possible. Last years, the struggle for reducing costs was accentuated within companies. However, stocks represent an important financial asset, and therefore, it is essential to control them. In addition, a bad management of stocks led either to delays in delivery, which generate additional production costs, either to the unnecessary inventory. The latter one can occur at different levels (from components at the last level to finished product), it costs money and immobilize funds. That is why, planners have to look for efficient methods of production and supply planning, to know exactly for each component, and when to order and in which quantity.The aim of this doctoral thesis is to investigate the supply planning in an uncertain environment. We are interested in a replenishment planning for multi-level assembly systems under a fixed demand and uncertainty of components lead times.We consider that each component has a fixed unit inventory cost; the finished product has an inventory cost and a backlogging cost per unit of time. Then, a general mathematical model for replenishment planning of multi-level assembly systems, genetic algorithm and branch and bound method are presented to calculate and to optimize the expected value of the total cost which equals to the sum of the inventory holding costs for the components, the backlogging and the inventory holding costs for the finished product. We can state by the different results that the convergence of the GA doesn't depend only on the number of components in the last level but also on the number of levels, the type of the BOM and the backlogging cost for the finished product.

Le problème de gestion de projet à contraintes de ressources est un des problèmesles plus étudiés dans la littérature. Il consiste à planifier des activités soumises à desrelations de précédence, et nécessitant des ressources renouvelables. L’objectif est deminimiser la durée du projet, soit le makespan. Nous étudions le problème de gestion deprojet à contraintes de ressources. Nous nous sommes intéressées à la résolution exactedu problème. Dans la première partie de la thèse, nous élaborons une série de bornesinférieures basées sur le raisonnement énergétique et des formulations mathématiques.Les résultats montrent que les bornes proposées surpassent ceux de la littérature. Dansla deuxième partie, nous proposons des procédures par séparation et évaluation utilisantles bornes inférieures dévelopées dans la première partie. / Resource Constrained Project Scheduling Problem is one of the most studied schedulingproblems in the literature. It consists in scheduling activities, submitted to precedencerelationship, and requiring renewable resources to be processed. The objective isto minimize the project duration, i.e., the makespan. We study the Resource ConstrainedProject Scheduling Problem. We are interested on the exact resolution of the problem.In the first part of the thesis, we develop a series of lower bounds based on energeticreasoning and mathematical formulations. The computational results show that theproposed lower bounds outperform the ones of the literature. In the second part, wepropose Branch-and-Bound procedures using the lower bounds developed on the firstpart.