La programmation par contraintes est une approche régulièrement utilisée pour traiter des problèmes d’ordonnancement variés. Les problèmes d’ordonnancement cumulatifs représentent une classe de problèmes dans laquelle des tâches non morcelable peuvent être effectuées en parallèle. Ces problèmes apparaissent dans de nombreux contextes réels, tels que par exemple l’allocation de machines virtuelles ou l’ordonnancement de processus dans le "cloud", la gestion de personnel ou encore d’un port. De nombreux mécanismes ont été adaptés et proposés en programmation par contraintes pour résoudre les problèmes d’ordonnancement. Les différentes adaptations ont abouti à des raisonnements qui semblent à priori significativement distincts. Dans cette thèse nous avons effectué une analyse détaillée des différents raisonnements, proposant à la fois une notation unifiée purement théorique mais aussi des règles de dominance, permettant une amélioration significative du temps d’exécution d’algorithmes issus de l’état de l’art, pouvant aller jusqu’à un facteur sept. Nous proposons aussi un nouveau cadre de travail pour l’ordonnancement cumulatif robuste, permettant de trouver des solutions supportant qu’à tout moment une ou plusieurs tâches soit retardées, sans remise en cause de l’ordonnancement généré et en gardant une date de fin de projet satisfaisante. Dans ce cadre, nous proposons une adaptation d’un algorithme de l’état de l’art, Dynamic Sweep. / Constraint programming is an approach regularly used to treat a variety of scheduling problems. Cumulative scheduling problems represent a class of problems in which non-preemptive tasks can be performed in parallel. These problems appear in many contexts, such as for example the allocation of virtual machines, the ordering process in the "cloud", personnel management or a port. Many mechanisms have been adapted and offered in constraint programming to solve scheduling problems. The various adaptations have resulted in reasoning that appear a priori significantly different. In this thesis we performed a detailed analysis of the various arguments, offering both a theoretical unified caracterization but also dominance rules, allowing a significant improvement in execution time of algorithms from the state of the art, up to a factor of seven. we also propose a new framework for robust cumulative scheduling, to find solutions that support at any time one or more tasks to be delayed while keeping a satisfactory end date of the project and without calling into question the generated scheduling. In this context, we propose an adaptation of an algorithm of the state of the art, Dynamic Sweep.

