La présence de poussières au sein des plasmas est rencontrée dans de multiples environnements tels que les plasmas de laboratoires ou les plasmas de fusion. Les processus conduisant à leur formation constituent un vaste champ d'études depuis plusieurs années. Ce travail de thèse a pour objectif d'étudier un nouveau mécanisme de croissance des poussières dans un plasma radiofréquence capacitif en mélange argon/acétylène. Dans certaines conditions, il a été observé que des ondes de densité de poussières apparaissaient spontanément au sein des nuages de poussières. Elles peuvent grandement favoriser l'agglomération des particules grâce à l'importante énergie cinétique qu'elles leur transfèrent. Pour réaliser cette étude, différents outils diagnostics ont été développés. Pour sonder les populations de poussières nanométriques, un premier diagnostic basé sur des mesures d'extinction dans le domaine visible associé à une méthode inverse a été mis au point. Un second diagnostic permettant l'étude des populations d'agglomérats supra-microniques a été utilisé. Il est basé sur l'utilisation de l'imagerie rapide et l'analyse automatique des films à l'aide d'un algorithme adapté (TRACE). Enfin, une méthode d'extraction des poussières en vue d'analyses ex-situ et utilisant la force de thermophorèse a été développée.Ces diagnostics ont ensuite été appliqués à l'étude des ondes de poussières et des processus d'agglomération. Nous avons montré que des agglomérats de plusieurs centaines de microns pouvaient être formés en quelques dizaines de secondes. L'influence des conditions expérimentales sur les caractéristiques des ondes et des agglomérats formés a également été étudiée / The dust particle growth in plasmas is of major concern for safety issues in fusion reactors, and conversely has important industrial impacts. Dusty plasmas produced in laboratory, fusion, and in astrophysical environments have been therefore widely studied for many years to better understand the involved physical phenomena. In this thesis work, we have investigated a new dust-growing mechanism in a capacitive radio-frequency plasma of argon/acetylene mixture, with developing necessary diagnostic tools. The population of nano-particles was probed using visible-wavelength range extinction measurements combined with an inverse method. The motions and the collisions in enlarging agglomerates were followed through a fast-imaging device and the images were then analyzed using a compatible algorithm (TRACE). Ex-situ studies were also carried out on dust particles collected with an extraction technique based on the thermophoresis force. These diagnostic tools allowed us to observe a spontaneous emergence of dust density waves (DDWs) under specific experimental conditions. These waves impart substantial kinetic energy to the dust particles and thus enhance their agglomeration rate. Large agglomerates up to several hundreds of microns may thus be produced in a few tens of seconds. We have also studied the influence of experimental conditions (power, pressure) on the waves and the agglomerate characteristics

Cette thèse apporte plusieurs contributions dans le domaine des langages formels. Notre premier travail a été de montrer la pertinence des grammaires de graphes comme outil de démonstration de résultats fondamentaux sur les langages algébriques. Nous avons ainsi reformulé avec un point de vue géométrique les démonstrations du lemme des paires itérantes et du lemme de Parikh. Nous avons ensuite étendu aux graphes réguliers des algorithmes de base sur les graphes finis, notamment pour calculer des problèmes de plus court chemin. Ces extensions ont été faites par calcul de plus petits points fixes sur les grammaires de graphes. Enfin, nous avons caractérisé des familles générales de systèmes de récriture de mots dont la dérivation préserve la régularité ou l’algébricité. Ces familles ont été obtenues par décomposition de la dérivation en une substitution régulière suivie de la dérivation du système de Dyck / Pas de résumé en anglais

