Le problème de bin packing consiste à déterminer le nombre minimum de conteneurs (bins) nécessaires pour ranger un ensemble d’objets. Ce problème NP- complet fait depuis de nombreuses années l’objet de multiples travaux de recherche, théoriques et pratiques. On le retrouve entre autres dans l’industrie de découpe de tissu, de l’acier, de bois et de verre. La littérature sur le problème de bin packing est riche et les algorithmes et approches de résolution sont très diverses. Cependant, les solutions proposées par ces algorithmes peuvent ne pas être utiles quand on traite des problèmes industriels réels. Dans cette thèse, nous considérons plusieurs types de contraintes liées à des incompatibilités entre objets. Ces contraintes sont inspirées de celles rencontrées lors d’une collaboration industrielle. Le sujet de recherche de cette thèse porte sur la résolution d’une variété de problèmes de bin packing. Nous nous intéressons à des bornes inférieures et supérieures pour les trois problèmes suivants : un problème de bin packing avec conflits dans lequel des relations de compatibilité sont exprimées entre les couples d’objets ; un problème de bin packing bi-objectif dans lequel deux critères sont à minimiser, le nombre de bins utilisés et le nombre de couples en conflit placés dans le même bin ; un problème de bin packing avec objets fragiles dans lequel la somme des tailles des objets placés dans un bin ne dépasse la fragilité d’aucun de ces objets. / The bin packing problem consists in minimizing the number of containers (bins) needed to place a set of objects. This NP-complete problem has been, for many years, the subject of multiple theoretical and practical researches. It appears in many industrial applications such as cutting steel, wood and glass. The literature on the bin packing problem is rich and the algorithms and resolution approaches are also very are very diversified. However, solutions offered by these algorithms may not be useful when we deal with real industrial problems. In this thesis, we consider several types of constraints such as compatibility relations between objects. These constraints are issued from real life industrial applications. The research topic of this thesis focuses on solving a variety of bin packing problems. We are interested in lower and upper bounds for three problems: a bin packing problem with conflicts in which some compatibility relations exist between pairs of objects, a problem bi-objective bin packing in which two criteria are to minimize: the number of bins used and the number of conflicting couples of objects placed in the same bin, a problem of bin packing with fragile objects in which the sum of the sizes of objects placed in a bin does not exceed the fragility of any of these objects.

De nos jours, le problème de transport de marchandise occupe une place importante dans la vie économique des sociétés modernes. Le problème de ramassage et de livraison (pick-up and delivery problem) est l'un des problèmes dont une grande partie des chercheurs s'y est intéressée.Il s'agit de déterminer un circuit de plusieurs véhicules, de façon à servir à coût minimal un ensemble de clients et de fournisseurs répartis dans un réseau, satisfaisant certaines contraintes relatives aux véhicules, à leurs capacités et à des précédences entre les nœuds. Les travaux de recherche développés dans cette thèse portent sur le PDPTW (Pickup and Delivery Problem with Time Windows) à plusieurs véhicules (m-PDPTW). Ce dernier a été traité dans les deux cas : statique et dynamique. Nous avons proposé plusieurs approches de résolution du m-PDPTW basées sur les algorithmes génétiques, l'optimisation multicritère et le calcul des bornes inférieures, et ceci pour minimiser un certain nombre de critères comme : le nombre de véhicules utilisés, la somme des retards ou le coût total de transport. Ces approches ont donné de bons résultats, principalement au niveau de la minimisation de la somme des retards où nous avons obtenu, dans plusieurs cas, un retard nul avec un coût de transport tolérable

Notre problème consiste à déterminer le nombre de grands rectangles identiques nécessaires pour ranger une liste de rectangles sans modifier leur orientation. Nous proposons des méthodes pour calculer des bornes inférieures pour ce problème, essentiellement basée sur le concept de fonctions dual-réalisables. Nous proposons aussi deux méthodes exactes de type énumératives. L'une permet de déterminer si un ensemble de rectangles peut être contenu dans un rectangle unique. Elle repose sur une nouvelle relaxation du problème. La deuxième méthode permet de résoudre le problème général de bin packing en deux dimensions. Elle calcule pour cela une décomposition itérative de l'ensemble des rectangles à placer.