Avec l’émergence du calcul haute-performance (HPC) et des applications Big Data, de nouvelles problématiques cruciales sont apparues. Parmi elles on trouve le problème du transfert de données, c’est-à-dire des communications entre machines, qui peut génerer des délais lors de gros calculs en plus d’avoir un impact sur la consommation énergétique. La réplication, que ce soit de tâches ou de fichiers, est un facteur qui accroît ces communications, tout en étant un outil quasi-indispensable pour améliorer le parallélisme du calcul et la résistance aux pannes. Dans cette thèse nous nous intéressons à la réplication de fichiers et à son impact sur les communications au travers de deux problèmes. Dans le premier, la multiplication de matrices en parallèle, le but est de limiter autant que possible ces réplications pour diminuer la quantité de données déplacées. Dans le second, l’ordonnancement de la phase « Map » de MapReduce, il existe une réplication initiale qu’il faut utiliser au mieux afin d’obtenir l’ordonnancement le plus rapide ou entraînant le moins de création de nouvelles copies. En plus de la réplication, nous nous intéressons aussi à la comparaison entre stratégies d’ordonnancement statiques (allocations faites en amont du calcul) et dynamiques (allocations faites pendant le calcul) sur ces deux problèmes avec pour objectif de créer des stratégies hybrides mélangeant les deux aspects. Pour le premier problème, le produit de matrices en parallèle, nous nous ramenons à un problème de partition de carré où l’équilibrage de charge est donné en entrée. Cet équilibrage donné, le but est de minimiser la somme des semi-paramètres des rectangles couvrant des zones ainsi créés. Ce problème a déjà été étudié par le passé et nous démontrons de nouveaux résultats. Nous proposons ainsi deux nouveaux algorithmes d’approximation, l’un fondé sur une stratégie récursive et l’autre sur l’usage d’une courbe fractale. Nous présentons également une modélisation alternative, fondée sur un problème similaire de partition de cube, dont nous prouvons la NP-complétude tout en fournissant deux algorithmes d’approximation. Pour finir, nous réalisons également une implémentation pratique du produit de matrices en utilisant nos stratégies d’allocation grâce à la librairie StarPU. Les résultats expérimentaux montrent une amélioration du temps de calcul ainsi qu’une diminution significative des transferts de données lorsqu’on utilise une stratégie statique d’allocation couplée à une technique de vol de tâches. Pour le second problème, l’ordonnancement de la phase « Map » de MapReduce, plusieurs copies des fichiers d’entrée sont distribuées parmi les processeurs disponibles. Le but ici est de faire en sorte que chaque tâche soit attribuée à un processeur possédant son fichier d’entrée tout en ayant le meilleur temps de calcul total. Une autre option étudiée est d’autoriser les tâches nonlocales (attribués à des processeurs ne possédant pas leurs fichiers d’entrée) mais d’en limiter le nombre. Dans cette thèse nous montrons premièrement qu’un algorithme glouton pour ce problème peut être modélisé par un processus de « balls-in-bins » avec choix, impliquant une surcharge (nombre de tâches supplémentaires par rapport à la moyenne) en O(mlogm) où m est le nombre de processeurs. Secondement, dans le cas où les tâches non-locales sont interdites, nous relions le problème à celui de l’orientation de graphes, ce qui permet d’obtenir des algorithmes optimaux et polynomiaux et l’existence d’une assignation presque parfaite avec forte probabilité. Dans le cas où les tâches non locales sont autorisées, nous proposons également des algorithmes polynomiaux et optimaux. Finalement, nous proposons un ensemble de simulations pour montrer l’efficacité de nos méthodes dans le cas de tâches faiblement hétérogènes. / The increasing importance of High Performance Computing (HPC) and Big Data applications creates new issues in parallel computing. One of them is communication, the data transferred from a processor to another. Such data movements have an impact on computational time, inducing delays and increase of energy consumption. If replication, of either tasks or files, generates communication, it is also an important tool to improve resiliency and parallelism. In this thesis, we focus on the impact of the replication of input files on the overall amount of communication. For this purpose, we concentrate on two practical problems. The first one is parallel matrix multiplication. In this problem, the goal is to induce as few replications as possible in order to decrease the amount of communication. The second problem is the scheduling of the “Map” phase in the MapReduce framework. In this case, replication is an input of the problem and this time the goal is to use it in the best possible way. In addition to the replication issue, this thesis also considers the comparison between static and dynamic approaches for scheduling. For consistency, static approaches compute schedules before starting the computation while dynamic approaches compute the schedules during the computation itself. In this thesis we design hybrid strategies in order to take advantage of the pros of both. First, we relate communication-avoiding matrix multiplication with a square partitioning problem, where load-balancing is given as an input. In this problem, the goal is to split a square into zones (whose areas depend on the relative speed of resources) while minimizing the sum of their half-perimeters. We improve the existing results in the literature for this problem with two additional approximation algorithms. In addition we also propose an alternative model using a cube partitioning problem. We prove the NP-completeness of the associated decision problem and we design two approximations algorithms. Finally, we implement the algorithms for both problems in order to provide a comparison of the schedules for matrix multiplication. For this purpose, we rely on the StarPU library. Second, in the Map phase of MapReduce scheduling case, the input files are replicated and distributed among the processors. For this problem we propose two metrics. In the first one, we forbid non-local tasks (a task that is processed on a processor that does not own its input files) and under this constraint, we aim at minimizing the makespan. In the second problem, we allow non-local tasks and we aim at minimizing them while minimizing makespan. For the theoretical study, we focus on tasks with homogeneous computation times. First, we relate a greedy algorithm on the makespan metric with a “ball-into-bins” process, proving that this algorithm produces solutions with expected overhead (the difference between the number of tasks on the most loaded processor and the number of tasks in a perfect distribution) equal to O(mlogm) where m denotes the number of processors. Second, we relate this scheduling problem (with forbidden non-local tasks) to a problem of graph orientation and therefore prove, with the results from the literature, that there exists, with high probability, a near-perfect assignment (whose overhead is at most 1). In addition, there are polynomial-time optimal algorithms. For the communication metric case, we provide new algorithms based on a graph model close to matching problems in bipartite graphs. We prove that these algorithms are optimal for both communication and makespan metrics. Finally, we provide simulations based on traces from a MapReduce cluster to test our strategies with realistic settings and prove that the algorithms we propose perform very well in the case of low or medium variance of the computation times of the different tasks of a job.