Notre travail porte sur le développement d'algorithmes performants d'application de grammaires locales, en prenant comme référence ceux des logiciels libres existants : l'analyseur syntaxique descendant d'Unitex et l'analyseur syntaxique à la Earley d'Outilex. Les grammaires locales sont un formalisme de représentation de la syntaxe des langues naturelles basé sur les automates finis. Les grammaires locales sont un modèle de construction de descriptions précises et à grande échelle de la syntaxe des langues naturelles par le biais de l'observation systématique et l'accumulation méthodique de données. L'adéquation des grammaires locales pour cette tâche a été testée à l'occasion de nombreux travaux. À cause de la nature ambiguë des langues naturelles et des propriétés des grammaires locales, les algorithmes classiques d'analyse syntaxique tels que LR, CYK et ne peuvent pas être utilisés dans le contexte de ce travail. Les analyseurs top-down et Earley sont des alternatives possibles ; cependant, ils ont des coûts asymptotiques exponentiels pour le cas des grammaires locales. Nous avons d'abord conçu un algorithme d'application de grammaires locales avec un coût polynomial dans le pire des cas. Ensuite, nous avons conçu des structures de donnés performantes pour la représentation d'ensembles d'éléments et de séquences. Elles ont permis d'améliorer la vitesse de notre algorithme dans le cas général. Nous avons mis en œuvre notre algorithme et ceux des systèmes Unitex et Outilex avec les mêmes outils afin de les tester dans les mêmes conditions. En outre, nous avons mis en œuvre différents versions de chaque algorithme en utilisant nos structures de données et algorithmes pour la représentation d'ensembles et ceux fournis par la Standard Template Library (STL) de GNU. Nous avons comparé les performances des différents algorithmes et de leurs variantes dans le cadre d'un projet industriel proposé par l'entreprise Telefónica I+D : augmenter la capacité de compréhension d'un agent conversationnel qui fournit des services en ligne, voire l'envoi de SMS à des téléphones portables ainsi que des jeux et d'autres contenus numériques. Les conversations avec l'agent sont en espagnol et passent par Windows Live Messenger. En dépit du domaine limité et de la simplicité des grammaires appliquées, les temps d'exécution de notre algorithme, couplé avec nos structures de données et algorithmes pour la représentation d'ensembles, ont été plus courts. Grâce au coût asymptotique amélioré, on peut s'attendre à des temps d'exécution significativement inférieurs par rapport aux algorithmes utilisés dans les systèmes Unitex et Outilex, pour le cas des grammaires complexes et à large couverture / This work focuses on the research and development of efficient algorithms of application of local grammars, taking as reference those of the currently existent open-source systems : Unitex's top-down parser and Outilex's Earley-like parser. Local grammars are a finite-state based formalism for the representation of natural language grammars. Moreover, local grammars are a model for the construction of fully scaled and accurated descriptions of the syntax of natural languages by means of systematic observation and methodical accumulation of data. The adequacy of local grammars for this task has been proved by multiple works. Due to the ambiguous nature of natural languages, and the particular properties of local grammars, classic parsing algorithms such as LR, CYK's and Tomita's cannot be used in the context of this work. Top-down and Earley parsers are possible alternatives, though they have an exponential worst-case cost for the case of local grammars. We have first conceived an algorithm of application of local grammars having a polynomial worst-case cost. Furthermore, we have conceived other optimizations which increase the efficiency of the algorithm for general cases, namely the efficient management of sets of elements and sequences. We have implemented our algorithm and those of the Unitex and Outilex systems with the same tools in order to test them under the same conditions. Moreover, we have implemented different versions of each algorithm, either using our custom set data structures or those included in GNU's implementation of the C++ Standard Template Library (STL). We have compared the performances of the different algorithms and algorithm versions in the context of an industrial natural language application provided by the enterprise Telefónica I+D : extending the understanding capabilities of a chatterbot that provides mobile services, such as sending SMSs to mobile phones as well as games and other digital contents. Conversation with the chatterbot is held in Spanish by means of Microsoft's Windows Live Messenger. In spite of the limited domain and the simplicity of the applied grammars, execution times of our parsing algorithm coupled with our custom implementation of sets were lower. Thanks to the improved asymptotic cost of our algorithm, execution times for the case of complex and large coverage grammars can be expected to be considerably lower than those of the Unitex and Outilex algorithms