Cette thèse est consacrée à l'étude théorique d'une méthode de calibration automatique des pénalités en sélection de modèles. Cette méthode se base sur une heuristique, appelée "heuristique de pente", qui stipule l'existence d'une pénalité minimale telle que la solution optimale du problème de pénalisation vaut deux fois celle-ci. En pratique, on estime la pénalité optimale en estimant préalablement la pénalité minimale, caractérisée par un changement brutal dans le comportement de la procédure de sélection de modèles autour de ce seuil de pénalisation. L'analyse théorique du phénomène de pente se base sur un contrôle à la constante près des déviations de l'excès de risque et de l'excès de risque empirique des estimateurs considérés, mesurant respectivement leur performance en prédiction et leur performance empirique. Ceci suggère en premier lieu, une forte spécification de la structure du problème étudié. Nous validons l'heuristique de pente dans un cadre général qui s'articule autour d'une notion nouvelle en M-estimation, que nous appelons "contraste régulier", et nous développons une méthodologie de preuve inédite, permettant de traiter à la fois la question des bornes supérieures et des bornes inférieures de déviation des excès de risque à modèle fixé. Nous retrouvons ainsi la plupart des résultats déjà connus sur l'heuristique de pente. En effet, nous donnons trois exemples d'estimation par minimum de contraste régulier, à savoir la régression par moindres carrés sur des modèles linéaires, l'estimation de la densité par moindres carrés sur des modèles affines et l'estimation de la densité par maximum de vraisemblance sur des ensembles convexes. Ceci nous permet d'étendre les résultats précédemment établis dans le cas de la régression à des modèles plus généraux et de valider l'heuristique de pente pour un risque non quadratique en considérant le cas de l'estimation par maximum de vraisemblance. Enfin, notre méthodologie de preuve fournit des pistes précises de recherche pour des situations non régulières, comme on en trouve en classification ou plus généralement en théorie de l'apprentissage statistique.

Notre travail porte sur le problème de bin-packing qui consiste à déterminer le nombre minimum de grands rectangles (bins) nécessaires pour ranger un ensemble de petits rectangles (objets). Ce problème d'optimisation combinatoire est NP-difficile au sens fort. Nous proposons des prétraitements des objets permettant la valorisation des espaces perdus dans les bins et la diminution de la taille du problème à résoudre. Nous proposons une nouvelle méthode d'évaluation de bornes inférieures tenant compte de la possibilité de tourner les objets de 90 degrés. Nous procédons à une résolution approchée du problème grâce à deux nouvelles méthodes : une heuristique et un algorithme de recherche tabou.

Un grand nombre d'applications concrètes (Radar, Sonar, Télécoms ...) requièrent une étape de détection dont l'effet principal est de restreindre l'ensemble des observations disponibles pour l'estimation des paramètres inconnus. Par conséquent, nous établissons l'expression des bornes inférieures de l'Erreur Quadratique Moyenne (EQM) conditionnées par un test d'hypothèse binaire au moyen d'une approche didactique générale. Pour valider l'intérêt de cette démarche, nous montrons également à l'aide d'une application fondamentale, que le problème de la précision de prédiction de l'EQM vraie par une borne inférieure à faible RSB, peut provenir d'une formulation incorrecte de la borne inférieure ne prenant pas en compte la vraie problématique, à savoir les problèmes conjoints de détection-estimation.

Historiquement, les inégalités d'oracle ont été développées comme des outils particulièrement efficaces pour l'adaptation à un paramètre inconnu en statistique mathématique. Initialement dédiées à la démonstration de propriétés statistiques de certains estimateurs, elles peuvent s'inscrire dans le cadre plus général du problème l'agrégation où elles sont au centre de la définition d'une vitesse optimale d'agrégation. Elles constituent alors d'une part des outils mathématiques et d'autre part des résultats précis et non asymptotiques.<br />Les travaux faisant l'objet de cette thèse présentent différentes utilisations des inégalités d'oracle, d'abord dans un cadre général d'agrégation puis dans des modèles statistiques plus particuliers, comme l'estimation de densité et la classification. Les résultats obtenus sont une palette non exhaustive mais représentative de l'utilisation des inégalités d'oracle en statistique mathématique.

De nos jours, le problème de transport de marchandise occupe une place importante dans la vie économique des sociétés modernes. Le problème de ramassage et de livraison (pick-up and delivery problem) est l’un des problèmes dont une grande partie des chercheurs s’y est intéressée.Il s’agit de déterminer un circuit de plusieurs véhicules, de façon à servir à coût minimal un ensemble de clients et de fournisseurs répartis dans un réseau, satisfaisant certaines contraintes relatives aux véhicules, à leurs capacités et à des précédences entre les nœuds. Les travaux de recherche développés dans cette thèse portent sur le PDPTW (Pickup and Delivery Problem with Time Windows) à plusieurs véhicules (m-PDPTW). Ce dernier a été traité dans les deux cas : statique et dynamique. Nous avons proposé plusieurs approches de résolution du m-PDPTW basées sur les algorithmes génétiques, l’optimisation multicritère et le calcul des bornes inférieures, et ceci pour minimiser un certain nombre de critères comme : le nombre de véhicules utilisés, la somme des retards ou le coût total de transport. Ces approches ont donné de bons résultats, principalement au niveau de la minimisation de la somme des retards où nous avons obtenu, dans plusieurs cas, un retard nul avec un coût de transport tolérable / Nowadays, the transport goods problem occupies an important place in the economic life of modern societies. The PDPTW (Pickup and delivery problem with Time Windows) is one which a large part of researchers was interested. This is an optimization vehicles routing problem which must meet requests for transport between suppliers and customers satisfying precedence and capacity.Researchers developed in this thesis concerns the resolution of the PDPTW with multiple vehicles (m-PDPTW). The latter was treated in two cases: static and dynamic.We have proposed some approaches to solving the m- PDPTW, based on genetic algorithms, multicriteria optimization and the lower bounds, and this to minimize a number of criteria such as: the vehicles number, the total travel cost, and the total tardiness time.Computational results indicate that the proposed approach gives good results with a total tardiness equal to zero with a tolerable cost

