Les recherches de cette thèse portent sur la mise en oeuvre des méthodes de la rechercheopérationnelle (RO) pour la conception de circuits numériques dans le domaine du traitementdu signal et de l’image, plus spécifiquement pour des applications multimédia et de visionembarquée.Face à la problématique de “Memory Wall”, les concepteurs de systèmes de vision embarquée,Mancini et al. (Proc.DATE, 2012), ont proposé un générateur de hiérarchies mémoiresad-hoc dénommé Memory Management Optimization (MMOpt). Cet atelier de conception estdestiné aux traitements non-linéaires afin d’optimiser la gestion des accès mémoires de cestraitements. Dans le cadre de l’outil MMOpt, nous abordons la problématique d’optimisationliée au fonctionnement efficace des circuits de traitement d’image générés par MMOpt visantl’amélioration des enjeux de performance (contrainte temps-réel), de consommation d’énergieet de coût de production (contrainte d’encombrement).Ce problème électronique a été modélisé comme un problème d’ordonnancement multiobjectif,appelé 3-objective Process Scheduling and Data Prefetching Problem (3-PSDPP), reflétantles 3 principaux enjeux électroniques considérés. À notre connaissance, ce problème n’apas été étudié avant dans la littérature de RO. Une revue de l’état de l’art sur les principaux travauxliés à cette thèse, y compris les travaux antérieurs proposés par Mancini et al. (Proc.DATE,2012) ainsi qu’un bref aperçu sur des problèmes voisins trouvés dans la littérature de RO,a ensuite été faite. En outre, la complexité de certaines variantes mono-objectif du problèmed’origine 3-PSDPP a été établie. Des approches de résolution, y compris les méthodes exactes(PLNE) et les heuristiques constructives, sont alors proposées. Enfin, la performance de cesméthodes a été comparée par rapport à l’algorithme actuellement utilisé dans l’outil MMOpt,sur des benchmarks disponibles dans la littérature ainsi que ceux fournis par Mancini et al.(Proc.DATE, 2012).Les solutions obtenues sont de très bonne qualité et présentent une piste prometteuse pouroptimiser les performances des hiérarchies mémoires produites par MMOpt. En revanche, vuque les besoins de l’utilisateur de l’outil sont contradictoires, il est impossible de parler d’unesolution unique en optimisant simultanément les trois critères considérés. Un ensemble debonnes solutions de compromis entre ces trois critères a été fourni. L’utilisateur de l’outilMMOpt peut alors décider de la solution qui lui est la mieux adaptée. / The research of this thesis focuses on the application of the Operations Research (OR)methodology to design new optimization algorithms to enable low cost and efficient embeddedvision systems, or more generally devices for multimedia applications such as signal and imageprocessing.The design of embedded vision systems faces the “Memory Wall” challenge regarding thehigh latency of memories holding big image data. For the case of non-linear image accesses, onesolution has been proposed by Mancini et al. (Proc. DATE 2012) in the form of a software tool,called Memory Management Optimization (MMOpt), that creates an ad-hoc memory hierarchiesfor such a treatment. It creates a circuit called a Tile Processing Unit (TPU) that containsthe circuit for the treatment. In this context, we address the optimization challenge set by theefficient operation of the circuits produced by MMOpt to enhance the 3 main electronic designcharacteristics. They correspond to the energy consumption, performance and size/productioncost of the circuit.This electronic problem is formalized as a 3-objective scheduling problem, which is called3-objective Process Scheduling and Data Prefetching Problem (3-PSDPP), reflecting the 3 mainelectronic design characteristics under consideration. To the best of our knowledge, this problemhas not been studied before in the OR literature. A review of the state of the art, including theprevious work proposed by Mancini et al. (Proc.DATE, 2012) as well as a brief overview onrelated problems found in the OR literature, is then made. In addition, the complexity of someof the mono-objective sub-problems of 3-PSDPP problem is established. Several resolutionapproaches, including exact methods (ILP) and polynomial constructive heuristics, are thenproposed. Finally, the performance of these methods is compared, on benchmarks available inthe literature, as well as those provided by Mancini et al. (Proc.DATE, 2012), against the onecurrently in use in the MMOpt tool.The results show that our algorithms perform well in terms of computational efficiency andsolution quality. They present a promising track to optimize the performance of the TPUs producedby MMOpt. However, since the user’s needs of the MMOpt tool are contradictory, such aslow cost, low energy and high performance, it is difficult to find a unique and optimal solutionto optimize simultaneously the three criteria under consideration. A set of good compromisesolutions between these three criteria was provided. The MMOpt’s user can then choose thebest compromise solution he wants or needs.