Les problèmes d'optimisation continue sont nombreux, en économie, en traitement de signal, en réseaux de neurones, etc. L'une des solutions les plus connues et les plus employées est l'algorithme évolutionnaire, métaheuristique basée sur les théories de l'évolution qui emprunte des mécanismes stochastiques et qui a surtout montré de bonnes performances dans la résolution des problèmes d'optimisation continue. L’utilisation de cette famille d'algorithmes est très populaire, malgré les nombreuses difficultés qui peuvent être rencontrées lors de leur conception. En effet, ces algorithmes ont plusieurs paramètres à régler et plusieurs opérateurs à fixer en fonction des problèmes à résoudre. Dans la littérature, on trouve pléthore d'opérateurs décrits, et il devient compliqué pour l'utilisateur de savoir lesquels sélectionner afin d'avoir le meilleur résultat possible. Dans ce contexte, cette thèse avait pour objectif principal de proposer des méthodes permettant de remédier à ces problèmes sans pour autant détériorer les performances de ces algorithmes. Ainsi nous proposons deux algorithmes :- une méthode basée sur le maximum a posteriori qui utilise les probabilités de diversité afin de sélectionner les opérateurs à appliquer, et qui remet ce choix régulièrement en jeu,- une méthode basée sur un graphe dynamique d'opérateurs représentant les probabilités de passages entre les opérateurs, et en s'appuyant sur un modèle de la fonction objectif construit par un réseau de neurones pour mettre régulièrement à jour ces probabilités. Ces deux méthodes sont détaillées, ainsi qu'analysées via un benchmark d'optimisation continue / The problems of continuous optimization are numerous, in economics, in signal processing, in neural networks, and so on. One of the best-known and most widely used solutions is the evolutionary algorithm, a metaheuristic algorithm based on evolutionary theories that borrows stochastic mechanisms and has shown good performance in solving problems of continuous optimization. The use of this family of algorithms is very popular, despite the many difficulties that can be encountered in their design. Indeed, these algorithms have several parameters to adjust and a lot of operators to set according to the problems to solve. In the literature, we find a plethora of operators described, and it becomes complicated for the user to know which one to select in order to have the best possible result. In this context, this thesis has the main objective to propose methods to solve the problems raised without deteriorating the performance of these algorithms. Thus we propose two algorithms:- a method based on the maximum a posteriori that uses diversity probabilities for the operators to apply, and which puts this choice regularly in play,- a method based on a dynamic graph of operators representing the probabilities of transitions between operators, and relying on a model of the objective function built by a neural network to regularly update these probabilities. These two methods are detailed, as well as analyzed via a continuous optimization benchmark

La crise énergétique marquée par une flambée des prix du pétrole et les impératifs d’un développement durable font des énergies renouvelables une alternative qui suscitent aujourd'hui l’intérêt de plusieurs équipes de recherches. Le Sénégal, pays subsaharien, non producteur de pétrole n’est pas épargné par cette crise. Celle-ci se traduit par, une faible couverture du pays (en particulier les zones rurales) par le réseau électrique national. Pour faire face à cela, la nouvelle orientation en matière de politique énergétique met l’accent sur l’utilisation des énergies renouvelables notamment, le solaire et l’éolienne. L'objectif principal de cette thèse est de dégager une méthodologie de conception d’un site isolé de production d’énergie électrique à partir des énergies alternatives. Il s'agit à partir des caractéristiques d’un site (ressources d’énergie disponibles, besoins énergétiques) de :- mettre en place une démarche qui permette le choix d’une architecture du réseau et de dimensionner de façon optimale l’ensemble des constituants du réseau (machines, sources et dispositifs de stockage) en tenant compte de toutes les contraintes- concevoir un dispositif de commande des composantes et de gestion des flux d’énergie Cette thèse comprend trois chapitres :- Chapitre 1 : pose la problématique de l’énergie au Sénégal. L’organisation institutionnelle du sous-secteur de l’électricité, les réalisations et les projets en cours sont présentés. Aussi, une étude sur les architectures de micro-réseaux est faite. - Chapitre 2 : traite des outils et logiciels. Une étude comparative des principaux logiciels d’analyse, de conception et simulation des micro-réseaux est réalisée. L’ensemble des composants de notre système ont été modélisées. Les méthodes d’optimisation et des outils de représentation graphique (Bond Graph, GIC et REM) des systèmes ont été présentés. Une enquête menée et une recherche bibliographique nous ont permis d’évaluer le potentiel énergétique du site et les besoins des populations.- Chapitre 3 : il s’agit de l’application de notre outil sur un site isolé identifié au Sénégal (MBoro/Mer). L’optimisation à travers la fonction objectif coût annualisée du système (ACS) nous a permis de dimensionner de façon optimale notre système. Aussi la commande du système avec la Représentation Energétique Macroscopique (REM) a été conçue.Pour la suite du travail, il faudrait envisager une prise en charge des problèmes de disponibilité du système à travers une surveillance et une supervision du dispositif. Le volet socio-économique aussi est à intégrer dans le futur afin de satisfaire l’évolution des besoins et des habitudes des populations. / The energy crisis characterized by the oil products price rising and the imperatives of sustainable development do that renewable energies are an alternative today witch attract the interest of several research teams. Senegal, sub-Saharan country, not oil producer is not spared by this crisis. The consequence of this is a low coverage of the country (especially rural areas) by the national grid. For solving this, the new orientation of the energy policy focuses on the use of renewable energy particularly solar and wind.The main objective of this thesis is to identify a methodology of design of an isolated site of electrical energy production from alternative energies It is consists on, from site characteristics (energy resources, energy requirements):- to develop an approach that allows the choice of network architecture and sizing optimally all components of the network (machines, sources and storage devices) taking into account all the constraints- to design a device for controlling components and managing the energy flowsThis thesis contains three chapters:- Chapter 1 - poses the problem of energy in Senegal. The institutional organization of the electricity sub-sector and the ongoing projects are presented. Also, a study of micro- architectures networks is made.- Chapter 2 deals with tools and software. A comparative study of the main software of analysis, design and simulation of micro- network is realized. The components of our system have been modeled. Optimization methods and tools for graphical representation (Bond Graph, GIC and EMR) systems were presented. A survey and a literature review allowed us to evaluate the energy potential of the site and the needs of populations.- Chapter 3: This is the application of our tool on an isolated site identified in Senegal (MBoro / Mer). Optimization through the Annualized Cost of the System (ACS) objective function has allowed us to scale our system optimally. As the control system with Energetic Macroscopic Representation (EMR) has been designed.For further work should be considered a treatment of problems of availability of the system through monitoring and supervision of the system. The socio- economic component is also integrated in the future to meet the changing needs and habits of the population.

