Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.

Le polyèdre associé à un problème d'optimisation combinatoire est l'enveloppe convexe des (vecteurs d'incidence des) solutions réalisables de ce problème. De nombreux problèmes d'optimisation combinatoire se formulent comme une maximisation de fonctions linéaires sur les polyèdres qui leurs sont associés. La description du polyèdre par un système d'inéquations linéaires est intimement liée à la résolution du problème correspondant, par le biais de la programmation linéaire. Afin de déterminer un tel système, une approche classique consiste à décomposer le problème en sous-problèmes tels que les polyèdres associés soient connus ; une composition ultérieure de ces derniers conduit à une description du polyèdre associé au problème considéré. L'objet principal de cette thèse est l'étude de la composition des polyèdres. Dans un premier temps, une approche de composition, basée sur la programmation dynamique et les méthodes de projection polyédrale, est étudiée et des résultats généraux sont proposés, permettant ainsi d'unifier des recherches existantes dans ce domaine. Cette approche est, ensuite, appliquée à la composition de polyèdres associés au problème du voyageur de commerce. En seconde partie, considérant le problème du stable, des opérations sur les graphes (composition par identification de sous-graphes de deux graphes donnés, adjonction d'une nouvelle arête) sont traitées. Des résultats polyédraux sont donc donnés, et des conséquences concernant la perfection et la h-perfection des graphes sont montrés

.

Les travaux présentés dans le cadre de cette thèse portent sur l'étude, la conception, le développement et le test d'un système de reconnaissance de mots manuscrits non contraints en-ligne pour une application omni-scripteurs. Le système proposé repose sur une architecture hybride neuro-markovienne comportant d'une part, un réseau de neurones à convolution (TDNN et/ou SDNN), et d'autre part des modèles de Markov à états cachés (MMC). Le réseau de neurones a une vision globale et travaille au niveau caractère, tandis que le MMC s'appuie sur une description plus locale et permet le passage du caractère au niveau mot. Nous avons d'abord étudié le système de reconnaissance au niveau caractère isolé (digits, majuscules, minuscules) et optimisé les architectures des réseaux en termes de performances et de taille. La seconde partie du travail a porté sur le passage au niveau mot. Ici, l'effort a consisté avant tout à la définition d'un schéma d'apprentissage global au niveau mot qui permet d'assurer la convergence globale du système, en définissant une fonction d'objectif qui mixe des critères basés modèle générateur (typiquement par maximum de vraisemblance) et des critères discriminants (de type maximum d'information mutuelle). Les différentes résultats présentés (sur les bases MNIST, IRONOFF, UNIPEN) montrent l'influence des principaux paramètres du système, soit en termes de topologie, de sources d'information, de modèles d'apprentissage (nombre d'états, pondération des critères, durée).

En microrobotique, la commande des systèmes est délicate car les phénomènes physiques liés à l'échelle microscopique sont complexes. Les méthodes dites d'apprentissage par renforcement constituent une approche intéressante car elles permettent d'établir une stratégie de commande sans connaissance \emph(a priori) sur le système. Au vu des grandes dimensions des espaces d'états des systèmes étudiés, nous avons développé une approche parallèle qui s'inspire à la fois des architectures comportementales et de l'apprentissage par renforcement. Cette architecture, basée sur la parallélisation de l'algorithme du Q-Learning, permet de réduire la complexité du système et d'accélérer l'apprentissage. Sur une application simple de labyrinthe, les résultats obtenus sont bons mais le temps d'apprentissage est trop long pour envisager la commande d'un système réel. Le Q-Learning a alors été remplacé par l'algorithme du Dyna-Q que nous avons adapté à la commande de systèmes non déterministes en ajoutant un historique des dernières transitions. Cette architecture, baptisée Dyna-Q parallèle, permet non seulement d'améliorer la vitesse de convergence, mais aussi de trouver de meilleures stratégies de contrôle. Les expérimentations sur le système de manipulation montrent que l'apprentissage est alors possible en temps réel et sans utiliser de simulation. La fonction de coordination des comportements est efficace si les obstacles sont relativement éloignés les uns des autres. Si ce n'est pas le cas, cette fonction peut créer des maxima locaux qui entraînent temporairement le système dans un cycle. Nous avons donc élaboré une autre fonction de coordination qui synthétise un modèle plus global du système à partir du modèle de transition construit par le Dyna-Q. Cette nouvelle fonction de coordination permet de sortir très efficacement des maxima locaux à condition que la fonction de mise en correspondance utilisée par l'architecture soit robuste.