Les travaux de cette thèse réalisée sous contrat CIFRE portent sur des problématiques d’ordonnancement de projets mufti-compétences. Définis en collaboration avec des experts de gestion de projet au sein de la société Néréide, deux modèles d’ordonnancement de projet font l’objet de cette étude. Dans le premier modèle, une tâche est définie par l’ensemble des compétences dont elle a besoin, la charge nécessaire de chaque compétence ainsi que la possibilité d’être interrompue ou non. Pour l’élaboration d’un planning prédictif respectant toutes les contraintes et minimisant la date de fin du projet, nous proposons des heuristiques de liste et métaheuristiques. Un modèle mathématique linéaire en nombres entiers ainsi que des bornes inférieures sont également développés. Dans un second temps, nous proposons, à partir d’un planning prédéfini, des méthodes pour ajuster le planning et répondre aux aléas survenus lors du déroulement du projet. Pour résoudre ce problème réactif, nous proposons une approche exacte itérative basée sur une formulation linéaire en nombres entiers ainsi qu’un algorithme génétique de type NSGA-II. Il s’agit donc d’une approche réactive bicritère où les solutions calculées doivent minimiser à la fois la date d’achèvement du projet et le nombre maximum de changements d’affectation de tâches aux employés. Dans le deuxième modèle, un cas particulier du modèle préemptif précédent est étudié. Nous nous intéressons au cas où une tâche nécessite une seule compétence avec possibilité de préemption seulement si les ressources ne sont pas disponibles (absence, congés, etc.). Dans ce modèle, une tâche est définie également par sa date de disponibilité et une date de fin souhaitée. Un coût d’utilisation personne/compétence est introduit. Pour ce dernier modèle, il s’agit d’un problème d’ordonnancement de projet bicritère, pour lequel les solutions calculées doivent minimiser le retard maximum et le coût global d’affectation des personnes aux tâches. Des heuristiques et métaheuristiques sont proposées pour ce modèle. Certaines méthodes de résolution proposées ont été implémentées sous forme d’add-ons intégrables au framework OFBiz. / The work presented in this thesis deals with multi-skill project scheduling problems. We have studied two models of project scheduling which are defined in collaboration with project management experts in Néréide company. In the first model, a task is defined by a set of required skills, the load needed for each skill as welI as the possibility of preemption. To build a predictive planning which respects aIl problem constraints and minimize the project completion time (makespan), we propose heuristics and meta-heuristics methods. A mixed integer mathematical linear programming model and lower bounds are also proposed. From a predefined planning, we propose an exact method based on a mathematical program as weIl as a genetic algorithm of type NSGA-II allowing to deal with disruptions occurred during the project realization. It is, therefore, a reactive approach in which we look for feasible solutions minimizing both the project completion date and the maximum number of resources assignment changes. In the second studied model, we focus on a case where a task exactly requires one skill with preemption possibility only in case of resources unavailability. In this model, a task is also characterized by its release and due date. A cost per person/skill is given. It is, therefore, a bi-objective problem in which the computed solutions must minimize both the maximum tardiness and the project global cost. Heuristics and meta-heuristics are proposed for solving this problem. Some proposed methods are integrated in the framework OFBiz as add-ons.

Nous étudions quatre problèmes d'ordonnancement sur machines parallèles. Ces quatre problèmes diffèrent par le critère que l'on cherche à minimiser : la somme des dates de fin, la somme pondérée des dates de fin, le retard total ou le retard total pondéré. Les jobs à ordonnancer sout soumis à des dates de disponibilité. Nous avons proposé pour ces quatres problèmes plusieurs règles de dominance. Une étude des bornes<br />inférieures a également été réalisée. Enfin, nous avons proposé une méthode de résolution exacte utilisant les règles de dominance ainsi que les bornes inférieures.