La prise en compte de machines à traitement par batch dans les problèmes d’ordonnancement d’ateliers complexes de type job-shop est particulièrement difficile. La fabrication de semiconducteurs est probablement l’une des applications pratiques les plus importantes pour ce types de problèmes. Nous considérons un problème d’ordonnancement de type job-shop flexible avec « p-batching », des flux rentrants, des temps de préparation dépendant de la séquence et des dates de début au plus tôt. Le but c’est d’optimiser différentes fonctions objectives régulières.Les approches existantes par graphe disjonctif pour ce problème utilise des nœuds dédiés pour représenter explicitement les batches. Afin de faciliter la modification du graphe conjonctif, notre nouvelle modélisation réduit cette complexité en modélisant les décisions de batching à travers les poids des arcs. Une importante contribution de cette thèse est un algorithme original qui prend les décisions de batching lors du parcours du graphe. Cet algorithme est complété par un déplacement (« move ») intégré qui permet de reséquencer ou réaffecter les opérations. Cette combinaison donne un voisinage riche que nous appliquons dans une approche méta-heuristique de type GRASP.Nous étendons cette approche en prenant en compte de nouvelles contraintes qui ont un rôle important dans l’application industrielle considérée. En particulier, nous modélisons de manière explicite les ressources internes des machines, et nous considérons un temps maximum d’attente entre deux opérations quelconques d’une gamme de fabrication. Les résultats numériques sur des instances de la littérature pour des problèmes plus simples ainsi que sur de nouvelles instances montrent la généricité et l’applicabilité de notre approche. Notre nouvelle modélisation permet de faciliter les extensions à d’autres contraintes complexes rencontrées dans les applications industrielles. / The integration of batching machines within a job-shop environment leads to a complex job-shop scheduling problem. Semiconductor manufacturing presumably represents one of the most prominent practical applications for such problems. We consider a flexible job-shop scheduling problem with p-batching, reentrant flows, sequence dependent setup times and release dates while considering different regular objective functions. The scheduling of parallel batching machines and variants of the job-shop scheduling problem are well-studied problems whereas their combination is rarely considered.Existing disjunctive graph approaches for this combined problem rely on dedicated nodes to explicitly represent batches. To facilitate modifications of the graph, our new modeling reduces this complexity by encoding batching decisions into edge weights. An important contribution is an original algorithm that takes batching decisions “on the fly” during graph traversals. This algorithm is complemented by an integrated move to resequence and reassign operations. This combination yields a rich neighborhood that we apply within a GRASP based metaheuristic approach.We extend this approach by taking further constraints into account that are important in the considered industrial application. In particular, we model internal resources of machines in detail and take maximum time lag constraints into account. Numerical results for benchmark instances of different problem types show the generality and applicability of our approach. The conciseness of our idea facilitates extensions towards further complex constraints needed in real-world applications.

Au cours de cette thèse, l'exploration de l'espace de solutions par des métaheuristiques est abordée. Les métaheuristiques sont des méthodes d'optimisation utilisées pour résoudre des problèmes NP-difficile. Elles explorent aléatoirement l'espace de recherche pour trouver les meilleures solutions. Dans un premier temps, l'ensemble des solutions est modélisé par un espace unidimensionnel par une Méthode de Conversion de l'Espace de recherche (MCE). Des métriques sont proposées pour évaluer l'exploration de l'espace de recherche par une métaheuristique en identifiant les zones explorées et inexplorées. Ces métriques sont utilisées pour orienter l'exploration de l'espace de recherche d'une méthode d'optimisation.La convergence est améliorée en accentuant le recherche dans les zones explorées. Pour sortir des minimums locaux, l'exploration est diversifiée en la dirigeant vers les zones inexplorées. En associant l'exploration du voisinage des solutions et ces métriques cartographiques, il est possible d'améliorer les performances des métaheuristiques. Plusieurs algorithmes mono-objectifs et multiobjectifs sont implémentés en version classique, hybridé par la recherche locale et par la MCE. Le Flexible Job Shop Problem (FJSP) est utilisé comme problème de référence. Les expérimentations avec les algorithmes hybridés montrent une amélioration des performances / In this thesis, the solution space exploration by the metaheuristic is developed. The metaheuristics optimization methods are used to solve NP-hard problems. They explore randomly the search space to look for the best solutions. In a first step, the solution set is modeled by a one-dimensional space by a Mapping Method (MaM). Metrics are proposed to evaluate the search space exploration by a metaheuristic, identifying the explored and unexplored zones. These metrics are used to guide the search space exploration of an optimization method. The convergence is improved by emphasizing the research in the zones explored. To get out local minima, the exploration is diversified by pointing it towards the unexplored zones. Combining the neighbour discovery of the solutions and these mapping metrics, it is possible to improve the performance of metaheuristics. Several single-objective and multi-objective algorithms are implemented in the classic version, hybridized with local search and MaM. The Flexible Job Shop Problem (FJSP) is used as a reference problem. The experimentations with hybridized algorithms show performance improved