Le développement simultané de terminaux mobiles multimédia (smartphones, tablettes) et de réseaux d'accès offrant des débits élevés conduit à une explosion du trafic liés aux contenus multimédia. Cette croissance nécessite un partage efficace des ressources radio entre fournisseurs de contenus (dans le cas de la diffusion) ou entre récepteurs (dans le cas de services de vidéo à la demande). Cette thèse propose des outils de partage équitable des ressources en termes de qualité des contenus multimédia reçu et de délai de transmission dans les deux contextes précédents. La variété des compromis débit-distorsion des contenus multimédia est exploitée à cet effet. Dans un premier temps, une solution centralisée de contrôle conjoint du débit de codage et de transmission de plusieurs programmes transmis sur un même canal est considérée. L'objectif est de fournir des flux de qualités similaires avec des variations limitées, tout en assurant des délais de transmission comparables. Ce problème est résolu en synthétisant une commande prédictive à l'aide d'outils d'optimisation sous contrainte. Dans un second temps, seule l'allocation de bande est centralisée, le contrôle des caractéristiques de compression de chaque flux est réalisé de manière distribuée. Le contrôleur centralisé ne renvoie que le niveau de remplissage des tampons associés à chaque flux aux fournisseurs de contenus distants. Une stratégie de régulation des débits de codage est alors mise en place par ces fournisseurs, de manière à réguler le niveau en bits ou en image des tampons. La stabilité de ce système de régulation couplé est étudiée en détails. Enfin, l'optimisation inter-couches d'une chaine de transmission de contenus multimédia scalable est considérée. Ce problème est formulé dans le contexte de la programmation dynamique. Lorsque des modèles de complexité raisonnable sont considérés et avec des caractéristiques du système bien connues, des solutions optimales peuvent être obtenues. Des techniques d'apprentissage sont mises en œuvre, lorsque le système n'est que partiellement connu, par exemple, lorsque l'état du canal de transmission parvient avec du retard à l'organe de commande.

Dans le contexte automobile actuel, étroitement lié à la volonté de réduire les émissions de CO2 dans l'atmosphère, les véhicules hybrides demeurent un passage obligé à court et moyen terme. Un véhicule hybride possède deux sources d'énergie pour assurer sa propulsion : en général un moteur thermique constitue la principale source d'énergie, tandis qu'un moteur électrique représente la source secondaire. La capacité d'un véhicule hybride à consommer moins de carburant, et à rejeter moins de CO2, provient de la présence du moteur électrique. Celui-ci peut être utilisé soit conjointement avec le moteur thermique, soit seul, aucun carburant n'étant alors consommé. La présence de ces deux sources d'énergie impose au système global d'être régi par une stratégie de contrôle déterminant la répartition du couple entre les deux moteurs en fonction de l'état de charge de la batterie. Cette répartition peut être déterminée pour être optimale vis-à-vis de critères tels que la consommation de carburant, les émissions de polluants, etc. L'objectif de la thèse est de développer des méthodes d'optimisation de la répartition de couple entre les deux moteurs d'un véhicule hybride, dans l'objectif de minimiser les émissions de CO2. Une première étape a consisté à développer des modèles représentatifs d'une architecture type adaptés aux types d'optimisation réalisée. Les algorithmes d'optimisation diffèrent selon qu'ils soient capables de traiter des problèmes hors-ligne, ou temps-réel. Parmi les algorithmes d'optimisation hors-ligne étudiés, la programmation dynamique a été utilisée pour déterminer le dimensionnement optimal des éléments principaux d'une architecture hybride, et en déterminer le gain théorique par rapport à une motorisation traditionnelle. Par ailleurs, un algorithme de tir original nommé SCOP a été développé, celui-ci permettant de traiter des problèmes de commande optimale avec contraintes sur l'état, tout en multipliant les performances par 50 par rapport à la méthode de programmation dynamique. Une stratégie de contrôle temps-réel, basée sur l'Equivalent Consumption Minimization Strategy (ECMS) utilisant le principe de Pontryagin, a été développée et implémentée sur un prototype de véhicule hybride, une Smart équipée d'un alterno-démarreur. Les résultats obtenus démontrent de l'action de la stratégie pour la réduction de la consommation de carburant et des émissions de CO2.

