La plupart des travaux en ordonnancement repose sur un modèle déterministe, peu adapté à la réalité de l'ordonnancement d'atelier. En effet, les ateliers de production sont soumis à un certain nombre d'incertitudes. C'est pourquoi l'ordonnancement sous incertitudes est un domaine en pleine expansion.<br /><br />D'autre part, l'humain n'est généralement pas pris en compte dans l'élaboration de la méthode d'ordonnancement. Pourtant, l'humain joue un rôle central dans le processus d'ordonnancement, et ses connaissances du terrain sont précieuses. C'est pourquoi nous pensons que des systèmes homme-machine efficaces sont nécessaires au bon fonctionnement des méthodes d'ordonnancement d'atelier.<br /><br />Pour cela, nous nous reposons sur l'ordonnancement de groupes. Cette méthode d'ordonnancement d'atelier comporte différents avantages pour notre recherche : c'est une méthode d'ordonnancement sous incertitudes et sa structure est facilement manipulable par l'humain. Nous étudions les systèmes homme-machine existant pour cette méthode d'ordonnancement. Nous proposons ensuite un nouveau système homme-machine, afin d'améliorer la coopération. Dans ce système, nous utilisons la qualité dans le meilleur des cas dans un ordonnancement de groupes. Comme ce thème n'est pas encore abordé dans la littérature, nous proposons des bornes inférieures, des heuristiques et une méthode exacte pour résoudre ce problème.

Les problèmes étudiés dans cette thèse sont motivés par des questions issues de l'optimisation des réseaux de télécommunication. Nous avons abordé ces problèmes sous deux angles principaux. D'une part nous avons étudié leurs propriétés de complexité et d'inapproximabilité. D'autre part nous avons dans certains cas proposé des algorithmes exacts ou d'approximation ou encore des méthodes heuristiques que nous avons pu comparer à des formulations en programmes linéaires mixtes sur des instances particulières.<br /><br />Nous nous intéressons aussi bien aux réseaux de coeur qu'aux réseaux d'accès. Dans le premier chapitre, nous présentons brièvement les réseaux d'accès ainsi que les réseaux multiniveaux de type IP/WDM et l'architecture MPLS que nous considérons pour les réseaux de coeur. Ces réseaux sont composés d'un niveau physique sur lequel est routé un niveau virtuel. A leur tour les requêtes des utilisateurs sont routées sur le niveau virtuel. Nous abordons également la tolérance aux pannes dans les réseaux multiniveaux qui motive deux problèmes que nous avons étudiés.<br /><br />Le second chapitre est consacré à la conception de réseaux virtuels. Dans un premier temps nous modélisons un problème prenant en compte la tolérance aux pannes, puis nous en étudions un sous-problème, le groupage. Notre objectif est de minimiser le nombre de liens virtuels, ou tubes, à installer pour router un ensemble de requêtes quelconque lorsque le niveau physique est un chemin orienté.<br /><br />Le troisième chapitre traite des groupes de risque (SRRG) induits par l'empilement de niveaux au sein d'un réseau multiniveaux. Grâce à une modélisation par des graphes colorés, nous étudions la connexité et la vulnérabilité aux pannes de ces réseaux.<br /><br />L'objet du quatrième chapitre est le problème du placement d'instruments de mesure du trafic dans le réseau d'accès d'un opérateur. Nous considérons aussi bien les mesures passives qu'actives. La surveillance du trafic possède de nombreuses applications, en particulier la détection de pannes et l'évaluation des performances d'un réseau.

Dans cette thèse, nous nous intéressons aux problèmes du knapsack multidimensionnel à choix multiple. Ils interviennent essentiellement en télécommunication. Nous proposons de nouvelles méthodes hybrides de résolution exacte et approchée. Dans un premier temps, nous proposons des méthodes heuristiques en se basant sur les techniques de génération de colonnes et d'arrondi. Ensuite, nous abordons une méthode de recherche locale, dite méthode de branchement local, où des contraintes linéaires sont introduites pour intensifier et diversifier la recherche. Cette méthode est ensuite hybridée avec la génération de colonnes et une technique d'arrondi. Concernant la résolution exacte, nous nous basons sur une méthode de "Branch and cut". Nous commençons par proposer de nouvelles contraintes valides pour le problème. Ensuite, nous les associons à des contraintes de couverture locales et globales dans un schéma énumératif. Les approches heuristiques et l'algorithme exact que nous proposons sont comparés à d'autres heuristiques de la littérature et au Solveur de programmes linéaires Cplex . L'ensemble de ces tests numériques ont été menés sur des instances ardues de la littérature ainsi que sur des instances générées aléatoirement de taille modérée.

