Le transport de matières dangereuses est connu pour son haut risque potentiel pour le réseau routier. Un accident peut avoir de graves conséquences pour la santé publique et l’environnement sur une longue période. L’optimisation du transport de matières dangereuses est une problématique importante. Cette thèse propose, pour la première fois dans la littérature, une stratégie de réservation de voies pour le transport de matières dangereuses. L’objectif est de proposer des itinéraires pour le transport de matières dangereuses qui minimisent à la fois le risque potentiel et l’impact négatif sur le trafic dans un réseau de transport dû à la réservation de voies. Dans cette thèse, nous nous focalisons sur deux nouveaux problèmes : l’optimisation de transport de matières dangereuses grâce à la stratégie de réservation de voies dans un réseau de transport selon si le risque dépend de l’instant de passage (appelé LRPTDR) ou pas (appelé LRPTIR). Pour chaque problème étudié, nous proposons un nouveau modèle d’optimisation multi-critères. Pour le LRPTIR, nous développons d’abord une méthode combinant la méthode de ε-contrainte et la logique floue pour obtenir des solutions Pareto-optimales et une solution préférée en fonction des critères du gestionnaire. Ensuite,une méthode qui combine le « cut-and-solve » and le « cutting plane» est proposée pour réduire le temps de calcul. Pour le LRPTDR, une méthode de « cut-and-solve » est appliquée, dans laquelle une nouvelle technique de « piecing cut » et une stratégie de relaxation partielle sont développées pour améliorer la performance. Les performances des algorithmes proposés sont évaluées à l’aide d’instances générées aléatoirement. Les résultats numériques montrent que les algorithmes proposés sont plus performants que le logiciel commercial CPLEX pour les problèmes étudiés. / Hazardous material transportation is well-known for its high potential risk. An accident may cause very serious economic damage and negative impacts on the public health and the environment over the long term. Optimization for hazardous material transportation is an important issue. For the first time in the literature, this thesis introduces the lane reservation strategy into the hazardous material transportation problem. The goal is to obtain a best compromise between the impact on normal traffic due to lane reservation and the transportation risk.In this thesis, we focus on two novel problems: hazardous material transportation problem via lane reservation in networks with time-invariant and time-dependent risk, called LRPTIR and LRPTDR, respectively. For these problems, multi-objective integer programming and multi-objective mixed integer programming models are formulated, respectively. For the LRPTIR, we first develop an ε-constraint and fuzzy-logic based method to obtain Pareto optimal solutions and a preferred solution. Then a cut-and-solve and cutting plane combined method is proposed to reduce the computational time. For the LRPTDR, an improved cut-and-solve based ε-constraint method is proposed, in which a new technique of generating piercing cuts is developed and a partial integral relaxation strategy is applied. The performance of the proposed algorithms is evaluated by randomly generated instances. Computational results demonstrate that for the considered problems, the cut-and-solve method outperforms software package CPLEX.