Les réseaux véhiculaires (VANETS) sont en phase de devenir incontournable pour les infrastructures routière améliorant le confort et la sécurité. Les VANETS possèdent quelques caractéristiques, liées la vitesse des véhicules qui peut devenir importante, concernant le changement rapide de topologie la mise à l'échelle, la densité du réseau, etc. Ces caractéristiques ont d'importantes implications sur la conception des protocoles d'accès (MAC) dans ce type de réseau. Le standard 802.11p est l'objet d'une attention importante par la communauté comme partie important du standard WAVE pour les VANETs. Cependant, la gestion de la qualité de service par le standard 802.11p ne peut pas répondre aux exigences d'une communication réaliste dans les réseaux véhiculaires. Trois sous problèmes ont été identifiés pour être traités dans le cadre des travaux de la présente thèse:(i) Problème du rapport cyclique des canaux CCH et SCH(ii) Problème de la qualité de service(iii) Problème de conception du protocole MAC multi-canaux. En se basant sur ces trois problèmes, trois approches ont été proposées(i) Une approche adaptative des rapports cycliques a été proposée, basée sur le trafic-réseau temps-réel(ii) Un modèle de la qualité de service a été proposé pour analyser la QdS dans les VANETS sous différentes configuration de l'intervalle SCH(iii) Un mécanisme d'ordonnancement ainsi qu'un protocole MAC multi-canaux a été proposé. Les différentes propositions ont été validées en simulation en exploitant différentes métriques de QdS pour montrer l'intérêt des solutions apportés aux problèmes identifiés ci-dessus / Vehicular ad-hoc Networks (VANETs) are becoming more and more popular as a means to increase the traffic safety and comfort. VANETs have some characteristics due to the vehicle's high speeds mobility such as rapid changes of topology, potentially large-scale, veritable network density and so on. These characteristics have important implications for design of MAC protocol in VANETs. 802.11p standard are attracting increasingly more attention as an important part of the WAVE protocol in VANETs. However the QoS of 802.11p standard can not yet meet the requirements of the realistic vehicular communication networks. Three sub-problems are identified in this study: (i) CCH and SCHs duty cycle problem, (ii) QoS analysis problem and (iii) Multichannel MAC protocol designing problem. Based on these problems, three approaches are proposed in this study: (i) To propose a duty cycle adaptive MAC protocol in which the duty cycle of CCH and SCH will be adapted based on the realtime network traffic; (ii) To propose a model to analyze the QoS in VANETs with various SCH interval settings; (iii) To propose a scheduling and QoS enhancement multi-channel MAC protocol in VANETs. All the proposed algorithms are implemented and validated in discrete event simulator. The simulation results demonstrate that the important QoS metrics such as the reliability, throughput, successful throughput, network capacity and channel utilization are improved by the proposed algorithms in this project