Un objectif de cette thèse est de fournir des outils d'analyse, de conception et d'implantation des approches métaheuristiques pour l'optimisation combinatoire en les formulant dans le cadre des systèmes multi-agents. L'accent est mis sur la potentialité de mise en œuvre distribuée des approches et sur l'utilisation de techniques d'apprentissage permettant d'adapter dynamiquement des méthodes de recherche.<br /><br />Dans le cadre de cette thèse nous proposons tout d'abord, un framework organisationnel et multi-agent pour la modélisation et l'implantation de métaheuristiques. Ce framework nommé AMF (Agent Metaheuristic Framework), introduit un modèle organisationnel de métaheuristiques qui décrit le système sous la forme d'une organisation composée de rôles en interaction. Le premier objectif de ce modèle est de donner un cadre d'analyse et de comparaison des différentes métaheuristiques existantes. Ensuite, il doit faciliter la conception de nouveaux algorithmes en encourageant une approche multi-agent. L'intérêt de l'approche organisationnelle, actuellement utilisée dans les systèmes multi-agents, est de pouvoir décrire un système aussi bien comme un tout, le système multi-agent, que comme un assemblage de composants, les agents. De plus, cette approche permet de distinguer l'analyse des fonctions du système, de l'analyse de son architecture. Enfin, l'approche organisationnelle encourage la modularité et la réutilisation des modèles. Nous proposons en complément de ce modèle un guide méthodologique. Il définit un ensemble d'étapes permettant de passer du modèle organisationnel à une méthode d'optimisation exprimée en termes d'agent.<br /><br />Ensuite, nous présentons une métaheuristique fondée sur la métaphore de la coalition, CBM (Coalition Based Metaheuristic), mettant en avant l'intérêt d'utiliser les systèmes multi-agents pour la conception de métaheuristiques. Dans cette métaheuristique, la recherche de solution est effectuée par un ensemble d'agents regroupés dans une coalition. Chaque agent est capable d'effectuer indépendamment des autres une recherche dans l'espace des solutions à l'aide d'opérateurs de déplacement dans un voisinage de la solution courante et d'adapter sa stratégie par apprentissage par renforcement. Des mécanismes de coopération entre agents permettent d'améliorer l'efficacité de la recherche. La structure de coalition permet d'intégrer naturellement au système de résolution des aspects de distribution et de décentralisation du contrôle, de même que des procédés d'apprentissage individuels et collectifs. L'efficacité de notre approche est évaluée expérimentalement en traitant deux problèmes d'optimisation combinatoire : un problème de tournées de véhicules et un problème de positionnement.

Cette thèse est une contribution à l'étude des arrangements. L'idée est le calcul de la combinatoire d'un arrangement de courbes ou surfaces compte tenu du fait que les données et les opérations ne seront connues qu'à une précision près. Dans cette démarche, il se pose un problème qui est de savoir si la combinatoire d'un arrangement est stable lorsque les éléments constitutifs sont perturbés. Un préliminaire indispensable est alors d'établir une définition rigoureuse adaptée à nos besoin concernant l'équivalence des arrangements. Le travail consiste essentiellement en un développement des notions mathématiques nécessaires pour étudier l'équivalence, la construction, les perturbations d'arrangements. Quelques résultats en terme d'analyse de complexité sont également énoncés. Des résultats sont obtenus sur les perturbations d'arrangements d'hyperplans en dimension quelconque. Dans le plan est étudiée une méthode particulière de calcul des arrangements des courbes, avec un exemple détaillé sur les cercles. Utilisant des transformations classiques de dualité, des applications des propriétés d'équivalence des arrangements d'hyperplans aux configurations de points et aux diagrammes de Voronoï sont aussi données