Les problèmes d'optimisation à grande échelle sont généralement difficiles à résoudre de façon optimale.Des algorithmes d'approximation tels que les métaheuristiques, capables de trouver rapidement des solutions sous-optimales, sont souvent préférés. Cette thèse porte sur les algorithmes de recherche locale multi-objectif (MOLS), des métaheuristiques capables de traiter l'optimisation simultanée de plusieurs critères. Comme de nombreux algorithmes, les MOLS exposent de nombreux paramètres qui ont un impact important sur leurs performances. Ces paramètres peuvent être soit prédits et définis avant l'exécution de l'algorithme, soit ensuite modifiés dynamiquement. Alors que de nombreux progrès ont récemment été réalisés pour la conception automatique d'algorithmes, la grande majorité d'entre eux ne traitent que d'algorithmes mono-objectif et l'optimisation d'un unique indicateur de performance. Dans cette thèse, nous étudions les relations entre la conception automatique d'algorithmes et l'optimisation multi-objective. Nous passons d'abord en revue les stratégies MOLS possibles et présentons un framework MOLS général et hautement configurable. Nous proposons également MO-ParamILS, un configurateur automatique spécialement conçu pour gérer plusieurs indicateurs de performance. Nous menons ensuite plusieurs études sur la conception automatique de MOLS sur de multiples problèmes combinatoires bi-objectifs. Enfin, nous discutons deux extensions de la configuration d'algorithme classique : d'abord l'intégration des mécanismes de contrôle de paramètres, pour bénéficier de multiples prédictions de configuration; puis l'utilisation séquentielle de plusieurs configurations. / Large-scale optimisation problems are usually hard to solve optimally.Approximation algorithms such as metaheuristics, able to quickly find sub-optimal solutions, are often preferred.This thesis focuses on multi-objective local search (MOLS) algorithms, metaheuristics able to deal with the simultaneous optimisation of multiple criteria. As many algorithms, metaheuristics expose many parameters that significantly impact their performance. These parameters can be either predicted and set before the execution of the algorithm, or dynamically modified during the execution itself. While in the last decade many advances have been made on the automatic design of algorithms, the great majority of them only deal with single-objective algorithms and the optimisation of a single performance indicator such as the algorithm running time or the final solution quality. In this thesis, we investigate the relations between automatic algorithm design and multi-objective optimisation, with an application on MOLS algorithms. We first review possible MOLS strategies ans parameters and present a general, highly configurable, MOLS framework. We also propose MO-ParamILS, an automatic configurator specifically designed to deal with multiple performance indicators. Then, we conduct several studies on the automatic offline design of MOLS algorithms on multiple combinatorial bi-objective problems. Finally, we discuss two online extensions of classical algorithm configuration: first the integration of parameter control mechanisms, to benefit from having multiple configuration predictions; then the use of configuration schedules, to sequentially use multiple configurations.

Les grilles de calcul et le “cloud computing” permettent de distribuer un ensemble de ressources informatiques, telles que du stockage ou du temps de calcul, à un ensemble d’utilisateurs en fonction de leurs demandes en donnant l’illusion de ressources infinies. Cependant, lorsque l’ensemble de ces ressources est insuffisant pour satisfaire les exigences des utilisateurs, des conflits d’intérêts surgissent. Ainsi, un libre accès à des ressources limitées peut entraîner une utilisation inefficace qui pénalise l’ensemble des participants. Dans de tels environnements, il devient nécessaire d’établir des procédures d’arbitrage afin de résoudre ces conflits en garantissant une distribution équitable aux différents utilisateurs. Nous présentons une nouvelle classe de problèmes : celle des ordonnancements multi-utilisateurs. Cette thèse aborde la notion d’équité au travers de problèmes d’allocation de ressources sous incertitudes et d’ordonnancement de tâches périodiques. / Grid and Cloud computing make possible the sharing of computer system resources, such as storage or computation time, among a set of users, according to their requests, thereby creating an illusion of infinite resources. However, as soon as those resources are insufficient to meet users’s expectations, conflicts of interest arise. Therefore, unlimited access to limited resources may lead to inefficient usage which penalizes the whole set of users. In such environments, arbitration becomes necessary in order to settle those conflicts and ensure a fair allocation to all users. We present two classes of problems : multi-user resource allocation under uncertainty and multi-user periodic task scheduling. We tackle these problems from the point of view of fairness.

Les grilles de calcul et le "cloud computing" permettent de distribuer un ensemble de ressources informatiques, telles que du stockage ou du temps de calcul, à un ensemble d'utilisateurs en fonction de leurs demandes en donnant l'illusion de ressources infinies. Cependant, lorsque l'ensemble de ces ressources est insuffisant pour satisfaire les exigences des utilisateurs, des conflits d'intérêts surgissent. Ainsi, un libre accès à des ressources limitées peut entraîner une utilisation inefficace qui pénalise l'ensemble des participants. Dans de tels environnements, il devient nécessaire d'établir des procédures d'arbitrage afin de résoudre ces conflits en garantissant une distribution équitable aux différents utilisateurs. Nous présentons une nouvelle classe de problèmes : celle des ordonnancements multi-utilisateurs. Cette thèse aborde la notion d'équité au travers de problèmes d'allocation de ressources sous incertitudes et d'ordonnancement de tâches périodiques.