L'objet de nos travaux porte sur la proposition d'une architecture hybride IEEE 802.11e/AFDX (Avionics Full Duplex switched ethernet) et sur l'étude des techniques permettant l'interconnexion d'un réseau avionique filaire AFDX et d'un réseau sans fil IEEE802.11e pour des applications de maintenance au sol. Ces techniques devront être capables de satisfaire les exigences temporelles des flux AFDX, en particulier la latence de bout à bout et la gigue. Pour des raisons de déterminisme d'accès au médium, nous avons focalisé nos travaux sur l'adaption de la méthode d'accès HCCA (HCF Controlled Channel Access) pour supporter les exigences de QoS du réseau AFDX. L'utilisation de la technologie IEEE 802.11e et de sa méthode d'accès HCCA n'est pas sans contrainte. L'HCCA est plus orientées pour transporter des flux multimédias tels que la voix et la vidéo, ces derniers n'imposant pas les mêmes contraintes temporelles ni le même niveau d'intégrité des données que les flux AFDX. Pour répondre aux exigences des trafics AFDX (gigue et latence), il est primordial d'améliorer l'HCCA. Nous proposons ainsi une méthode d'accès basée sur l'HCCA appelé AFS-HCCA (AFDX Flows Scheduling with HCCA). Notre méthode implémente deux ordonnanceurs: (1) un ordonnanceur local distribué sur toutes les stations (QSTA) et (2) un ordonnanceur centralisé et contrôlé par le point d'accès (HC). L'ordonnanceur local nommé AWS (AFDX Wireless Scheduler) améliore considérablement celui de référence HCCA, car il sérialise les trames en fonction de leurs contraintes temporelles et intègre une méthode de retransmission contrôlée. AWS n'agit pas sur l'optimisation de la bande passante, d'où notre proposition de deux stratégies supplémentaires: Optimized Solution et Released Bandwidth Solution. Les résultats obtenus par l'ordonnancement AWS distribué et ses stratégies de gestion de la bande passante montrent de réelles nouvelles performances par rapport à la norme HCCA. Cependant, il est indispensable d'ordonnancer de façon centralisée l'ensemble de ces flux pour garantir un accès optimal au médium. Nous avons proposé deux méthodes d'ordonnancement hors-ligne : AFBA (Advanced Fixe BandWidth Allocation) et VBA (Variable Bandwidth Allocation). AFBA alloue des bandes passantes fixes calculées à priori pour satisfaire les exigences temporelles de tous les flux AFDX. VBA quant à lui est basé sur une allocation de bandes passantes variables calculée en fonction des arrivées des trames dans les files d'attente de chaque station. Les ordonnanceurs locaux et centraux avec leurs variantes ont été modélisés et simulés avec OPNET à partir de différents scénarios réels de flux AFDX. Les résultats montrent que l'HCCA de référence de la norme 802.11e n'est pas adapté aux fortes contraintes temporelles de l'AFDX. Nos contributions en termes de sérialisation des flux et d'optimisation de la bande passante réduisent les pertes de trames de 93%, même dans un pire cas avec un réseau chargé et un taux d'erreur binaire élevé. / The object of our works concerns at the suggestion of hybrid architecture IEEE 802.11e / AFDX (Avionics Full Duplex switched ethernet) and the study of techniques allowing the interconnection of a wired avionic network AFDX and a wireless network IEEE802.11e for applications of maintenance the ground

