Cette thèse considère le problème de sélection et d'ordonnancement des prises de vue d'un satellite agile d'observation de la Terre. La mission d'un satellite d'observation est d'obtenir des photographies de la surface de la Terre afin de satisfaire des requêtes d'utilisateurs. Les demandes, émanant de différents utilisateurs, doivent faire l'objet d'un traitement avant transmission d'un ordre vers le satellite, correspondant à une séquence d'acquisitions sélectionnées. Cette séquence doit optimiser deux objectifs sous contraintes d'exploitation. Le premier objectif est de maximiser le profit global des acquisitions sélectionnées. Le second est d'assurer l'équité du partage des ressources en minimisant la différence maximale de profit entre les utilisateurs. Deux métaheuristiques, composées d'un algorithme génétique à clé aléatoire biaisées (biased random key genetic algorithm - BRKGA) et d'une recherche locale multi-objectif basée sur des indicateurs (indicator based multi-objective local search - IBMOLS), sont proposées pour résoudre le problème. Pour BRKGA, trois méthodes de sélection, empruntées à NSGA-II, SMS-EMOA, et IBEA, sont proposées pour choisir un ensemble de chromosomes préférés comme ensemble élite. Trois stratégies de décodage, parmi lesquelles deux sont des décodages uniques et la dernière un décodage hybride, sont appliquées pour décoder les chromosomes afin d'obtenir des solutions. Pour IBMOLS, plusieurs méthodes pour générer la population initiale sont testées et une structure de voisinage est également proposée. Des expériences sont menées sur des cas réalistes, issus d'instances modifiées du challenge ROADEF 2003. On obtient ainsi les fronts de Pareto approximés de BRKGA et IBMOLS dont on calcule les hypervolumes. Les résultats de ces deux algorithmes sont comparés.

Le travail de cette thèse est à l'interface des dom aines de la recherche opérationnelle et de la micro -électronique. Il traite de l'utilisation des techniques d'optimisation combinatoire pour la DFT (Design For Test) des Circuits Intégrés (CI). Avec la croissance rapide et la complexité des CI actuels, la qualité ainsi que le coût du test sont devenus des paramètres importants dans l'industrie des semi-con ducteurs. Afin de s'assurer du bon fonctionnement du CI, l'étape de test est plus que jamais une étape essentielle et délicate dans le processus de fabrication d'un CI. Pour répondre aux exigences du marché, le test doit être rapide et efficace dans la révélation d'éventuels défauts. Pour cela, il devient incontournable d'appréhender la phase de test dès les étapes de conception du CI. Dans ce contexte, la conception testable plus connue sous l'appellation DFT vise à améliorer la testabilité des CI. Plusieurs problèmes d'optimisation et d'aide à la décision découlent de la micro-électronique. La plupart de ces travaux traitent des problèmes d'optimisation combinatoire pour le placement et routage des circuits. Nos travaux de recherche sont à un niveau de conception plus amont, la DFT en présynthèse au niveau transfert de registres ou RTL (Register Transfer Level). Cette thèse se découpe en trois parties. Dans la première partie nous introduisons les notions de bases de recherche opérationnelle, de conception et de test des CI. La démarche suivie ainsi que les outils de résolution utilisés dans le reste du document sont présentés dans cette partie. Dans la deuxième partie, nous nous intéressons au problème de l'optimisation de l'insertion des chaîne s de scan. A l'heure actuelle, le "scan interne" est une des techniques d'amélioration de testabilité ou de DFT les plus largement adoptées pour les circuits intégrés numériques. Il s'agit de chaîner les éléments mémoires ou bascules du circuit de sorte à former des chaînes de scan qui seront considérées pendant la phase de test comme points de contrôle et d'observation de la logique interne du circuit. L'objectif de notre travail est de développer des algorithmes permettant de générer pour un CI donné et dès le niveau RTL des chaînes de scan optimales en termes de surface, de temps de test et de consommation en puissance, tout en respectant des critères de performance purement fonctionnels. Ce problème a été modélisé comme la recherche de plus courtes chaînes dans un graphe pondéré. Les méthodes de résolution utilisées sont basées sur la recherche de chaînes hamiltoniennes de longueur minimale. Ces travaux ont été réalisés en collaboration avec la start-up DeFacTo Technologies. La troisième partie s'intéresse au problème de partage de blocs BIST (Built In Self Test) pour le test des mémoires. Le problème peut être formulé de la façon suivante : étant données des mémoires de différents types et tailles, ainsi que des règles de partage des colliers en série et en parallèle, il s'agit d'identifier des solutions au problème en associant à chaque mémoire un collier. La solution obtenue doit minimiser à la fois la surface, la consommation en puissance et le temps de test du CI. Pour résoudre ce problème, nous avons conçu un prototype nommé Memory BIST Optimizer (MBO). Il est constitué de deux phases de résolution et d'une phase de validation. La première phase consiste à créer des groupes de compatibilité de mémoires en tenant compte des règles de partage et d'abstraction des technologies utilisées. La deuxième phase utilise les algorithmes génétiques pour l'optimisation multi-objectifs afin d'obtenir un ensemble de solutions non dominées. Enfin, la validation permet de vérifier que la solution fourn ie est valide. De plus, elle affiche l'ensemble des solutions à travers une interface graphique ou textuelle. Cela permet à l'utilisateur de choisir la solution qui lui correspond le mieux. Actuellement, l'outil MBO est intégré dans un flot d'outils a ST-microelectronics pour une utilisation par ses clients.

Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leur déploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers.