Les technologies numériques ont engendré depuis peu, des volumes de données importants, qui peuvent receler des informations utiles. Ceci a donné naissance à l'extraction de connaissances à partir des données qui désigne le processus d'extraction d'informations implicites, précédemment inconnues et potentiellement utiles enfouies dans les données. La fouille de données comprend cinq phases dont la principale est l'extraction de modèles. Nous nous intéressons aux connaisances exprimées sous la forme de règles de dépendance et à la qualité de ces règles. Une règle de dépendance est une implication conditionnelle entre ensembles d'attributs. Les algorithmes standard ont pour but de rechercher les meilleurs modèles. Derrière ces processus se cache en fait une véritable problématique d'optimisation. Nous considérons la recherche des règles de dépendance les plus intéressantes comme étant un problème d'optimisation dans lequel la qualité d'une règle est quantifiée par des mesures. Ainsi, il convient d'étudier les espaces de recherche induits par les mesures ainsi que les algorithmes de recherche dans ces espaces. Il ressort que la plupart des mesures observées présentent des propriétés différentes suivant le jeu de données. Une approche analytique n'est donc pas envisageable dans fixer certains paramères. Nous observons les variations relatives de mesures évaluées simultanément ; certaines d'entre elles sont antagonistes ce qui ne permet pas d'obtenir "la" meilleure règle ; il faut alors considérer un ensemble de compromis satisfaisants. Nous apportons des solutions par le biais des algorithmes génétiques.

Dans cette thèse, nous apportons la contribution à la conception de robots médicaux, en proposant une démarche de conception simultanée de la structure mécanique du robot. Par opposition à une vision séquentielle naturelle de la conception, la formalisation du processus créatif permet une simultanéité, ouvrant la voie à des structures innovantes dédiées : en robotique médicale, faible masse et faible compacité de la structure mécanique sont souvent recherchées. A partir d'un descriptif de démarches existantes, nous effectuons la conception d'un robot de télé-échographie et d'un robot de chirurgie mini-invasive. Pour les deux applications, de fortes contraintes sont présentes. En télé-échographie, la portabilité est très recherchée, requérant une faible compacité. Pour la chirurgie mini-invasive, les moto-réducteurs du robot in vivo doivent être dimensionnés au plus juste. Ici, nous avons formalisé l'amélioration de la compacité d'une structure parallèle pour la télé-échographie. Les résultats montrent une amélioration de la compacité de l'ordre de 5%. Dans le même esprit, nous avons formalisé la synthèse dimensionnelle de deux robots 2R-R-R de chirurgie mini-invasive in vivo. Nous réalisons l'optimisation simultanée entre le dimensionnement des moto-réducteurs et des longueurs des corps pour tendre vers une simultanéité totale du processus créatif, ce qui nous permet d'améliorer les performances en termes de force et vitesse à l'effecteur. Ces expériences de conception montrent les limites à une simultanéité stricte. Nous indiquons le besoin d'adapter outils et méthodes de conception mécatronique pour une simultanéité en conception robotique tenant compte de l'aspect imparfait du processus créatif.