L'informatique a changé profondément les aspects méthodologiques du processus de découverte dans les différents domaines du savoir. Les chercheurs ont à leur disposition aujourd'hui de nouvelles capacités qui permettent d'envisager la résolution de nouveaux problèmes. Les plates-formes parallèles et distribués composées de ressources partagés entre différents participants peuvent rendre ces nouvelles capacités accessibles à tout chercheur et offre une puissance de calcul qui a été limitée jusqu'à présent, aux projets scientifiques les plus grands (et les plus riches). Dans ce document qui regroupe les résultats obtenus pendant mon doctorat, nous explorons quatre facettes différentes de la façon dont les organisations s'engagent dans une collaboration sur de plates-formes parallèles et distribuées. En utilisant des outils classiques de l'analyse combinatoire, de l'ordonnancement multi-objectif et de la théorie des jeux, nous avons montré comment calculer des ordonnancements avec un bon compromis entre les résultats obtenu par les participants et la performance globale de la plate-forme. En assurant des résultats justes et en garantissant des améliorations de performance pour les différents participants, nous pouvons créer une plate-forme efficace où chacun se sent toujours encourager à collaborer et à partager ses ressources. Tout d'abord, nous étudions la collaboration entre organisations égoïstes. Nous montrons que le comportement égoïste entre les participants impose une borne inférieure sur le makespan global. Nous présentons des algorithmes qui font face à l'égoïsme des organisations et qui présentent des résultats équitables. La seconde étude porte sur la collaboration entre les organisations qui peuvent tolérer une dégradation limitée de leur performance si cela peut aider à améliorer le makespan global. Nous améliorons les bornes d'inapproximabilité connues sur ce problème et nous présentons de nouveaux algorithmes dont les garanties sont proches de l'ensemble de Pareto (qui regroupe les meilleures solutions possibles). La troisième forme de collaboration étudiée est celle entre des participants rationnels qui peuvent choisir la meilleure stratégie pour leur tâches. Nous présentons un modèle de jeu non coopératif pour le problème et nous montrons comment l'utilisation de "coordination mechanisms" permet la création d'équilibres approchés avec un prix de l'anarchie borné. Finalement, nous étudions la collaboration entre utilisateurs partageant un ensemble de ressources communes. Nous présentons une méthode qui énumère la frontière des solutions avec des meilleurs compromis pour les utilisateurs et sélectionne la solution qui apporte la meilleure performance globale. / Computer science is deeply changing methodological aspects of the discovery process in different areas of knowledge. Researchers have at their disposal new capabilities that can create novel research opportunities. Parallel and distributed platforms composed of resources shared between different participants can make these new capabilities accessible to every researcher at every level, delivering computational power that was restricted before to bigger (and wealthy) scientific projects. This work explores four different facets of the rules that govern how organizations engage in collaboration on modern parallel and distributed platforms. Using classical combinatorial tools, multi-objective scheduling and game-theory, we showed how to compute schedules with good trade-offs between the results got by the participants and the global performance of the platform. By ensuring fair results and guaranteeing performance improvements for the participants, we can create an efficient platform where everyone always feels encouraged to collaborate and to share its resources. First, we study the collaboration between selfish organizations. We show how the selfish behavior between the participants imposes a lower bound on the global makespan. We present algorithms that cope with the selfishness of the organizations and that achieve good fairness in practice. The second study is about collaboration between organizations that can tolerate a limited degradation on their performance if this can help ameliorate the global makespan. We improve the existing inapproximation bounds for this problem and present new algorithms whose guarantees are close to the Pareto set. The third form of collaboration studied is between rational participants that can independently choose the best strategy for their jobs. We present a non-cooperative game-theoretic model for the problem and show how coordination mechanisms allow the creation of approximate pure equilibria with bounded price of anarchy. Finally, we study collaboration between users sharing a set of common resources. We present a method that enumerates the frontier of best compromise solutions for the users and selects the solution that brings the best value for the global performance function.