Il y a un intérêt croissant pour le développement d'applications sur les plates-formes multiprocesseurs homo- et hétérogènes en raison de l'extension de leur champ d'application et de l'apparition des puces many-core, telles que Kalray MPPA-256 (256 cœurs) ou TEGRA X1 de NVIDIA (256 GPU et 8 cœurs 64 bits CPU). Étant donné l'ampleur de ces nouveaux systèmes massivement parallèles, la mise en œuvre des applications sur ces plates-formes est difficile à cause de leur complexité, qui tend à augmenter, et de leurs exigences strictes à la fois qualitatives (robustesse, fiabilité) et quantitatives (débit, consommation d’énergie). Dans ce contexte, les Modèles de Calcul (MdC) flot de données ont été développés pour faciliter la conception de ces applications. Ces MdC sont par définition composées de filtres qui échangent des flux de données via des liens de communication. Ces modèles fournissent une représentation intuitive des applications flot de données, tout en exposant le parallélisme de tâches de l’application. En outre, ils fournissent des capacités d'analyse statique pour la vivacité et l’exécution en mémoire bornée. Cependant, de nouvelles applications de signalisation et de traitement des médias complexes présentent souvent plusieurs défis majeurs qui ne correspondent pas aux restrictions des modèles flot de données statiques classiques: 1) Comment fournir des services garantis contre des interférences inévitables qui peuvent affecter des performances temps réel ?, et 2) Comment ces langages flot de données qui sont souvent trop statiques pourraient répondre aux besoins des applications embarquées émergentes, qui nécessitent une exécution plus dynamique et plus dépendante du contexte ? Pour faire face au premier défi, nous proposons un ordonnancement hybride, nommé Self-Timed Periodic (STP), qui relie des MdC flot de données classiques et des modèles de tâches temps réel. Cet ordonnancement peut aussi être considéré comme un modèle d'exécution combinant l'ordonnancement classique dirigé seulement par les contraintes de dépendance d'exécution appelé Self-Timed Scheduling (STS), évalué comme le plus approprié pour des applications modélisées sous forme de graphes flot de données, avec l'ordonnancement périodique: STS améliore les indicateurs de performance des programmes, tandis que le modèle périodique capture les aspects de synchronisation. Nous avons évalué la performance de notre ordonnancement sur un ensemble de 10 applications et nous avons constaté que dans la plupart des cas, notre approche donne une amélioration significative de la latence par rapport à un ordonnancement purement périodique ou Strictly Periodic Scheduling (SPS), et rivalise bien avec STS. Les expériences montrent également que, pour presque tous les cas de test, STP donne un débit optimal. Sur la base de ces résultats, nous avons évalué la latence entre le temps d'initiation de tous les deux acteurs dépendants, et nous avons introduit une approche basée sur la latence pour le traitement des flux à tolérance de pannes modélisée comme un graphe Cyclo-Static Dataflow (CSDF), dans le but d'aborder des problèmes de défaillance de nœud ou de réseau… / There is an increasing interest in developing applications on homo- and heterogeneous multiprocessor platforms due to their broad availability and the appearance of many-core chips, such as the MPPA-256 chip from Kalray (256 cores) or TEGRA X1 from NVIDIA (256 GPU and 8 64-bit CPU cores). Given the scale of these new massively parallel systems, programming languages based on the dataflow model of computation have strong assets in the race for productivity and scalability, meeting the requirements in terms of parallelism, functional determinism, temporal and spatial data reuse in these systems. However, new complex signal and media processing applications often display several major challenges that do not fit the classical static restrictions: 1) How to provide guaranteed services against unavoidable interferences which can affect real-time performance?, and 2) How these streaming languages which are often too static could meet the needs of emerging embedded applications, such as context- and data-dependent dynamic adaptation? To tackle the first challenge, we propose and evaluate an analytical scheduling framework that bridges classical dataflow MoCs and real-time task models. In this framework, we introduce a new scheduling policy noted Self-Timed Periodic (STP), which is an execution model combining Self-Timed scheduling (STS), considered as the most appropriate for streaming applications modeled as data-flow graphs, with periodic scheduling: STS improves the performance metrics of the programs, while the periodic model captures the timing aspects. We evaluate the performance of our scheduling policy for a set of 10 real-life streaming applications and find that in most of the cases, our approach gives a significant improvement in latency compared to the Strictly Periodic Schedule (SPS), and competes well with STS. The experiments also show that, for more than 90% of the benchmarks, STP scheduling results in optimal throughput. Based on these results, we evaluate the latency between initiation times of any two dependent actors, and we introduce a latency-based approach for fault-tolerant stream processing modeled as a Cyclo-Static Dataflow (CSDF) graph, addressing the problem of node or network failures. For the second challenge, we introduce a new dynamic Model of Computation (MoC), called Transaction Parameterized Dataflow (TPDF), extending CSDF with parametric rates and a new type of control actor, channel and port to express dynamic changes of the graph topology and time-triggered semantics. TPDF is designed to be statically analyzable regarding the essential deadlock and boundedness properties, while avoiding the aforementioned restrictions of decidable dataflow models. Moreover, we demonstrate that TPDF can be used to accurately model task timing requirements in a great variety of situations and introduce a static scheduling heuristic to map TPDF to massively parallel embedded platforms. We validate the model and associated methods using a set of realistic applications and random graphs, demonstrating significant buffer size and performance improvements (e.g., throughput) compared to state of the art models including Cyclo-Static Dataflow (CSDF) and Scenario-Aware Dataflow (SADF).