Nos travaux de recherche portent sur le problème de prise en compte des contraintes liées aux ressources humaines, en termes d'affectation des opérateurs aux machines, dans les problèmes d'ordonnancement d'atelier. Ce problème intégrant l'affectation des opérateurs aux machines consiste à déterminer 1 'état d'atelier au cours du temps, et à considérer le problème d'ordonnancement d'atelier dans sa globalité en prenant en compte l'influence de l'affectation des ressources humaines sur les activités de production. Ceci impose en plus de la gestion de la séquence des travaux, la gestion des affectations des hommes aux postes de travail. Nous avons considéré le cas où les productivités des machines dépendant de 1 'affectation des opérateurs. Nous avons supposé que le nombre d'opérateurs est inférieur au nombre de machines, un opérateur peut superviser simultanément plusieurs machines et que la supervision simultanée de plusieurs machines par un opérateur diminue les productivités de ces dernières. L'originalité de nos travaux de recherche est liée au fait que les durées opératoires des travaux sont variables dans le temps et sont fonctions de 1 'évolution des affectations des opérateurs aux machines dans le temps. Deux grandes parties composent nos travaux de recherche. La première partie porte sur le problème de modélisation de 1 'affectation des opérateurs aux machines. Elle consiste en la proposition d'un cadre théorique pour 1 'intégration des contraintes liées à la prise en compte des ressources humaines, en terme d'affectation des opérateurs aux machines, dans la modélisation des problèmes d'ordonnancement d'atelier. Une définition d'un problème d'ordonnancement d'atelier impliquant l'aspect" ressources humaines" est alors proposée. La seconde partie a porté sur une application de la modélisation proposée dans la première partie pour le cas d'une production cyclique. Plus précisément, nous avons étudié le problème d'existence d'une affectation des opérateurs réalisant un ordonnancement cyclique pour un atelier_ de type Flow Shop. Nous avons supposé qu'un ordonnancement cyclique, défini par une durée de cycle et un ensemble de travaux à réaliser durant cette durée, est donné pour des productivités nominales des machines et sans aucune prise en compte des ressources humaines. Par conséquent, et dans le cas où le nombre d'opérateurs est inférieur au nombre de machines et que l'affectation des opérateurs conditionnent les productivités des machines, 1 'introduction et la considération des ressources humaines pour la réalisation de l'ordonnancement cyclique pourrait allonger la durée d'exécution des travaux et remettre en cause la durée de cycle. Nous avons étudié ce problème d'existence d'une affectation des opérateurs réalisable pour Flow Shop Cyclique pour trois modes de réaffectations des opérateurs : calendaire, sur évènement de fin de tâche et libre. Nous avons présenté une formulation mathématique du problème pour ces trois modes de réaffectation des opérateurs, démontré que ce problème est NP-complet pour les deux modes calendaires et sur événement, et qu'une restriction du problème de mode de réaffectation libre est NP-complet. Nous avons également proposé, pour ces trois modes, un modèle mathématique linéaire en nombre entier. Une approche de résolution basée sur le principe de la programmation dynamique a été proposée pour les deux modes réaffectation calendaire et sur événement.