Les systèmes temps-réels sont des systèmes qui sont soumis à "des contraintes de temps", comme par exemple le délais de réponse d'un système à un événement physique. Souvent les temps de réponse sont de l'ordre du milliseconde et parfois même du microseconde. Construire des systèmes temps-réels nécessite l'utilisation de méthodologies de conception et de mise en œuvre qui garantissent la propriété de respect des contraintes de temps, par exemple un système doit réagir dans les limites définies par l'utilisateur tels que les délais et la périodicité. Un délai non respecté dans systèmes temps-réel critique est catastrophique, comme par exemple dans les systèmes automobiles. Si un airbag se déclanche tard dans un accident de voiture, même quelques millisecondes trop tard peuvent conduire à des répercussions graves. Dans les systèmes temps-réels non critiques, une perte significative de performance et de QoS peuvent se produire, comme par exemple dans les réseaux de systèmes multimédia. Contribution: Nous fournissons une méthode de conception rigoureuse des systèmes temps-réel. L'implèmentation est générée à partir d'une application logicielle temps-réel et une plate-forme cible, en utilisant les deux modèles suivants: * Un modèle abstrait représentant le comportement de l'application logicielle en temps réel sous forme d' un automate temporisé. Celui-ci décrit des contraintes temporelles définies par l'utilisateur qui sont indépendantes de la plateforme. Ses transitions sont intemporelles et correspondent à l'exécution des différentes instructions de l'application. * Un modèle physique représentant le comportement du logiciel en temps réel s'exécutant sur une plate-forme donnée. Il est obtenu par l'attribution des temps d'exécution aux transitions du modèle abstrait. Une condition nécessaire pour garantir l'implémentabilité dy système est la "time-safety", c'est à dire, toute séquence d'exécution du modèle physique est également une séquence d'exécution du modèle abstrait. "Time-safety" signifie que la plate-forme est assez rapide pour répondre aux exigences de synchronisation de l'application. Comme les temps d'exécution des actions ne sont pas connus avec exactitude, "time-safety" est vérifiée pour les temps d'exécution pire cas es actions en faisant l' hypothèse de la robustesse. La robustesse signifie que la "time-safety" est préservée lorsqu'on augmente la vitesse de la plate-forme d'exécution. Pour des logiciels et plate-forme d'exécution correspondant à un modèle robuste, nous définissons un moteur d'exécution qui coordonne l'exécution du logiciel d'application afin de répondre à ses contraintes temporelles. En outre, en cas de non-robustesse, le moteur d'exécution permet de détecter les violations de contraintes temporelles en arrêtant l'exécution. Nous avons mis en place le moteur d'exécution pour les programmes BIP. Nous avons validé la méthode pour la conception et la mise en œuvre du robot Dala. Nous montrons les avantages obtenus en termes d'utilisation du processeur et l'amélioration de la latence de la réaction. / Context: Real-time systems are systems that are subject to "real-time constraints"— e.g. operational deadlines from event to system response. Often real-time response times are understood to be in the order of milliseconds and sometimes microseconds. Building real-time systems requires the use of design and implementation methodologies that ensure the property of meeting timing constraints e.g. a system has to react within user-defined bounds such as deadlines and periodicity. A missed deadline in hard real-time systems is catastrophic, like for example in automotive systems, for example if an airbag is fined too late in a car accident, even one ms too late leads to serious repercussions. In soft real-time systems it can lead to a significant loss of performance and QoS like for example in networked multimedia systems. Contribution: We provide a rigorous design and implementation method for the implementation of real-time systems. The implementation is generated from a given real-time application software and a target platform by using two models: * An abstract model representing the behavior of real-time software as a timed automaton. The latter describes user-defined platform-independent timing constraints. Its transitions are timeless and correspond to the execution of statements of the real-time software. * A physical model representing the behavior of the real-time software running on a given platform. It is obtained by assigning execution times to the transitions of the abstract model. A necessary condition for implementability is time-safety, that is, any (timed) execution sequence of the physical model is also an execution sequence of the abstract model. Time-safety means that the platform is fast enough to meet the timing requirements. As execution times of actions are not known exactly, time-safety is checked for worst-case execution times of actions by making an assumption of time-robustness: time-safety is preserved when speed of the execution platform increases. For given real-time software and execution platform corresponding to a time-robust model, we define an execution Engine that coordinates the execution of the application software so as to meet its timing constraints. Furthermore, in case of non-robustness, the execution Engine can detect violations of time-safety and stop execution. We have implemented the execution Engine for BIP programs with real-time constraints. We have validated the method for the design and implementation of the Dala rover robot. We show the benefits obtained in terms of CPU utilization and amelioration in the latency of reaction.