Cette thèse porte sur l’optimisation d’opérations dans un terminal maritime pétrolier en vue d’assister les opérateurs de supervision. L’objectif est de fournir des solutions candidates pour la sélection d’alignements (chemins) de pipelines et pour l’ordonnancement d’opérations de transfert de pétrole et de maintenance de vannes. La principale difficulté de ce travail est la gestion d’un réseau à ressources limitées et conflictuelles. La prise de décision doit être réalisée en fonction des disponibilités des dispositifs, de la capacité opérative du réseau, d’aspects financiers (pénalités) liés au service, et d’activités de maintenance planifiées au préalable. L’optimisation est abordée par des approches tropicales du fait que ces techniques appréhendent de manière concise et intuitive les phénomènes de synchronisation. Les propositions développées ici commencent par des modèles d’optimisation algébriques mono-objectif et se complexifient, lors de l’intégration de nouvelles variabilités, jusqu’à la proposition de modèles d’optimisation multi-objectif hybrides par approches d’intelligence artificielle et algébriques. Dans un premier temps, un modèle d’optimisation mono-objectif non linéaire est proposé en algèbre (max,+) pour minimiser les pénalités, intégrant des phénomènes de nature différente dans une contrainte générique unique. Dans un deuxième temps, la linéarisation est résolue par une priorisation des opérations en conflit. Dans ce contexte, deux critères de linéarisation sont considérés : le premier concernant les pénalités potentielles pour les clients, et le deuxième concernant la criticité des opérations. Le modèle (max,+) non linéaire minimisant les pénalités est étendu pour la prise en compte de la recherche d’alignements et de la minimisation des retards des opérations de maintenance. Pour appréhender la dimension multi-objectif, une approche hybride d’algorithmes génétiques et des systèmes (max,+) linéaires est ensuite discutée. Enfin, dans un cadre plus formel, un nouveau produit synchrone exploitant les phénomènes de parallélisme au plus tôt est défini pour des automates tropicaux pour minimiser le makespan. Les propositions sont validées par des données industrielles recueillies auprès de l’entreprise pétrolière PDVSA et du fournisseur de solutions de supervision Thales Group. Les principales contributions à la recherche relèvent de la considération des approches tropicales dans la résolution de la problématique d’optimisation conduisant à des modèles concis et potentiellement linéaires, la proposition d’une approche hybride d’algorithmes génétiques et systèmes (max,+) linéaires exploitant les avantages de recherche distribuée des approches de l’intelligence artificielle avec les modèles concis issus de l’algèbre (max,+), et de la définition d’un nouveau produit synchrone d’automates tropicaux par une exploitation des phénomènes de parallélisme pour un comportement au plus tôt. / This thesis addresses operations optimization in an oil seaport with the fundamental purpose of assisting supervision operators. The objective is to provide candidate solutions for pipeline alignment (path) selection and for scheduling of oil transfer operations, as well as maintenance operations, considering that the system has limited and conflicting resources. Informed decision making should consider operations scheduling and alignment selection based on : devices availability, operative capacity of the network, financial aspects (penalties) due to late service, and a predefined maintenance schedule. The optimization problem is addressed by tropical approaches given their potential for yielding concise and intuitive representations when modeling synchronization phenomena. The proposals developed herein start by algebraic mono-objective optimization models. They subsequently become more complex, as new aspects are included, leading to the formulation of hybrid multi-objective optimization models based on artificial intelligence approaches as well as (max,+)-linear system theory. Firstly, a mono-objective optimization model is proposed in (max,+) algebra for penalty minimization. This model integrates different nature phenomena into one single constraint. It is nonlinear, considers predefined alignments for transfer operations and is validated through an optimization solver (LINGO). Secondly, linearization of such model is introduced for prioritization of conflicting operations. Within this context, 2 criteria are addressed: potential penalties for clients and, on the other hand, operations criticality. The nonlinear (max,+) model minimizing penalties is extended in order to consider alignment search and delay minimization for maintenance operations. In order to address the multi-objective nature of the problem, an approach based on genetic algorithms and (max,+)-linear system theory is proposed. Finally, in a more formal framework, a new synchronous product for tropical automata exploiting parallelism phenomena at the earliest is defined in order to minimize the makespan. The proposed models and methods herein have been validated by industrial data gathered from the oil company PDVSA and from the supervision solutions provider Thales Group. The main contributions of this research are, firstly, the application of tropical approaches to this specific optimization problem, yielding concise and potentially linear models. Secondly, the proposal of a hybrid approach based on genetic algorithms and (max,+)-linear systems, which exploits the advantages of the distributed search of artificial intelligence approaches and the conciseness of the models stemming from (max,+) algebra. The final contribution focuses on the definition of the alphabet for a new synchronous product of tropical automata.