La gestion d'énergie d'un véhicule hybride consiste à développer une stratégie, qui détermine à chaque instant la répartition des flux d'énergie thermique et électrique, minimisant la consommation globale du véhicule. La modélisation de la consommation du véhicule hybride permet d'écrire cette problématique sous la forme d'un problème d'optimisation dynamique sous contraintes d'évolutions. Ce problème est résolu de façon optimale lorsque l'ensemble des conditions de roulage sont connues à priori. La commande optimale obtenue sert de référence pour évaluer la performance des stratégies embarquées dans le véhicule. En s'appuyant sur la théorie de l'optimisation optimale, deux stratégies ont été crées : l'une prédictive qui a été testée sur un simulateur numérique et une autre, reposant sur le principe du problème dual, qui a été embarqué avec succès sur deux véhicules hybrides conventionnels. Pour les hybrides rechargeables, leur capacité énergétique et la possibilité de se recharger sur le réseau électrique libère des contraintes dans la problématique d'optimisation énergétique. C'est pourquoi, une nouvelle stratégie spécifique a été développée dans l'objectif de profiter au maximum de l'énergie électrique embarquée pour minimiser les émissions du véhicule. Pour l'ensemble des véhicules hybrides, la batterie est un composant clef dont le vieillissement vient modifier sa rentabilité économique et énergétique. C'est pourquoi un observateur a été conçu pour fournir une information précise de la température interne des cellules. Cette information est utilisée par une stratégie spécifique optimisant la consommation tout en préservant la batterie des températures extrêmes, nuisibles à sa longévité.

Depuis une dizaine d'années, les constructeurs et les grands groupesdu secteur de l'automobile se sont mobilisés autour de la recherche et dudéveloppement de nouveaux prototypes de véhicules économes (moins consommateursd'énergie) et propres (moins de rejets de polluants) tels queles véhicules hybrides et tout électriques. C'est une nouvelle mutation. Ellefait profondément évoluer l'automobile, d'une architecture de propulsionthermique, devenue maîtrisée mais fortement polluante, vers une tractionélectrique ou hybride plus complexe et peu, voire pas du tout, maîtrisée ;le nombre de composants (sources d'énergie, actionneurs, contrôleurs, calculateurs,...) devient important, de nature multidisciplinaire et possédantbeaucoup de non linéarités. De plus, faute de maturité dans ce domaine, àce jour l'industrie de l'automobile ne possède pas encore les connaissancessuffisantes nécessaires à la modélisation, à la simulation et à la conceptionde ces nouveaux véhicules et plus particulièrement les dispositifs relatifs auxsources d'énergie et aux différents actionneurs de propulsion.Les travaux de cette thèse visent à donner des méthodes de conceptiond'une chaine de traction hybride et d'en gérer la gestion de l'énergie. Lathèse s'appuie sur l'exemple de la conception et la gestion de l'énergie d'unvéhicule hybride basé sur une pile à combustible et des batteries.Dans un premier temps, un méthode de dimensionnement des composantsde la chaine de traction est présentée : Elle consiste en l'étude statistique decycle de conduite générés pseudo aléatoirement représentatif de la conduiteen condition réelle de véhicule. Un générateur de cycle de conduite à été créeet est présenté, et la méthode de dimensionnement de la source primaire, iciune pile a combustible, ainsi que le source secondaire de puissance, ici desbatteries, est détaillée. Un exemple est pris pour illustrer cette méthode avecla conception d'un véhicule de type camion poubelle décrivant des cycles deconduites urbains à arrêts fréquents.Dans un second temps, la gestion de l'énergie de la chaine de traction hybridesérie est étudiée : une gestion de l'énergie "offline" est présentée, basé surl'optimisation par programmation dynamique. Cette optimisation permetd'avoir le découpage de la puissance par les deux sources de la chaine detraction de manière optimal pour un cycle précis. De part l'aspect déterministede la programmation dynamique, les résultats servent de référence quant aufuturs développements de gestion temps réel.Un contrôleur temps réel basé sur la logique floue est ainsi exposé et lesrésultats sont comparés par rapport à la gestion "offline". Le contrôleurest ensuite optimisé et rendu adaptatif par un algorithme génétique et unalgorithme de reconnaissance de type de profil routier.Enfin, une introduction à la gestion de l'énergie dans les véhicules hybrides de type : "plug in" est présentée : Elle repose sur le principe de la déterminationde la distance restante à parcourir par la reconnaissance de la destination àl'aide d'une matrice de probabilité de Markov.