En chirurgie mini-invasive guidée par l’image, une planification préopératoire précise des trajectoires des outils chirurgicaux est un facteur clé pour une intervention réussie. Cependant, une planification efficace est une tâche difficile, qui peut être considérablement améliorée en considérant différents facteurs contributifs tels que les déformations biomécaniques intra-opératoires, ou en introduisant de nouvelles techniques d'optimisation. Dans ce travail, nous nous concentrons sur deux aspects. Le premier aspect porte sur l'intégration de la déformation intra-opératoire dans le processus de planification de trajectoire. Nos méthodes combinent des techniques d'optimisation géométrique à base de simulations biomécaniques. Elles sont caractérisées par un certain niveau de généralité, et ont été expérimentées sur deux types d’interventions chirurgicales: les procédures percutanées pour l'ablation de tumeurs hépatiques, et la stimulation cérébrale profonde en neurochirurgie. Deuxièmement, nous étudions, mettons en œuvre, et comparons plusieurs approches d'optimisation en utilisant des méthodes qualitatives et quantitatives, et nous présentons une méthode efficace d'optimisation évolutionnaire multicritères à base de Pareto qui permet de trouver des solutions optimales qui ne sont pas accessibles par les méthodes existantes. / In image-guided minimally invasive surgery, a precise preoperative planning of the surgical tools trajectory is a key factor to a successful intervention. However, an efficient planning is a challenging task, which can be significantly improved when considering different contributing factors such as biomechanical intra-operative deformations, or novel optimization techniques. In this work, we focus on two aspects. The first aspect addresses integrating intra-operative deformation to the path planning process. Our methods combine geometric-based optimization techniques with physics-based simulations. They are characterized with a certain level of generality, and are experimented on two different surgical procedures: percutaneous procedures for hepatic tumor ablation, and in neurosurgery for Deep Brain Stimulation (DBS). Secondly, we investigate, implement, and compare many optimization approaches using qualitative and quantitative methods, and present an efficient evolutionary Pareto-based multi-criteria optimization method which can find optimal solutions that are not reachable via the current state of the art methods.

Les grilles de calcul et le "cloud computing" permettent de distribuer un ensemble de ressources informatiques, telles que du stockage ou du temps de calcul, à un ensemble d'utilisateurs en fonction de leurs demandes en donnant l'illusion de ressources infinies. Cependant, lorsque l'ensemble de ces ressources est insuffisant pour satisfaire les exigences des utilisateurs, des conflits d'intérêts surgissent. Ainsi, un libre accès à des ressources limitées peut entraîner une utilisation inefficace qui pénalise l'ensemble des participants. Dans de tels environnements, il devient nécessaire d'établir des procédures d'arbitrage afin de résoudre ces conflits en garantissant une distribution équitable aux différents utilisateurs. Nous présentons une nouvelle classe de problèmes : celle des ordonnancements multi-utilisateurs. Cette thèse aborde la notion d'équité au travers de problèmes d'allocation de ressources sous incertitudes et d'ordonnancement de tâches périodiques.

Dans cette thèse, nous apportons la contribution à la conception de robots médicaux, en proposant une démarche de conception simultanée de la structure mécanique du robot. Par opposition à une vision séquentielle naturelle de la conception, la formalisation du processus créatif permet une simultanéité, ouvrant la voie à des structures innovantes dédiées : en robotique médicale, faible masse et faible compacité de la structure mécanique sont souvent recherchées. A partir d’un descriptif de démarches existantes, nous effectuons la conception d’un robot de télé-échographie et d’un robot de chirurgie mini-invasive. Pour les deux applications, de fortes contraintes sont présentes. En télé-échographie, la portabilité est très recherchée, requérant une faible compacité. Pour la chirurgie mini-invasive, les moto-réducteurs du robot in vivo doivent être dimensionnés au plus juste. Ici, nous avons formalisé l’amélioration de la compacité d’une structure parallèle pour la télé-échographie. Les résultats montrent une amélioration de la compacité de l’ordre de 5%. Dans le même esprit, nous avons formalisé la synthèse dimensionnelle de deux robots 2R-R-R de chirurgie mini-invasive in vivo. Nous réalisons l’optimisation simultanée entre le dimensionnement des moto-réducteurs et des longueurs des corps pour tendre vers une simultanéité totale du processus créatif, ce qui nous permet d’améliorer les performances en termes de force et vitesse à l’effecteur. Ces expériences de conception montrent les limites à une simultanéité stricte. Nous indiquons le besoin d’adapter outils et méthodes de conception mécatronique pour une simultanéité en conception robotique tenant compte de l’aspect imparfait du processus créatif. / In this thesis, we propose a contribution to the design of medical robots, by offering a concurrent design or simultaneous approach. As opposed to a natural sequential view of the design process, the formalization of the creative process allows simultaneity, paving the way for innovative structures, dedicated: in the medical robotic field, low mass and low compactness of the mechanical structure are often sought. From a description of existing approaches, we design a tele-ultrasound robot and a minimally invasive surgery robot. For both applications, high physical integration is required. For tele-ultrasound robots, portability is highly sought, requiring low compactness. For minimally invasive surgery, geared motors of the in vivo robot must be sized correctly. Here, we formalized the improvement of compactness of an existing parallel structure for remote ultrasound application. The results show an improvement of compactness of around 5%. In the same way, we formalize the dimensional synthesis of two robots 2R-R-R for in vivo minimally invasive surgery. The results show the under-sizing of some actuators. We perform simultaneous optimization between the design of geared motors and lengths of the body of a robot 2R-RR, tendering towards full simultaneity of the creative process, allowing to improve minimal force and velocity at the end-effector of the robot. These experiments of design show limits to a strict simultaneity. We indicate the need to adapt the tools and methods of mechatronic design for simultaneous robotics design, taking into account the imperfect aspect of the creative process.