Les infrastructures de calcul très haute performance ont connu une croissance rapide en particulier ces dernières années. Cette croissance a toujours été motivée par les besoins accrus en puissance de calcul qu'expriment les scientifiques dans divers domaines. Cependant, ces systèmes devenus de plus en plus larges constituent de gros consommateurs d'électricité et consomment déjà plusieurs mégawatts. Afin de consommer ''moins'' et ''mieux'', nous avons proposé un environnement logiciel qui d'une part, permet de choisir avant de pré-exécuter l'application, les versions de services applicatifs consommant le moins d'énergie, et qui d'autre part, repose sur une grille électrique intelligente pour planifier les réservations des ressources de calcul de ces infrastructures. Cet environnement, appelé SESAMES, a été adapté à deux services applicatifs indispensables au calcul très haute performance : la tolérance aux pannes et la diffusion de données. Des validations expérimentales ont montré que l'on peut réduire la consommation énergétique de chacun des deux services étudiés en s'appuyant sur les estimations énergétiques précises fournies par SESAMES pour n'importe quel contexte d'exécution et pour n'importe quelle plate-forme dotée de wattmètres. Notre méthodologie d'estimation repose sur une description du contexte d'exécution et sur une calibration de la plate-forme d'exécution basée sur la collecte de mesures énergétiques. Des simulations ont démontré que l'ordonnanceur multi-critères des réservations de ressources proposé dans SESAMES, permet de réduire à la fois la consommation énergétique, le coût financier et l'impact environnemental de ces réservations, tout en respectant les contraintes imposées par l'utilisateur et le fournisseur d'énergie. / High performance computing (HPC) infrastructures have experienced a rapid growth, particularly these last years. This growth has been driven by the increased need in terms of computational power expressed by scientists in various fields. However, their increasing size makes them important electricity consumers since they already consume several megawatts. In order to consume "less" and better", we proposed a framework which permits to choose the less consuming versions of the services before pre-executing the application. In addition, our framework relies on a smart grid in order to schedule resource reservations on these computing infrastructures. This framework, called SESAMES, is adapted to two services required in high performance computing: fault tolerance and data broadcasting. Experimental validations have shown that we can reduce the energy consumption of both services by relying on accurate energy estimations provided by SESAMES for any execution context and for any platform equipped with wattmeters. Our estimation methodology is based on a description of the execution context and on a platform calibration that consists of gathering energy measurements. Simulations have shown that the multi-criteria reservation scheduler proposed in SESAMES, simultaneously reduces the energy consumption, the financial cost and the environmental impact of these reservations, while respecting the constraints imposed by the user and the energy supplier.