Ce document décrit de nouvelles modélisations et approches de résolution que nous appliquons à des problèmes de découpe et de conditionnement. Nous étudions dans un premier temps plusieurs techniques de décomposition alliées à différentes méta-heuristiques basées sur des stratégies d'oscillation. Nous étudions ensuite le concept de fonctions dual-réalisables qui permettent d'obtenir des évaluations par défaut polynomiales pour des problèmes de conditionnement. Finalement, nous proposons des modèles originaux pour des problèmes de placement de rectangles. Nous utilisons ces modèles dans des méthodes de programmation par contraintes.

La distribution de marchandises est un secteur en constant développement et constitue un facteur économique important. Par contre, dans les villes, il contribue notamment aux problèmes de congestion, pollution, bruit et d'autres dérangements à la population des villes. Pour faire face à ces problèmes, une nouvelle discipline est née à la fin du XXe siècle, la " City Logistics ", qui a comme objectifs principaux la réduction de la congestion, la pollution et le bruit occasionné par le transport de marchandises en ville. Dans les dernières années, plusieurs études et expériences se sont développées en toute l'Europe, mais pour l'instant une politique commune en matière de logistique urbaine n'a pas encore été proposée par l'Union Européenne. En Italie, seulement certaines villes de petite taille ont expérimenté des politiques de " city logistics " avec succès, mais sans un lien entre elles. Nous observons que ces expériences utilisent des centres urbains de distribution de marchandises, ce qui peut se traduire en un système de transport à deux ou plus niveaux. Plusieurs études en recherche opérationnelle ont traité des problématiques liées à des systèmes à niveaux multiples pour la distribution de marchandise. Néanmoins, l'optimisation des coûts de transport est en générale réalisé en considérant chaque niveau indépendant des autres, ou en approximant les coûts du transport dans certains niveaux pour simplifier. Un autre problème est le manque d'une unification de la terminologie utilisée dans ces études, qui difficulte la recherche bibliographique. Le but de cette recherche est, d'un coté, proposer des lignes guide d'accion en matière de planification de la distribution urbaine de marchandises, en unifiant certains termes, et d'un autre coté présenter une famille de problèmes d'optimisation de routes des véhicules qui considère les systèmes à niveaux multiples dans son ensemble et pas comme une somme de systèmes indépendants. Dans un premier temps, nous présentons les principales expériences de " city logistics " en Italie, ainsi que des lignes d'action dans la planification des systèmes de distribution urbaine des marchandises qui puissent devenir opérationnels et efficients. Ensuite nous présentons les principales problématiques et limites de l'optimisation de systèmes de transports à niveaux multiples, en unifiant les concepts et la notation. Nous proposons une nouvelle famille de problèmes d'optimisation de routes de véhicules pour des systèmes à niveaux multiples, en détaillant le cas basique : le problème de routes de véhicules à deux niveaux. Nous proposons des modèles mathématiques pour ce problème et des résultats numériques pour illustrer les avantages et les limites de la modélisation de ces systèmes.