Le problème de tournées de véhicules (Vehicle Routing Problem - VRP) est un problème d'optimisation combinatoire utilisé généralement pour modéliser et résoudre des différents problèmes rencontrés dans les systèmes logistiques et de transport. Dans cette thèse, nous nous sommes intéressés à l'étude et la résolution d'une classe de problèmes du VRP appelée les problèmes de courses d'orientation (Team Orienteering Problem - TOP). Dans cette catégorie de problèmes, il est a priori impossible de visiter tous les clients en raison de ressources limitées. On associe plutôt un profit à chaque client qui représente sa valeur. Ce profit est collecté lorsque le client est visité par l'un des véhicules disponibles. L'objectif est donc de sélectionner un sous ensemble de clients à servir tout en maximisant le profit total collecté. Dans un premier temps, nous avons introduit une nouvelle généralisation pour le TOP que nous avons appelé le Clustered TOP ou CluTOP. Dans cette variante, les clients sont regroupés en sous-ensembles appelés clusters auxquels nous associons des profits. Pour résoudre cette variante, nous avons proposé un schéma exact basé sur l'approche des plans sécants avec des inégalités valides supplémentaires et des pré-traitements. Nous avons également conçu une méthode heuristique basée sur l'approche order first-cluster second. Cette heuristique hybride combine une heuristique de type Adaptive Large Neighborhood Search qui explore l'espace des solutions et une procédure de découpage qui explore l'espace de recherche des tours géants. De plus, la procédure de découpage est renforcée par une recherche locale afin de mieux explorer l'espace de recherche. Le deuxième problème traité dans ce travail s'appelle le Synchronized Team Orienteering Problem with Time Windows (STOPTW). Cette variante avait été initialement proposée afin de modéliser des scénarios liés à la protection des infrastructures stratégiques menacées par l'avancée des feux de forêts. En plus des contraintes de fenêtres de temps et des visites synchronisées, cette variante considère le cas d'une flotte de véhicules hétérogène. Pour résoudre ce problème, nous avons proposé une méthode heuristique basée sur l'approche GRASP×ILS qui est parvenue à dominer la seule approche existante dans la littérature. La dernière variante du TOP abordée dans cette thèse s'appelle le Set Orienteering Problem (SOP). Les clients dans cette variante sont regroupés en sous-ensembles appelés clusters. Un profit est associé à chaque groupe qui n'est obtenu que si au moins un client est desservi par le véhicule disponible. Nous avons proposé une méthode de coupes avec deux procédures de séparation pour séparer les contraintes d'élimination des sous-tours. Nous avons également proposé un algorithme Mémétique avec une procédure de découpage optimale calculée à l'aide de la programmation dynamique. / The Vehicle Routing Problem (VRP) is a family of Combinatorial Optimization Problems generally used to solve different issues related to transportation systems and logistics. In this thesis, we focused our attention on a variant of the VRP called the Team Orienteering Problem (TOP). In this family of problems, it is a priory impossible to visit all the customers due to travel time limitation on vehicles. Instead, a profit is associated with each customer to represent its value and it is collected once the customer is visited by one of the available vehicles. The objective function is then to maximize the total collected profit with respect to the maximum travel time. Firstly, we introduced a new generalization for the TOP that we called the Clustered TOP (CluTOP). In this variant, the customers are grouped into subsets called clusters to which we associate profits. To solve this variant, we proposed an exact scheme based on the cutting plane approach with additional valid inequalities and pre-processing techniques. We also designed a heuristic method based on the order first-cluster second approach for the CluTOP. This Hybrid Heuristic combines between an ANLS heuristic that explores the solutions space and a splitting procedure that explores the giant tours search space. In addition, the splitting procedure is enhanced by local search procedure in order to enhance its coverage of search space. The second problem treated in this work is called the Synchronized Team Orienteering Problem with Time Windows (STOPTW). This variant was initially proposed in order to model scenarios related to asset protection during escaped wildfires. It considers the case of a heterogeneous fleet of vehicles along with time windows and synchronized visits. To solve this problem, we proposed a heuristic method based on the GRASP×ILS approach that led to a very outstanding results compared to the literature. The last variant of the TOP tackled in this thesis called the Set Orienteering Problem (SOP). Customers in this variant are grouped into subsets called clusters. Each cluster is associated with a profit which is gained if at least one customer is served by the single available vehicle. We proposed a Branch-and-Cut with two separation procedures to separate subtours elimination constraints. We also proposed a Memetic Algorithm with an optimal splitting procedure based on dynamic programming.