Dans cette thèse, j'ai considéré d'un point de vue théorique deux problèmes importants pour les futures plateformes dîtes Exascales : les restrictions liées à leur fiabilité ainsi que les contraintes énergétiques. En première partie de cette thèse, je me suis intéressé à l'étude de placements optimal de ces checkpoints dans un but de minimisation de temps total d'exécution. En particulier, j'ai considéré les checkpoints périodiques et coordonnés. J'ai considéré des prédicteurs de fautes capables de prévoir, de manière imparfaite, les fautes arrivant sur la plateforme. Dans ce contexte, j'ai conçu des algorithmes efficaces pour résoudre mes problèmes. Dans un deuxième temps, j'ai considéré des fautes silencieuses. Ces fautes ne peuvent être détectées qu'uniquement par un système de vérification.Dans le cas où une de ces fautes est détectée, l'utilisateur doit retourner au point de sauvegarde le plus récent qui n'a pas été affecté par cette faute, si un tel point existe ! Dans ce contexte, j'ai à nouveau proposé des algorithmes optimaux au premier ordre, mixant points de sauvegarde et points de vérification. Dans la seconde partie de cette thèse, j'ai considéré des problèmes énergétiques liés à ces mêmes plateformes. Ces problèmes critiques doivent être reliés aux problèmes de fiabilité de la partie précédente. Dans ce contexte, j'ai couplé des techniques de baisse de consommation énergétique à des techniques d'augmentation de fiabilité comme la reexécution, la réplication ainsi que le checkpoint. Pour ces différents problèmes, j'ai pu fournir des algorithmes dont l'efficacité a été montrée soit au travers de simulations, soit grâce à des preuves mathématiques. / This thesis deals with two issues for future Exascale platforms, namelyresilience and energy.In the first part of this thesis, we focus on the optimal placement ofperiodic coordinated checkpoints to minimize execution time.We consider fault predictors, a software used by system administratorsthat tries to predict (through the study of passed events) where andwhen faults will strike. In this context, we propose efficientalgorithms, and give a first-order optimal formula for the amount ofwork that should be done between two checkpoints.We then focus on silent data corruption errors. Contrarily to fail-stopfailures, such latent errors cannot be detected immediately, and amechanism to detect them must be provided. We compute the optimal periodin order to minimize the waste.In the second part of the thesis we address the energy consumptionchallenge.The speed scaling technique consists in diminishing the voltage of theprocessor, hence diminishing its execution speed. Unfortunately, it waspointed out that DVFS increases the probability of failures. In thiscontext, we consider the speed scaling technique coupled withreliability-increasing techniques such as re-execution, replication orcheckpointing. For these different problems, we propose variousalgorithms whose efficiency is shown either through thoroughsimulations, or approximation results relatively to the optimalsolution. Finally, we consider the different energetic costs involved inperiodic coordinated checkpointing and compute the optimal period tominimize energy consumption, as we did for execution time.

Pour assurer les communications dans un réseau de capteurs sans fil, les capteurs utilisent un modèle simplifié de protocoles en couches inspiré du modèle OSI. Ce modèle comporte cinq couches, chaque couche devant assurer des fonctionnalités indépendantes et particulières. Nous nous intéressons à deux couches qui sont impliquées directement dans les décisions assurant les communications, la couche Liaison de données dans laquelle le protocole MAC assure la coordination des communications entre voisins directs, et la couche Réseau dans laquelle le protocole de routage est responsable de trouver une route entre un émetteur et un récepteur. Chacune des deux couches vise à améliorer certaines métriques, comme la latence, mais les décisions incohérentes venant de différents protocoles peuvent ne pas le permettre. Par conséquent, les décisions spatiales du protocole de routage et les décisions temporelles du protocole MAC doivent être corrélées pour optimiser la latence des communications. Les protocoles cross-layer résolvent ce problème soit en assurant des communications entre des protocoles des deux couches, soit en combinant les deux couches en une nouvelle couche. Dans ce contexte, cette thèse étudie les protocoles cross-layer existants entre MAC et routage et propose de nouvelles approches ayant comme but de minimiser la latence des communications. Dans un premier temps, nous avons proposé un protocole de routage qui utilise des informations du protocole MAC qu’est un TDMA pour trouver un chemin entre le noeud qui capte les données et la station de base tout en minimisant la latence des communications [1]. Ensuite, nous nous sommes intéressés au cas inverse, i.e. des approches MAC qui utilisent des informations de routage pour établir des ordonnancements TDMA de communication pour les nœuds du réseau, ces ordonnancements visant toujours à optimiser la latence des communications [2, 3, 5].Enfin, dans [4], nous avons proposé une approche qui combine un protocole MAC et un protocole de routage en un seul protocole. / Traditionally, in Wireless Sensor Networks, protocols are designed independently in the layered protocol stack, and metrics involved in several layers can be affected. Communication latency is one metric example, impacted by both the routing protocol in the network layer and the MAC protocol in the data link layer. Cross-layer protocols are known to be more efficient when exploiting the dependencies between these layers.In this context, and aiming to minimize the communication latency, we propose different cross-layer approaches concerning routing trees and TDMA schedules. First, we propose a routing approach using information of the TDMA schedule. Then, we propose different TDMA scheduling approaches which use information of the routing tree. Finally, we propose an approach that combines MAC and routing to produce a routing tree and a TDMA schedule simultaneously. Extensive simulations have shown better results of our contributions compared to the state of the art in terms of latency. Other metrics such as the energy consumption, the duty cycle of the nodes and the number of hops in the routing paths were also considered during the evaluation of our contributions.