Les travaux présentés dans cette thèse portent sur le placement et l’ordonnancement d’applications de flots de données. On se place dans le contexte de plates-formes composées de processeurs sujets à des pannes. Dans une première partie, on considère un type particulier d’applications de flots de données: les services filtrants. On étudie l'ordonnancement de telles applications sur des plates-formes homogènes et hétérogènes, d'abord sans tenir compte des coûts de communication, puis en les incluant dans le modèle. On considère enfin l’ordonnancement d’un tel calcul sur une chaîne de processeurs. Le comportement d’un service filtrant est comparable à celui d’un calcul effectué sur un processeur non fiable: certains résultats vont être calculés, et d’autres perdus. On étudie le modèle des pannes transitoires. On veut effectuer un calcul à la fois fiable et efficace. La complexité de différentes variantes de ce problème est démontrée. Deux heuristiques sont décrites, puis comparées expérimentalement. Si les pannes transitoires sont les pannes les plus fréquemment rencontrées sur des grilles de calculs classiques, certains types de plates-formes rencontrent d’autres types de défaillances. Les grilles de volontaires sont particulièrement instables. Sur ce type de plate-forme, on veut exécuter des calculs itératifs. Cette application est constituée soit de tâches indépendantes, soit de tâches couplées, qui doivent être calculées ensemble et au même rythme. Dans chaque cas, le problème est d’abord étudié théoriquement, puis des heuristiques sontproposées, et leur performances sont comparées. / This thesis deals with the mapping and the scheduling of workflows. In this context, we consider unreliable platforms, with processors subject to failures. In a first part, we consider a particular model of streaming applications : the filtering services. In this context, we aim at minimizing period and latency. We first neglect communication costs. In this model, we study scheduling problems on homogeneous and heterogeneous platforms. Then, the impact of communication costs on scheduling problems of a filtering application is studied. Finally, we consider the scheduling problem of such an application on a chain of processors. The theoretical complexity of any variant of this problem is proved. This filtering property can model the reliability of processors. The results of some computations are successfully computed, and some other ones are lost. We consider the more frequent failure types : transient failures. We aim efficient and reliable schedules. The complexity of many variants of this problem is proved. Two heuristics are proposed and compared using using simulations. Even if transient failures are the most common failures in classical grids, some particular type of platform are more concerned by other type of problems. Desktop grids are especially unstable. In this context, we want to execute iterative applications. All tasks are executed, then a synchronization occurs, and so on. Two variants of this problem are considered : applicationsof independent tasks, and applications where all tasks need to be executed at same speed. In both cases, the problem is first theoretically studied, then heuristics are proposed and compared using simulations.