La problématique de l'imagerie radar pose comme objectif de caractériser la cible observée. Dans le contexte de la télédétection appliquée aux milieux forestiers, il s'agit d'extraire les paramètres physiques constitutifs de la végétation.Ce manuscrit traite donc de la problématique de l'inversion de données électromagnétiques pour les basses fréquences radar, de la bande VHF à la bande P. Dans ces bandes de fréquences la canopée (feuilles et petites branches) n'interagit quasiment pas avec l'onde radar et la forêt peut donc, en première approximation, être représentée par des cylindres verticaux (troncs) et inclinés (branches primaires).Dans ce contexte, les méthodes d'inversion numériques s'appuient sur des modèles qui calculent, à de multiples reprises, les champs rayonnés par ce type de diffuseurs. Il faut alors choisir un modèle physique dont le compromis rapidité/précision penche en faveur de la rapidité, donc un modèle "approché". La précision du modèle choisi est ensuite étudié puis validé par comparaison à un modèle dont le compromis rapidité/précision est inversé, donc un modèle "exact". Parmi les nombreuses méthodes d'inversion, celle de l'algorithme génétique (AG) a été choisie. Cet algorithme bien connu est ici analysé puis amélioré pour répondre aux exigences du problème électromagnétique posé. Il est ensuite validé sur des données simulées et mesurées. Cette validation est aussi l'occasion d'étudier l'impact du jeu de données utilisé sur la rapidité et la précision de l'inversion, en fonction des configurations d'antenne (fréquences, positions, polarisations). / The objective of radar imaging is to characterize the observed target. In the case of forest remote sensing, the objective is to extract the component of the vegetation physical parameters.This manuscript addresses the problem of the inversion of electromagnetic data for low frequency wave, VHF band to the P band. In these frequency bands, the canopy (leaves and small branches) does not almost interact with the radar wave and the forest can thus, in first approximation, be represented by vertical cylinders (trunks) and tilted (primary branches).In this context, the numerical electromagnetic methods of inversion lean on models which calculate, many times, the scattered fields radiated by such broadcasters. It is then necessary to choose a physical model which compromise speed/accuracy tilts in favor of the speed, thus a "approached" model. The exactness of the chosen model is then studied and then validated by comparison to a model which the compromise speed/accuracy is inverted, thus a "exact" model. Among the many numerical methods of inversion, that of the genetic algorithm (AG) was chosen. This algorithm, well known, is analyzed here then improved to meet the requirements of the composed electromagnetic problem. It is then validated on simulated and measured data. This validation is also an opportunity to study the impact of the set of data used on the speed and the precision of the inversion, according to the configurations of antenna (frequencies, positions, polarizations).