L’évolution continue des environnements de production et l’augmentation des besoins des clients, demandent un processus de production plus rapide et efficace qui contrôle plusieurs paramètres en même temps. Nous nous sommes intéressés au développement de méthodes d’aide à la décision qui permettent d’améliorer l’ordonnancement de la production. L’entreprise partenaire (Norelem) fabrique des pièces de précision mécanique, il faut donc prendre en compte les différentes contraintes de ressources (humaines et d’outillage) existantes dans l’atelier de production.Nous avons abordé l’étude d’un atelier d’ordonnancement de type open shop ou chemin ouvert, où une tâche peut avoir de multiples séquences de production puisque l’ordre de fabrication n’est pas fixé et l’objectif à minimiser est le temps total de séjour. Des contraintes d’affectation de ressources humaines (multi-compétences) et de disponibilité d’outillage ont été prises en compte.Des modèles mathématiques linéaires et non-linéaires ont été développés pour décrire la problématique. Etant donné que les méthodes exactes sont limitées aux instances de petites tailles à cause des temps de calcul, des méthodes de résolution approchées ont été proposées et comparées. De plus, nous avons abordé l’optimisation multi-objectif en considérant trois objectifs, la minimisation du temps total de séjour et l’équilibrage de charge des ressources (humaines et machines).L’efficacité des méthodes est prouvée grâce à des tests sur des instances théoriques et l’application au cas réel / The continuous evolution of manufacturing environments and the growing of customer needings, leads to a faster and more efficient production process that controls an increasing number of parameters. This thesis is focused on the development of decision making methods in order to improve the production scheduling. The industrial partner (Norelem) produces standardized mechanical elements, so many different resource constraints (humans and tools) are presented in its workshop.We study an open shop scheduling problem where one job can follow multiple production sequences because there is no fixed production sequence and the objective function is to minimize the total flow time. In addition, multi-skilled personnel assignment and tool’s availability constraints are involved.Mathematical models: linear and non-linear formulations have been developed to describe the problem. Knowing the exact method limitations in terms of instance sizes because of the duration, heuristics methods have been proposed and compared. Besides that, the multi-objective optimization was exposed to deal with three objectives as total flow time minimization and workload balancing concerning both, humans and machines.The efficiency of these methods was proved by several theoretical instance tests and the application on the real industrial case

Les nouvelles architectures de calcul intensif intègrent de plus en plus de microprocesseurs qui eux-mêmes intègrent un nombre croissant de cœurs de calcul. Cette multiplication des unités de calcul dans les architectures ont fait apparaître des topologies fortement hiérarchiques. Ces architectures sont dites NUMA. Les algorithmes de simulation numérique et les solveurs de systèmes linéaires qui en sont une brique de base doivent s'adapter à ces nouvelles architectures dont les accès mémoire sont dissymétriques. Nous proposons dans cette thèse d'introduire un ordonnancement dynamique adapté aux architectures NUMA dans le solveur PaStiX. Les structures de données du solveur, ainsi que les schémas de communication ont dû être modifiés pour répondre aux besoins de ces architectures et de l'ordonnancement dynamique. Nous nous sommes également intéressés à l'adaptation dynamique du grain de calcul pour exploiter au mieux les architectures multi-cœurs et la mémoire partagée. Ces développements sont ensuite validés sur un ensemble de cas tests sur différentes architectures. / New supercomputers incorporate many microprocessors which include themselves one or many computational cores. These new architectures induce strongly hierarchical topologies. These are called NUMA architectures. Sparse direct solvers are a basic building block of many numerical simulation algorithms. They need to be adapted to these new architectures with Non Uniform Memory Accesses. We propose to introduce a dynamic scheduling designed for NUMA architectures in the PaStiX solver. The data structures of the solver, as well as the patterns of communication have been modified to meet the needs of these architectures and dynamic scheduling. We are also interested in the dynamic adaptation of the computation grain to use efficiently multi-core architectures and shared memory. Experiments on several numerical test cases will be presented to prove the efficiency of the approach on different architectures.