La théorie de la complexité distingue les problèmes que l'on sait résoudre en un temps polynomial en la taille des données (que l'on peut qualifier de raisonnable), des problèmes NP-complets, qui nécessitent (en l'état actuel des connaissances) un temps de résolution exponentiel en la taille des données (que l'on peut qualifier de déraisonnable). C'est pour cette raison que la communauté scientifique s'est tournée vers les algorithmes (polynomiaux) d'approximation dont la mesure de qualité se fait le plus souvent grâce au rapport d'approximation en pire cas (pour un problème de minimisation de taille, un algorithme a un rapport d'approximation de k si la taille de toute solution pouvant être retournée par l'algorithme est inférieure ou égale à k fois la taille de la solution optimale). Dans la littérature, on en vient à considérer qu'un algorithme est plus performant qu'un autre lorsqu'il possède un plus petit rapport d'approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d'un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution). Mes travaux de thèse ont pour objet de mieux "capturer" le comportement des algorithmes d'approximation en allant plus loin que le simple rapport d'approximation en pire cas, et ce sur deux problèmes distincts : I. Le problème du Vertex Cover En montrant que les performances moyennes d'un algorithme peuvent être décorélées des performances en pire cas. Par exemple, nous avons montré que dans la classe des graphes spécialement conçus pour le piéger en pire cas, l'algorithme glouton "Maximum Degree Greedy" retourne, en moyenne, des solutions dont la taille tend vers l'optimum lorsque n tend vers l'infini. En évaluant les performances moyennes d'un algorithme. Nous avons prouvé que l'algorithme online présenté par Demange et Paschos en 2005 (dont le rapport d'approximation en pire cas est égal au degré maximum du graphe) est au plus 2-approché en moyenne dans n'importe quel graphe. Ce résultat, combiné à d'autres, montre que cet algorithme est "en pratique" meilleur que la plupart des algorithmes 2-approchés connus, malgré un mauvais rapport d'approximation en pire cas . En comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons proposé un algorithme de liste et nous avons prouvé analytiquement qu'il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande). Nous avons également comparé analytiquement (en utilisant des outils comme les séries génératrices) les performances moyennes de six algorithmes sur les chemins. Nous les avons ensuite expérimentées sur un grand nombre de graphes de diverses familles bien choisies. On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d'approximation (fonction du degré max. du graphe). Tous ces résultats montrent que le rapport d'approximation en pire cas n'est pas toujours suffisant pour caractériser l'intégralité de la qualité d'un algorithme et que d'autres analyses (en moyenne notamment) doivent être effectuées pour en faire le tour. II. Le problème de la connexion de groupes dynamiques dans les réseaux Nous avons analysé un processus de mise-à-jour d'un arbre connectant dans un réseau un groupe que les membres peuvent rejoindre ou quitter à tout moment. Notre processus possède de bonnes propriétés : il est simple à implémenter et il garantit, après chaque opération d'ajout ou de retrait, que le diamètre de l'arbre est au plus 2 fois l'optimal. Cependant, pour obtenir cette garantie, nous devons autoriser la reconstruction totale de l'arbre lorsque le membre identifié comme sa racine quitte le groupe. Ces étapes de reconstruction sont très coûteuses et nous cherchons donc à en évaluer le nombre. Des travaux précédents montraient que dans le pire cas, il faut reconstruire (quasiment) à chaque étape pour conserver la garantie sur le diamètre. Nous montrons dans cette thèse (en utilisant les marches aléatoires, etc.) que, en fonction de certains paramètres du problèmes (comme les probabilités associées aux opérations d'ajout et de retrait), l'espérance du nombre de reconstructions est soit logarithmique en le nombre d'évènements (ajout ou retrait), soit constant. Ce résultat montre que le comportement moyen est très bon (malgré un pire cas très défavorable) et que notre processus de mise-à-jour peut être une solution viable en pratique.

Ce travail s'intéresse à la planification tactique de chaînes logistiques dans un environnement incertain et perturbé. Dans le cadre de relations "point-à point", nous proposons une approche permettant d'élaborer une planification tactique optimale et réactive d'un maillon d'une chaîne logistique en présence de paramètres incertains et de perturbations. Notre approche se fonde sur une structure à deux niveaux décisionnels. Le premier niveau effectue une planification agrégée en minimisant le coût global de production. Il établit ensuite "un plan de guidage" qui est transmis au niveau détaillé. Ce dernier effectue sa planification en suivant "au mieux" le plan de guidage et en prenant en compte les contraintes et données détaillées ignorées au niveau supérieur. Le niveau détaillé adopte un processus dynamique de planification à horizon glissant. Il réactualise ses données à chaque étape de planification afin d'assurer la réactivité du processus décisionnel. Nous caractérisons explicitement l'inertie du système décisionnel en distinguant deux phases : la phase d'anticipation et la phase de réalisation. Chaque phase est caractérisée par un délai temporel. Ainsi, nous proposons une modélisation originale du processus décisionnel de chaque décision via trois variables. Le niveau détaillé est formulé selon un programme linéaire. Au niveau agrégé, nous proposons un modèle global ayant l'originalité de prendre en compte les spécificités du processus décisionnel détaillé. Le couplage entre les deux niveaux est assuré par le plan de guidage. Selon les informations incluses dans le plan de guidage, le niveau agrégé accorde un certain degré d'autonomie au niveau détaillé, ceci conditionne la réactivité et la robustesse de la planification. Dans notre travail, nous considérons trois types de guidage : deux guidages budgétaires "globaux" et un guidage "prescriptif" par la sous-traitance agrégée. Notre approche est évaluée par simulation dans le cadre d'une demande incertaine. Pour cela, nous développons deux outils de simulation et un ensemble d'indicateurs de performances. Les expérimentations réalisées confirment la performance de notre approche par rapport à des approches classiques et mettent en évidence l'influence du type de guidage et du profil de la demande détaillée sur la réactivité et la robustesse des solutions trouvées.