L'hydrogène est l'un des vecteurs énergétiques les plus prometteurs dans la recherche d'un mix énergétique plus durable. Plusieurs études et feuilles de route ont été réalisées sur le potentiel d'une économie « hydrogène » et ont identifié que même si de nombreuses technologies requisessont déjà disponibles aujourd'hui, le déploiement d'infrastructures hydrogène constitue la tâche la plus difficile de son développement, dont la mesure où on doit atteindre des coûts compétitifs et avoir l'acceptation du marché. La conception de la chaîne logistique de l’hydrogène (HSC), enparticulier à des fins de mobilité, implique une série de décisions importantes à différents niveaux (sources d'énergie, production, transport et stockage) et peut être considérée comme un problème multi-échelle et multi-période avec plusieurs parties prenantes. L'objectif de ce travail est de proposer un cadre méthodologique pour aborder le problème de conception de la HSC de manière complémentaire au travail proposé dans le travail de doctorat de (Sofia de Leon Almaraz, 2014) dans lequel une formulation multi-objectif a été mise en œuvre via la méthodologie - contrainte pour obtenir le front de Pareto, en optimisant trois objectifs en même temps : le coût journalier total, le potentiel de réchauffement global et un indice de risque de sécurité. Une analyse de sensibilité basée sur un plan d'expérience en utilisant les méthodes de plan factoriel et surface de réponse a été réalisée pour identifier les principaux paramètres (facteurs) et leur interaction affectant le critère économique, soit le coût journalier total (TDC) (réponse), englobant les coûts capitaux et opérationnels. Cette analyse de sensibilité souligne que la demande est de loin le paramètre le plus important qui conditionne fortement le critère TDC, de sorte que davantage d'efforts sont nécessaires pour modéliser l'incertitude de la demande de façon homogène. Dans la formulation initiale de la conception de la HSC, la taille du problème liée au nombre de variables binaires conduit souvent à des difficultés pour résoudre le problème. Dans ce travail, le potentiel des algorithmes génétiques (GA) via une variante de NSGA-II est exploré pour faire face à la formulation multi-objectif, afin de produire automatiquement le front de Pareto. La formulation du modèle a ensuite été étendue pour tenir compte de l'incertitude de la demande, ce qui donne plus de robustesse à l'approche proposée. Deux études de cas soutiennent cette analyse : d'abord au niveau régional, les résultats de la conception de la HSC pour l'ancienne région Midi-Pyrénées obtenus avec les deux modèles sont comparés. Les solutions obtenues par GA présentent le même ordre de grandeur que celles obtenues avec MILP (Programmation Linéaire en Nombres Entiers) dans le problème mono-critère, mais de meilleures solutions de compromis sont produites dans la formulation multi-objectif et des résultats plus flexibles sont obtenues avec la modélisation de l’incertitude de demande. Puis l’écosystème aéroportuaire, Tarbes-Lourdes, a été étudié : l'infrastructure aéroportuaire est une étude de cas intéressante, car un aéroport est une source d'émissions qui affectent le climat à cause des émissions générées par les activités faites à l'intérieur et à l'extérieur du périmètre de l'aéroport, liées à l’opération et utilisation de l’aéroport. Enfin, une analyse post-optimale sur une solution de compromis de la HSC est réalisée sur la base d'une évaluation sociale, via deux analyses coûts-bénéfices (CBA) d'un point de vue social (SCBA) et gouvernemental (subventions et taxes), montrant que l'incorporation d'externalités aide à financer une proportion importante des coûts. L'approche SCBA pour le déploiement de l'hydrogène intègre les avantages sociétaux induits à travers la réduction des émissions de gaz à effet de serre, la réduction de la pollution atmosphérique mais aussi les coûts sociaux par l'augmentation de la consommation de platine.