Nos travaux concernent la mise en œuvre de méthodologies pour la résolution de problèmes d’ordonnancement en industries agroalimentaires. Trois nouvelles approches basées sur les algorithmes génétiques, sont proposées pour la résolution de problèmes d’ordonnancement multi-objectifs : les algorithmes génétiques séquentiels (SGA), les algorithmes génétiques parallèles (PGA) et les algorithmes génétiques parallèles séquentiels (PSGA). Deux approches coopératives multi-objectifs en mode relais, SH_GA/TS et SH_GA/SA, hybridant toutes les deux des métaheuristiques de haut niveau, sont par la suite proposées. Un algorithme évolutionnaire et un algorithme de recherche locale sont, dans ce cas exécutés séquentiellement / The purpose of our works is the implementation of methodologies for the resolution of the agro-food industry scheduling problem. Three new approaches based on genetic algorithms are proposed to solve multi-objectives scheduling problems: sequential genetic algorithms (SGA), parallel genetic algorithms (PGA) and parallel sequential genetic algorithms (PSGA). Two high-level hybrid algorithms, SH_GA/TS et SH_GA/SA, are also proposed. The purpose in this hybridization is to benefit the exploration of the solution space by a population of individuals with the exploitation of solutions through a smart search of the local search algorithm

La logistique de gestion de crise fait de plus en plus parler d’elle. En effet, que ce soit au sujet de conflits géopolitiques ou de catastrophes naturelles, ou encore lorsqu’il s’agit d’urgences de proximité, on ne peut plus passer à côté de la gestion de crise pour faire face à des faits internationaux ou nationaux. La logistique de gestion de crise œuvre pour que les secours soient optimisés et que l’aide et le ravitaillement en nourriture, eau, médicaments, soit apportés rapidement aux zones sinistrées. Les travaux de recherche présentés dans cette thèse, dans le cadre d’une coopération avec le département logistique d’EADS, visent à apporter une réponse à ces défis. Nous présentons, dans ce contexte, des solutions basées sur une approche de modélisation, optimisation et simulation orientée agents de flux logistiques. Les problèmes de gestion de flux abordés nous ont permis d’étudier et développer trois volets d’investigation : un module d’aide au positionnement des zones logistiques qui permet de minimiser les distances entre les zones et d’optimiser leurs nombre et ce pour une meilleure circulation des flux, une approche innovante pour l’ordonnancement distribué des tâches de livraison qui permet d’apporter une solution à un problème de gestion des flux fortement distribué, et finalement un agent holonique qui permet de fournir une estimation de la consommation à venir d’un site logistique, en alliant l’expertise des logisticiens aux modèles à base de logique floue. Pour démontrer l’efficacité des approches utilisées, un démonstrateur baptisé OBAC (Optimisation à Base d’Agents Communicants) a été réalisé, intégrant toutes ces approches et applications militaires / Nowadays, crisis management logistics is facing new challenges. Indeed, geopolitical conflicts, natural disasters or emergencies can cause big damages and so require rapid and effective response. Due to their sudden occurrence, we are countering a high disturbances context: a Crisis Management Supply Chain (CMSC). Working in such an uncertain environment incites to be equipped with optimization and cooperation mechanisms assuring all the chain actors satisfaction, while acting in a collective way to reach a common objective: the crisis management.In this thesis, we focus on the definition of a modeling approach and an agent-based simulation of the Crisis Management Supply Chain. We propose a decision support system that deals with three problems: the optimal positioning of logistics zones to facilitate the flows circulation, an innovative method for solving a highly-distributed delivery scheduling problem, based on a multi-agent system, for the distribution of relief materials (food, water, clothes, etc.) to the areas affected by the disaster, and finally a need estimating agent to give an accurate forecast of resources’ consumption in the logistic zones. Blending the agent paradigm with the optimization technics helped reach our goals of implementing a large-scale decision support system. The simulation results highlight our contributions