Les problèmes d'optimisation en variables mixtes sont souvent résolus par décomposition quand ils sont de grande taille, avec quelques inconvénients : difficultés de garantir la qualité voire l'admissibilité des solutions et complexité technique des projets de développement. Dans cette thèse, nous proposons une approche directe, en utilisant la recherche locale, pour résoudre des problèmes d'optimisation mixte. Notre méthodologie se concentre sur deux points : un vaste ensemble de mouvements et une évaluation incrémentale basée sur des algorithmes approximatifs, travaillant simultanément sur les dimensions combinatoire et continue. Tout d'abord, nous présentons un problème d'optimisation des stocks de banches sur chantiers. Ensuite, nous appliquons cette technique pour optimiser l'ordonnancement des mouvements de terre pour le terrassement d'autoroutes et de voies ferrées. En n, nous discutons d'un problème de routage de véhicules avec gestion des stocks. Les coûts logistiques sont optimisés pour livrer un produit fluide par camion dans des zones géographiques d'une centaine de clients, avec la gestion de l'inventaire con ée au fournisseur.

Le thème de ce mémoire est l'ordonnancement dans les ateliers de production. L'objectif est d'étudier différents modèles classiques en analysant les liens et différences entre ces modèles et les problèmes pratiques associés. Les méthodes utilisées sont l'analyse de problèmes de nos partenaires industriels, l'étude de la complexité des problèmes ou de la structure des solutions et la proposition de méthodes de résolution exactes ou approchées. Le premier axe de cette thèse est l'étude de problèmes d'ordonnancement avec contraintes de ressources d'entrée/sortie. Les environnements considérés sont les flowshops robotisés et le nouveau modèle d'indisponibilité des opérateurs. Le second axe abordé concerne l'ordonnancement avec high multiplicity où les pièces sont agrégées en catégories. La description complète d'un ordonnancement (c'est-à-dire les instants de fabrication des tâches) n'est que pseudo-polynomiale de la taille de l'instance.

Pour garantir la pérennité de l'entreprise, celle-ci doit souvent chercher des contrats à l'export. Dans le domaine de la Défense, ces contrats s'accompagnent souvent de transferts de technologie (ToT) vers le pays acquéreur. Ceux-ci sont partiels et un compromis est nécessaire entre la protection de la propriété industrielle, celle du secret national et les demandes du client. C'est dans ce contexte, et notamment au sein de DCNS que nous cherchons de nouvelles techniques de protection logicielles. Face aux échecs des différentes techniques de protections actuelles (obfuscations et packer) qui ne proposent que de ralentir la compréhension des données, une nouvelle approche de protection est envisagée. L'idée principale est de filtrer les accès mémoires des données identifiées comme sensibles. Cette solution, qui s'inscrit dans un environnement industriel défini (architecture Intel et système d'exploitation Linux), doit impacter au minimum le système et les applications fournis par DCNS. Nous proposons une architecture qui s'appuie sur les dernières technologies Intel et particulièrement sur la virtualisation matérielle. Celle-ci nous permet d'obtenir un haut niveau de privilège et de contrôler finement les applications. Notre solution permet de protéger les données exécutables des binaires de type ELF, dans les architectures 32 et 64 bits, sans modification du système cible. Nous détaillons les différentes étapes pour protéger l'exécution d'un processus (du chargement à son arrêt) ainsi que les problèmes rencontrés et les choix pour y remédier. Nous montrons également, à travers différentes mesures, l'efficacité d'une telle architecture et son faible impact sur les performances globales. Dans notre implémentation, seules les données exécutables sont protégées, nous proposons donc des pistes d'améliorations pour couvrir la totalité du binaire en mémoire. Et nous étudions les évolutions possibles pour intégrer notre protection dans une architecture de confiance et ainsi, renforcer sa persistance face aux attaques. Notre solution permet donc par construction d'interdire toutes les lectures et écritures des données exécutables sensibles et s'adapte à tous les systèmes d'exploitation Linux sans aucune modification du système.