Cette thèse s’intéresse à un problème de bin-packing en deux dimensions avec des défauts sur les bins rencontré dans l’industrie verrière. Les plans de découpe sont guillotine 4-stage exact, les objets à couper sans défauts.Une possible résolution utilise la décomposition de Dantzig-Wolfe puis une génération de colonnes et un branch-and-price. Cela est impossible dans notre cas du fait d’instances de trop grande taille. Nous résolvons d’abord le problème de pricing sans défauts par un algorithme incrémental de labelling basé sur un programme dynamique (DP), représenté par un problème de flot dans un hypergraphe. Notre méthode est générique pour les problèmes de sac-à-dos guillotine mais ne résout pas de larges instances en un temps de calcul raisonnable. Nous résolvons alors le problème de bin-packing sans défauts grâce à un DP et une heuristique de diving. Le DP génère des colonnes “non propres”,ne pouvant pas participer à une solution entière. Nous adaptons le diving pour ce cas sans perte d’efficacité. Nous l’étendons alors au cas avec défauts. Nous réparons d’abord heuristiquement une solution du problème sans défauts. La fixation des colonnes dans le diving sans-défaut est ensuite modifiée pour gérer les défauts. Les résultats industriels valident nos méthodes. / This thesis deals with a two-dimensional bin-packing problem with defects on bins from the glass industry. Cutting patterns have to be exact 4-stage guillotine and items defect-free. A standard way to solve it isto use Dantzig-Wolfe reformulation with column generation and branch-and price.This is impossible in our case due to large instance size. We first study and solve the defect-free pricing problem with an incremental labelling algorithm based on a dynamic program (DP), represented as a flow problem in a hypergraph. Our method is generic for guillotine knapsack problems but fails to solve large instance in a short amount of time. Instead we solve the defect freebin-packing problem with a DP and a diving heuristic. This DP generatesnon-proper columns, cutting patterns that cannot be in an integer solution.We adapt standard diving heuristic to this “non-proper” case while keeping itseffectiveness. We then extend the diving heuristic to deal with defects. Ourfirst proposal heuristically repairs a given defect-free solution. Secondly the defect-free diving heuristic is adjusted to handle defects during column fixing.Our industrial results outline the effectiveness of our methods.

L'objectif de la thèse est l'étude mathématique et l'analyse numérique du problème non linéaire de Sobolev. Un premier chapitre est consacré à l'analyse a priori pour le problème de Sobolev où on utilise des méthodes de semi-discrétisation explicite en temps. Des estimations d'erreurs ont été obtenues assurant que les schémas numériques utilisés convergent lorsque le pas de discrétisation en temps et le pas de discrétisation en espace tendent vers zéro. Dans le second chapitre, on s'intéresse au problème de Sobolev singulièrement perturbé. En vue de la stabilité des schémas numériques, on utilise dans cette partie des méthodes numériques implicites (la méthode d'Euler et la méthode de Crank- Nicolson) pour discrétiser le problème par rapport au temps. Dans le troisième chapitre, on présente des applications et des illustrations où on utilise le logiciel "FreeFem++". Dans le dernier chapitre, on considère une équation de type Sobolev et on s'intéresse à la dérivation d'estimations d'erreur a posteriori pour la discrétisation de cette équation par la méthode des éléments finis conforme en espace et un schéma d'Euler implicite en temps. La borne supérieure est globale en espace et en temps et permet le contrôle effectif de l'erreur globale. A la fin du chapitre, on propose un algorithme adaptatif qui permet d'atteindre une précision relative fixée par l'utilisateur en raffinant les maillages adaptativement et en équilibrant les contributions en espace et en temps de l'erreur. On présente également des essais numériques. / The purpose of this work is the mathematical study and the numerical analysis of the nonlinear Sobolev problem. A first chapter is devoted to the a priori analysis for the Sobolev problem, where we use an explicit semidiscretization in time. A priori error estimates were obtained ensuring that the used numerical schemes converge when the time step discretization and the spatial step discretization tend to zero. In a second chapter, we are interested in the singularly perturbed Sobolev problem. For the stability of numerical schemes, we used in this part implicit semidiscretizations in time (the Euler method and the Crank-Nicolson method). Our estimates of Chapters 1 and 2 are confirmed in the third chapter by some numerical experiments. In the last chapter, we consider a Sobolev equation and we derive a posteriori error estimates for the discretization of this equation by a conforming finite element method in space and an implicit Euler scheme in time. The upper bound is global in space and time and allows effective control of the global error. At the end of the chapter, we propose an adaptive algorithm which ensures the control of the total error with respect to a user-defined relative precision by refining the meshes adaptively, equilibrating the time and space contributions of the error. We also present numerical experiments.