Les architectures multi-cœurs utilisant des mémoire bloc-notes sont des architectures attrayantes pour l'exécution des applications embarquées temps-réel, car elles offrent une grande capacité de calcul. Cependant, les systèmes temps-réel nécessitent de satisfaire des contraintes temporelles, ce qui peut être compliqué sur ce type d'architectures à cause notamment des ressources matérielles physiquement partagées entre les cœurs. Plus précisément, les scénarios de pire cas de partage du bus de communication entre les cœurs et la mémoire externe sont trop pessimistes. Cette thèse propose des stratégies pour réduire ce pessimisme lors de l'ordonnancement d'applications sur des architectures multi-cœurs. Tout d'abord, la précision du pire cas des coûts de communication est accrue grâce aux informations disponibles sur l'application et l'état de l'ordonnancement en cours. Ensuite, les capacités de parallélisation du matériel sont exploitées afin de superposer les calculs et les communications. De plus, les possibilités de superposition sont accrues par le morcellement de ces communications. / Multi-core architectures using scratch pad memories are very attractive to execute embedded time-critical applications, because they offer a large computational power. However, ensuring that timing constraints are met on such platforms is challenging, because some hardware resources are shared between cores. When targeting the bus connecting cores and external memory, worst-case sharing scenarios are too pessimistic. This thesis propose strategies to reduce this pessimism. These strategies offer to both improve the accuracy of worst-case communication costs, and to exploit hardware parallel capacities by overlapping computations and communications. Moreover, fragmenting the latter allow to increase overlapping possibilities.

De plus en plus d'ordinateurs utilisent des architectures hybrides combinant des processeurs multi-cœurs (CPUs) et des accélérateurs matériels comme les GPUs (Graphics Processing Units). Ces plates-formes parallèles hybrides exigent de nouvelles stratégies d'ordonnancement adaptées. Cette thèse est consacrée à une caractérisation de ce nouveau type de problèmes d'ordonnancement. L'objectif le plus étudié dans ce travail est la minimisation du makespan, qui est un problème crucial pour atteindre le potentiel des nouvelles plates-formes en Calcul Haute Performance.Le problème central étudié dans ce travail est le problème d'ordonnancement efficace de n tâches séquentielles indépendantes sur une plateforme de m CPUs et k GPUs, où chaque tâche peut être exécutée soit sur un CPU ou sur un GPU, avec un makespan minimal. Ce problème est NP-difficiles, nous proposons donc des algorithmes d'approximation avec des garanties de performance allant de 2 à (2q + 1)/(2q) +1/(2qk), q> 0, et des complexités polynomiales. Il s'agit des premiers algorithmes génériques pour la planification sur des machines hybrides avec une garantie de performance et une fin pratique. Des variantes du problème central ont été étudiées : un cas particulier où toutes les tâches sont accélérées quand elles sont affectées à un GPU, avec un algorithme avec un ratio de 3/2, un cas où les préemptions sont autorisées sur CPU, mais pas sur GPU, le modèle des tâches malléables, avec un algorithme avec un ratio de 3/2. Enfin, le problème avec des tâches dépendantes a été étudié, avec un algorithme avec un ratio de 6. Certains des algorithmes ont été intégré dans l'ordonnanceur du système xKaapi. / More and more computers use hybrid architectures combining multi-core processors (CPUs) and hardware accelerators like GPUs (Graphics Processing Units). These hybrid parallel platforms require new scheduling strategies. This work is devoted to a characterization of this new type of scheduling problems. The most studied objective in this work is the minimization of the makespan, which is a crucial problem for reaching the potential of new platforms in High Performance Computing. The core problem studied in this work is scheduling efficiently n independent sequential tasks with m CPUs and k GPUs, where each task of the application can be processed either on a CPU or on a GPU, with minimum makespan. This problem is NP-hard, therefore we propose approximation algorithms with performance ratios ranging from 2 to (2q+1)/(2q)+1/(2qk), q>0, and corresponding polynomial time complexities. The proposed solving method is the first general purpose algorithm for scheduling on hybrid machines with a theoretical performance guarantee that can be used for practical purposes. Some variants of the core problem are studied: a special case where all the tasks are accelerated when assigned to a GPU, with a 3/2-approximation algorithm, a case where preemptions are allowed on CPUs, the same problem with malleable tasks, with an algorithm with a ratio of 3/2. Finally, we studied the problem with dependent tasks, providing a 6-approximation algorithm. Experiments based on realistic benchmarks have been conducted. Some algorithms have been integrated into the scheduler of the xKaapi runtime system for linear algebra kernels, and compared to the state-of-the-art algorithm HEFT.