Les intégrines sont des protéines membranaires hétérodimériques impliquées dans l'adhésion et la migration cellulaire. Elles sont notamment surexprimées lors de la néoangiogenèse tumorale. Une dizaine d'entre elles reconnaît un motif peptidique RGD (Arg-Gly-Asp) structuré. Des analogues de cette séquence peuvent être utilisés pour la détection précoce de tumeurs et de métastases. Nous avons entrepris de développer de nouveaux traceurs, marqués au 99mTc, spécifiques de l'intégrine alphaVbeta3, et d'identifier les traceurs efficaces par un criblage in vivo qui permet de prendre en compte au plus tôt les aspects de biodistribution et de pharmacocinétique. Ne disposant d'aucun modèle prédictif fiable de la structure des complexes d'oxotechnétium au début de ce projet, nous avons préféré une approche combinatoire pour développer une série de ligands potentiels de l'intégrine alphaVbeta3. <br />Les traceurs ont été obtenus selon deux stratégies : 1) cyclisation d'analogues linéaires de RGD par un motif NS2/S coordinant un cœur oxotechnétium ; 2) assemblage combinatoire de motifs indépendants par coordination du cœur oxotechnétium par le motif NS2+S. La stabilité des traceurs technétiés et de leurs analogues rhéniés a été testée en présence de glutathion et dans le plasma. Une première évaluation in vitro sur intégrine purifiée a montré que l'un des peptides RGD, cyclisé par le rhénium, se lie spécifiquement à alphaVbeta3. Un modèle tumoral (tumeur U87-MG, implantée sur des souris nude) a été validé au laboratoire et une méthode d'analyse du criblage in vivo a été mise au point à l'aide de composés modèles marqués au 99mTc. Il s'avère que les données de biodistribution et le pourcentage d'activité retrouvé dans la tumeur sont encourageants pour les complexes cycliques, bien que l'identification des traceurs efficaces soit rendue difficile par leur instabilité dans les conditions d'analyse.

Daniel Kan associe a tout ensemble simplicial réduit x un fibre principal contractile de base x et de fibre un groupe simplicial libre, note gx. Un concept généralisé de prisme nous permet de considérer ce groupe comme sous-quotient canonique d'un modèle simplicial de l'espace de lacets de x, et de munir l'espace total du fibre d'une contraction combinatoire évoquant l'idée topologique de contraction des chemins. Est ainsi établie une correspondance biunivoque explicite entre les représentants algébriques des classes d'homotopie de Gx et certains représentants géométriques des classes d'homotopie de x. En utilisant les propriétés homotopiques du commutant de Gx nous obtenons enfin une version effective du théorème de Hurewicz comportant entre autres la construction algorithmique de sphères combinatoires a partir de certains cycles homologique

Étant donnes un graphe g=(v,e) et une fonction cout définie sur les arêtes de ce graphe, cette thèse étudie le problème du voyageur de commerce relaxe qui consiste a trouver une tournée sur G, de longueur minimum, telle que chaque sommet soit visite au moins au fois

.

L'objet de ce mémoire est l'étude et la construction d'un modèle de surfaces fondé sur la représentation par un atlas de cartes : <br />L'intérêt d'un tel modèle est qu'il permet de travailler localement sur la sur face sans perte de la cohérence globale, et d'autre part d'hériter des notions de géométrie différentielle attachées à cette représentation pour définir une surface régulière, et donc résoudre intrinsèquement les problèmes de continuité ordinairement rencontrés par les représentations paramétriques par morceaux. Nous avons présenté ce modèle dans le cadre des modèles de surfaces d'usage courant en informatique graphique, puis dans le cadre plus théorique de la géométrie différentielle. <br /> Nous avons ensuite proposé la construction d'un tel modèle à partir d'un nuage de points 3D interpolés au préalable par une surface triangulée qui est une variété de dimension 2, connexe et compacte. Cette construction se déroule en trois étapes. Chaque étape rencontre un problème géométrique auquel nous proposons une solution innovante. En particulier, nous avons démontré que le nerf d'un recouvrement bien formé est une triangulation combinatoire. Nous avons également étudié la para métrisation d'une couronne du plan par un C1-difféomorphisme, ainsi que le raccord continu de surfaces par combinaison convexe.