Dans cette thèse, nous avons traité les problèmes d'ordonnancement d'ateliers de type flowshop hybride à deux étages avec machines à traitement par batches sur le second étage et compatibilité entre les tâches.Les durées opératoires des tâches sont données par des intervalles, et les tâches sont dites compatibles si elles partagent une même durée d'exécution. Pour le problème de minimisation de la date de fin d'ordonnancement de ce type d'atelier, nous avons développé 6 heuristiques à performances garanties. D'après les expériences réalisées, ces heuristiques sont efficaces sur de grandes instances. Pour les petites instances, nous avons présenté deux méthodes exactes de type procédures par séparation évaluation qui permettent de résoudre des instances de 20 tâches. Nous avons également développé un schéma d'approximation polynomial (PTAS) utilisable lorsque les durées d'exécution sur le premier étage sont identiques. En complément de ces travaux, nous avons également étudié d’autres problèmes de minimisation de critères réguliers sur une machine à traitement par batches. Nous avons développé des algorithmes de programmation dynamiques pseudo-polynomiaux pour les problèmes de minimisation de la somme des dates de fin d'exécution et pour les problèmes avec dates de fin souhaitées. Afin de compléter ces résultats de complexité, nous avons montré la NP-complétude des problèmes avec dates de fin souhaitées / This thesis deals with 2-stages hybrid flowshop scheduling problems with batching machines on the second stage and compatibility constraints. The processing times of tasks are given by intervals and tasks are compatible if they share a same second stage processing time. We developped 6 heuristics with worth-case analysis for the makespan minimization problem. The experimental results show that these heuristics give good schedules with an average gap of 1\% on 200 task instances. For small instances, we presented 2 exact methods, Branch \& Bounds, which solves up to 20 task instances. For the particular case with identical processing times on first stage and uniform processing time intervals we developped a Polynomial Time Approximation Scheme (PTAS). The second part of this thesis deal with scheduling problems on one batching machine with infinite capacity and regular criteria minimization. We developped pseudo-polynomial dynamic programming algorithm for minimization total completion time, maximal lateness and total tardiness. Finally we show the NP-completeness of problems with due dates

Nous proposons de développer des outils d’aide à la décision pour l’ordonnancement de chaînes logistiques. Nous privilégions la coopération entre les différents acteurs de la chaîne notamment la négociation avec les fournisseurs sur les dates d’arrivée des composants, et avec les clients sur les dates de livraisons des produits finis. Nous considérons une chaîne logistique qui consiste en un réseau d’entreprises avec des centres de décisions indépendants. Les produits finis ou semi finis des entreprises d’assemblage sont fabriqués en utilisant des composants ou produits semi finis fournis par les autres entreprises du réseau ou par des fournisseurs externes. On est au niveau opérationnel, chaque entreprise construit son ordonnancement par rapport à ses propres centres de production. Comme la production de produits finis dépend des composants, des négociations sont entamées entre les entreprises concernant les dates d’arrivées des composants (les fenêtres de temps). Une solution globale est obtenue par une approche itérative par décomposition incluant des négociations bilatérales entre les centres de production et de décisions pour définir l’ordonnancement juste à temps minimisant la somme des pénalités. Pour résoudre l’ordonnancement juste à temps local de chaque centre de production nous proposons une méthode approchée basée sur les algorithmes génétiques. Chaque solution est évaluée grâce à un algorithme polynomial basé sur le PERT coût. Un contrôle semi décentralisé est envisagé pour assurer la convergence des négociations. Par ailleurs, nous étudions un ensemble de problèmes concernant l’optimisation des transports dans les chaînes logistiques / We propose new decision methods for coordinating supply chain scheduling. We focus on the cooperation between supply chain partners by means of negotiations about suppliers’ raw materials arrival dates, and customers’ delivery dates of finished. We consider a supply chain, which consists in a network of independant enterprises. The finished products (or sub products) of the assembly enterprise are produced using components and/or sub products supplied by other enterprises or by external suppliers. We are at the scheduling level and each enterprise builds its own schedules associated with its production centers. As an operation can be performed only when the production center has received the necessary components, the schedules are dependent. This induces negotiations between decision centers which is expressed by penalty functions associated with soft and hard release dates and due dates. A global solution is searched by an iterative decomposition approach including alternatively bilateral negotiations between the production decision centers and just in time scheduling, minimizing the local total sum of penalties. To solve each local just-in-time scheduling problem, we propose an approximation approach based on meta-heuristics, which explores the set of solutions, in which a solution is described by the job order on each machine and is evaluated using a “pert cost” algorithm.. A semi-decentralized control is suggested to assume the negotiation convergence. Furthermore, we study some transportation optimization problems in supply chains

La réalisation d'une mission robotique se décompose usuellement en trois étapes: la planification, i.e. le choix des taches à réaliser, le séquencement, i.e. la détermination du timing et de l'ordre de réalisation des tâches, et finalement l'exécution du plan de tâches. Pour les systèmes redondants tels que les robots humanoïdes, la tâche (dans le sens de fonction de tâche) détermine une commande sur une partie du robot, permettant ainsi la réalisation simultanée de plusieurs tâches à l'aide d'un formalisme de pile de tâches. Cependant, les mécanismes d'ordonnancement classiques ne gèrent pas les cas où le mouvement est déterminé par un ensemble de tâches hiérarchisé: pour ces robots, la phase d'ordonnancement est éludée et l'exécution se base directement sur la plan de tâches donné par le planificateur. Le but de cette thèse est de réintroduire cette phase d'ordonnancement, tout en maintenant le rôle central de la tâche. Dans un premier temps, la continuité de la commande fournie par la pile de tâches est étudiée. En particulier, nous mettons en évidence les discontinuités accompagnant la réalisation d'événements discrets (à savoir l'insertion, le retrait et l'échange de priorité de tâches), puis proposons et comparons plusieurs méthodes de lissage. Ensuite, nous présentons une méthode permettant d'optimiser une séquence de tâches donnée en modifiant le timing et la paramétrisation des tâches, tout en respectant les contraintes liées à l'environnement. Enfin, une nouvelle utilisation de la flexibilité de la fonction de tâche consistant à adapter une séquence de tâches aux préférences d'un utilisateur humain est illustrée. Ces résultats sont illustrés sur un robot humanoïde. / A general agreed approach on mission and motion planning consists in splitting it into three steps: decomposing the mission into a sequence of tasks (task planning), determining the order of realization and the timing of the tasks (task scheduling) and finally executing the task sequence. This approach maintains the task component in the entire reasoning, using it as a bridge between planning, scheduling and execution.In the sense of task function, a task defines a control law on part of the robot. Hence, for highly redundant systems such as humanoid robots, it is possible to realize several tasks simultaneously using a stack-of-tasks formalism. Though, classical schedulers do not handle the case where the motion is specified not by one, but by a combination of tasks organized into a hierarchy. As a result, the scheduling phase is usually skipped. This thesis aims at reintroducing the scheduling phase, while maintaining the central role of the task.First, the stack-of-tasks formalism is recalled and the continuity of the control law is studied. Particularly, we show that discreet operations (insertion, removal and swap of priority between tasks) create discontinuities in the control. We then present and discuss smoothing methods. Second, we present a task-overlapping based method to optimize not only the scheduling but also the behavior of the tasks of a given sequence, while accounting for the physical constraint of the execution. Finally, we introduce a new perspective in the usage of the task-function approach the task function approach to personalize a task sequence and take into account user preferences.These results are experimented on the humanoid robot platform HRP-2.

Les travaux présentés dans cette thèse portent sur l’ordonnancement d’applications multi-tâches linéaires de type workflow sur des plateformes distribuées. La particularité du système étudié est que le nombre de machines composant la plateforme est plus petit que le nombre de tâches à effectuer. Dans ce cas les machines sont supposées être capables d’effectuer toutes les tâches de l’application moyennant une reconfiguration, sachant que toute reconfiguration demande un temps donné dépendant ou non des tâches. Le problème posé est de maximiser le débit de l’application,c’est à dire le nombre moyen de sorties par unité de temps, ou de minimiser la période, c’est à dire le temps moyen entre deux sorties. Par conséquent le problème se décompose en deux sous problèmes: l’assignation des tâches sur les machines de la plateforme (une ou plusieurs tâches par machine), et l’ordonnancement de ces tâches au sein d’une même machine étant donné les temps de reconfiguration. Pour ce faire la plateforme dispose d’espaces appelés buffers, allouables ou imposés, pour stocker des résultats de production temporaires et ainsi éviter d’avoir à reconfigurer les machines après chaque tâche. Si les buffers ne sont pas pré-affectés nous devons également résoudre le problème de l’allocation de l’espace disponible en buffers afin d’optimiser l’exécution de l’ordonnancement au sein de chaque machine. Ce document est une étude exhaustive des différents problèmes associés à l’hétérogénéité de l’application ; en effet si la résolution des problèmes est triviale avec des temps de reconfiguration et des buffers homogènes, elle devient bien plus complexe si ceux-ci sont hétérogènes. Nous proposons ainsi d’étudier nos trois problèmes majeurs pour différents degrés d’hétérogénéité de l’application. Nous proposons des heuristiques pour traiter ces problèmes lorsqu’il n’est pas possible de trouver une solution algorithmique optimale. / In this document we tackle scheduling problems of multitask linear workflow applications ondistributed platforms. In our particular problem the number of available machines on the platformis lower than the number of stages within the pipeline. The machines are then assumed to be able toperform any kind of task on the application given the appropriate reconfiguration (or setup), the catchbeing that any reconfiguration is time consuming. The problem that we try to solve is to maximizethe throughput of such applications, i.e., the mean amount of outputs per unit of time, or to minimizeits period, i.e., the average time between two outputs. As a result this problem is split into two subproblems:mapping tasks onto different machines of the platform (most machines will likely handleseveral tasks), and find an optimal schedule within a machine while taking setup times into account.To solve this we introduce buffers, which are spaces available for each machine to store temporaryproduction results and avoid reconfiguring after each task execution, and which may or may notbe already allocated for each stage. If those buffers are not already allocated to each task then athird problem must be solved to properly allocate the available space onto each buffer, as differentbuffer configurations have a huge impact on the scheduling of a machine. This document presentsan exhaustive coverage of the different problems that are associated with the heterogeneity of theapplication; the problems with homogeneous buffer capacities and setup times are rather simple tosolve, but they get a lot more complex as heterogeneity increases. We study the three main subproblemsfor each heterogeneity combination, and offer heuristic solution to solve them when anoptimal solution cannot be reasonably found.

L'ordonnancement de tâches sur un système temps réel dur correspond à trouver une façon de choisir, à chaque instant, quelle tâche doit être exécutée sur le processeur pour que chacune ait le temps de terminer son travail avant son échéance. Ce problème, dans le contexte monoprocesseur, est déjà bien étudié et permet des applications sur des systèmes en production (aérospatiale, bourse etc.). Aujourd'hui, les plateformes multiprocesseur se sont généralisées et ont amené de nombreuses questions telles que l'utilisation efficace de tous les processeurs. Dans cette thèse, nous explorons les approches existantes pour résoudre ce problème. Nous étudions tout d'abord l'approche par partitionnement qui consiste à utiliser les recherches existantes en ramenant ce problème à plusieurs systèmes monoprocesseur. Ici, nous proposons un algorithme générique dont les paramètres sont adaptables en fonction de l'objectif à atteindre. Nous étudions ensuite l'approche par semi-partitionnement qui permet la migration d'un nombre restreint de tâches. Nous proposons une solution avec des migrations restreintes qui pourrait être assez simplement implémentée sur des systèmes concrets. Nous proposons ensuite une solution avec des migrations non restreintes qui offre de meilleurs résultats mais est plus difficile à implémenter. Enfin, les programmeurs utilisent de plus en plus le concept de tâches parallèles qui peuvent utiliser plusieurs processeurs en même temps. Ces tâches sont encore peu étudiées et nous proposons donc un nouveau modèle pour les représenter. Nous étudions les ordonnanceurs possibles et nous définissons une façon de garantir l'ordonnançabilité de ces tâches pour deux d'entre eux / The scheduling of tasks on a hard real-time system consists in finding a way to choose, at each time instant, which task should be executed on the processor so that each succeed to complete its work before its deadline. In the uniprocessor case, this problem is already well studied and enables us to do practical applications on real systems (aerospace, stock exchange etc.). Today, multiprocessor platforms are widespread and led to many issues such as the effective use of all processors. In this thesis, we explore the existing approaches to solve this problem. We first study the partitioning approach that reduces this problem to several uniprocessor systems and leverage existing research. For this one, we propose a generic partitioning algorithm whose parameters can be adapted according to different goals. We then study the semi-partitioning approach that allows migrations for a limited number of tasks. We propose a solution with restricted migration that could be implemented rather simply on real systems. We then propose a solution with unrestricted migration which provides better results but is more difficult to implement. Finally, programmers use more and more the concept of parallel tasks that can use multiple processors simultaneously. These tasks are still little studied and we propose a new model to represent them. We study the possible schedulers and define a way to ensure the schedulability of such tasks for two of them

Cette thèse présente nos travaux de recherche qui ont comme principal objectif d'assurer la portabilité des performances et le passage à l'échelle des applications scientifiques complexes exécutées sur des plates-formes multi-coeurs parallèles et hiérarchiques. La portabilité des performances est obtenue lorsque l'ordonnancement des tâches d'une application permet de réduire les périodes d'inactivité des coeurs de la plate-forme. Cette portabilité des performances peut être affectée par différents problèmes tels que des déséquilibres de charge, des communications coûteuses et des surcoûts provenant de l'ordonnancement des tâches. Le déséquilibre de charge est la conséquence de comportements de charges irrégulières et dynamiques, où le volume de calcul varie dynamiquement en fonction de la tâche et de l'étape de simulation. Les communications coûteuses sont provoquées par un ordonnancement qui ne prend pas en compte les différents temps de communication entre tâches sur une plate-forme hiérarchique. Cela est accentué par des communications non uniformes et asymétriques au niveau mémoire et réseau. Enfin, ces surcoûts peuvent être générés par des algorithmes de placement trop complexes dont les coûts ne seraient pas compensés par les gains de performance.Pour atteindre cet objectif de portabilité des performances, notre approche repose sur une récolte d'informations précises sur la topologie de la machine qui vont aider les algorithmes d'ordonnancement de tâches à prendre les bonnes décisions. Dans ce contexte, nous avons proposé une modélisation générique de la topologie des plates-formes parallèles. Le modèle comprend des latences et des bandes passantes mesurées de la mémoire et du réseau qui mettent en évidence des asymétries. Ces informations sont utilisées par nos trois algorithmes d'équilibrage de charge nommés NucoLB, HwTopoLB, et HierarchicalLB. De plus, ces algorithmes utilisent des informations provenant de l'exécution de l'application. NucoLB se concentre sur les aspects non uniformes de plates-formes parallèles, alors que HwTopoLB considère l'ensemble de la hiérarchie pour ses décisions, et HierarchicalLB combine ces algorithmes hiérarchiquement pour réduire son surcoût d'ordonnancement de tâches. Ces algorithmes cherchent à atténuer le déséquilibre de charge et des communications coûteuses tout en limitant les surcoûts de migration des tâches.Les résultats expérimentaux avec les trois régulateurs de charge proposés ont montré des améliorations de performances sur les meilleurs algorithmes de l'état de l'art: NucoLB a présenté jusqu'à 19% d'amélioration de performances sur un noeud de calcul; HwTopoLB a amélioré les performances en moyenne de 19%, et HierarchicalLB a surclassé HwTopoLB de 22% en moyenne sur des plates-formes avec plus de dix noeuds de calcul. Ces résultats ont été obtenus en répartissant la charge entre les ressources disponibles, en réduisant les coûts de communication des applications, et en gardant les surcoûts d'équilibrage de charge faibles. En ce sens, nos algorithmes d'équilibrage de charge permettent la portabilité des performances pour les applications scientifiques tout en étant indépendant de l'application et de l'architecture du système. / This thesis presents our research to provide performance portability and scalability to complex scientific applications running over hierarchical multicore parallel platforms. Performance portability is said to be attained when a low core idleness is achieved while mapping a given application to different platforms, and can be affected by performance problems such as load imbalance and costly communications, and overheads coming from the task mapping algorithm. Load imbalance is a result of irregular and dynamic load behaviors, where the amount of work to be processed varies depending on the task and the step of the simulation. Meanwhile, costly communications are caused by a task distribution that does not take into account the different communication times present in a hierarchical platform. This includes nonuniform and asymmetric communication costs at memory and network levels. Lastly, task mapping overheads come from the execution time of the task mapping algorithm trying to mitigate load imbalance and costly communications, and from the migration of tasks.Our approach to achieve the goal of performance portability is based on the hypothesis that precise machine topology information can help task mapping algorithms in their decisions. In this context, we proposed a generic machine topology model of parallel platforms composed of one or more multicore compute nodes. It includes profiled latencies and bandwidths at memory and network levels, and highlights asymmetries and nonuniformity at both levels. This information is employed by our three proposed topology-aware load balancing algorithms, named NucoLB, HwTopoLB, and HierarchicalLB. Besides topology information, these algorithms also employ application information gathered during runtime. NucoLB focuses on the nonuniform aspects of parallel platforms, while HwTopoLB considers the whole hierarchy in its decisions, and HierarchicalLB combines these algorithms hierarchically to reduce its task mapping overhead. These algorithms seek to mitigate load imbalance and costly communications while averting task migration overheads.Experimental results with the proposed load balancers over different platform composed of one or more multicore compute nodes showed performance improvements over state of the art load balancing algorithms: NucoLB presented improvements of up to 19% on one compute node; HwTopoLB experienced performance improvements of 19% on average; and HierarchicalLB outperformed HwTopoLB by 22% on average on parallel platforms with ten or more compute nodes. These results were achieved by equalizing work among the available resources, reducing the communication costs experienced by applications, and by keeping load balancing overheads low. In this sense, our load balancing algorithms provide performance portability to scientific applications while being independent from application and system architecture.

L'objectif de cette thèse est de fournir des outils d'aide à la décision pour piloter les plateformes logistiques à court de moyen terme. La première partie décrit la problématique concernée et les notions essentielles dans le cadre des chaînes logistiques. Dans la deuxième partie, le problème de la planification est étudié, nous proposons des modèles linéaires pour minimiser les coûts de personnel, qui prennent en compte les flux : leurs variations saisonnières, la possibilité de les négocier localement en amont et en aval, ainsi que leur organisation et celle du travail. Ainsi, l'outil peut être utilisé dans la coordination des flux entres les partenaires de la chaîne livrées en amont et en aval de la plateforme et la négociation des dates de livraison. Ces modèles sont testés et validés sur des instances générées aléatoirement, sur des configurations inspirées de problèmes réels. Dans la troisième partie, nous travaillons sur l'ordonnancement des activités de préparation de commandes. Ici, nous combinons deux familles de contraintes difficiles : l'arrivée de composants (ressources consommables) à des dates et en quantités connues à l'amont de la plateforme, et des tournées de livraison à dates fixées à l'aval. Trois cas particuliers sont étudiés, selon la façon dont les tournées sont organisées. Nous proposons des procédures par séparation et évaluation pour ces problèmes, et un modèle linéaire en nombres entiers pour le cas le plus simple. Des expériences sont faites sur des familles d'instances générées aléatoirement et de manière partiellement hétérogène. Plusieurs perspectives de généralisation sont proposées / The aim of this thesis is to provide decision support systems to control logistic platforms at the mid-term and short-term levels. Several problems and main notions concerning logistic platform context are described in the first part. In the second part, planning problems are studied. Two linear programming models are proposed to minimize the workforce costs. These models take into account several characteristics : seasonal flow variations, work and flow organization in the platform, and local negotiations of the upstream and downstream flows. In consequence, our decision support system can be used in the flow coordination between supply chain partners. Two types of negotiations are considered : negotiations of upstream and downstream delivered quantities and negotiation of delivery dates. These models have been tested on pertinent randomly generated instances inspired from concerete problems. In the third part of the thesis, the external flows of the platforme are assumed to be fixed. Orders preparation scheduling problem inside the platform is considered. Two families of strong contraints are combined : staircase availability of components (consumable resources) and dixed delivery dates. According to the way the downstream deliveries are organized and penalised, three different cases (based on industrial applications) have been studied. We proposed three branch and bound procedures for these problems, and an integer linear program for the easiest problem. Experimental analysis has been done over heterogeneous randomly generated instance families. In the last part, a series of perspectives for this work are proposed

Le cloud computing est l’accomplissement du rêve de nombreux informaticiens désireux de transformer et d’utiliser leurs logiciels comme de simples services, rendant ces derniers plus attractifs et séduisants pour les utilisateurs. Dans le cadre de cette thèse, les technologies du cloud computing sont présentées, ainsi que les principaux défis que ce dernier va rencontrer dans un futur proche, notamment pour la gestion et l’analyse des données. A partir de la théorie moderne d'ordonnancements des tâches, nous avons proposé une gestion hiérarchique d’ordonnancements des tâches qui satisfait aux différentes demandes des cloud services. D’un point de vue théorique, nous avons principalement répondu à trois questions cruciales de recherche. Premièrement, nous avons résolu le problème de l'allocation des ressources au niveau de l’utilisateur. Nous avons en particulier proposé des algorithmes basés sur la théorie des jeux. Avec une méthode Bayésienne d’apprentissage, l'allocation des ressources atteint l'équilibre de Nash parmi les utilisateurs en compétition malgré une connaissance insuffisante des comportements de ces derniers. Deuxièmement, nous avons abordé le problème d'ordonnancements des tâches au niveau du système. Nous avons trouvé un nouveau seuil pour l'utilisation d’ordonnancements des tâches en ligne, considérant le dispositif séquentiel de MapReduce. Ce seuil donne de meilleurs résultats que les méthodes existantes dans l’industrie. Troisièmement, nous avons défini un critère de comparaison pour les tests d’ordonnancements de tâches en ligne. Nous avons proposé un concept de fiabilité d'essai pour évaluer la probabilité qu'un ensemble de tâches aléatoires passe un essai donné. Plus la probabilité est grande, plus la fiabilité est élevée. Un test présentant une grande fiabilité garantit une bonne utilisation du système. D’un point de vue pratique, nous avons développé un simulateur basé sur le concept de MapReduce. Ce simulateur offre un environnement directement utilisable par les chercheurs familiers avec SimMapReduce, leur permettant de s’affranchir des aspects informatiques d’implémentations et leur permettant notamment de se concentrer sur les aspects algorithmiques d’un point de vue théorique. / Cloud computing, the long-held dream of computing as a utility, has the potential to transform a large part of the IT industry, making software even more attractive as a service and shaping the way in which hardware is designed and purchased. In this thesis, we reviewed the new cloud computing technologies, and indicated the main challenges for their development in future, among which resource management problem stands out and attracts our attention. Combining the current scheduling theories, we proposed cloud scheduling hierarchy to deal with different requirements of cloud services. From the theoretical aspects, we have accomplished three main research issues. Firstly, we solved the resource allocation problem in the user-level of cloud scheduling. We proposed game theoretical algorithms for user bidding and auctioneer pricing. With Bayesian learning prediction, resource allocation can reach Nash equilibrium among non-cooperative users even though common knowledge is insufficient. Secondly, we addressed the task scheduling problem in the system-level of cloud scheduling. We proved a new utilization bound for on-line schedulability test, considering the sequential feature of MapReduce. We deduced the relationship between cluster utilization bound and the ratio of Map to Reduce. This new schedulable bound with segmentation uplifts classic bound which is most used in industry. Thirdly, we settled the comparison problem among on-line schedulability tests in cloud computing. We proposed a concept of test reliability to evaluate the probability that a random task set could pass a given schedulability test. The larger the probability is, the more reliable the test is. From the aspect of system, a test with high reliability can guarantee high system utilization. From the practical aspects, we have developed a simulator to model MapReduce framework. This simulator offers a simulated environment directly used by MapReduce theoretical researchers. The users of SimMapReduce only concentrate on specific research issues without getting concerned about finer implementation details for diverse service models, so that they can accelerate study progress of new cloud technologies.

Les satellites d’observation de la Terre sont des senseurs qui acquièrent des données, les compressent et les mémorisent à bord, puis les vident vers le sol. Des incertitudes rendent la planification des activités au sol de plus en plus discutable car la planification est alors pessimiste et les plans largement sous-optimaux. Cette thèse détaille la conception d'une planification mixte qui permet de profiter de la réalisation des paramètres incertains à bord tout en préservant la prévisibilité de l'exécution pour les opérateurs au sol. Notre première contribution concerne le problème de planification des vidages. Un mécanisme de planification flexible a été conçu dans lequel seules les acquisitions de haute priorité sont planifiées de manière pessimiste. A bord, un algorithme adapte le plan en fonction des volumes réels, en s'assurant que le vidage des acquisitions de haute priorité est toujours garanti, et insère des nouveaux vidages si possible. Notre deuxième contribution concerne le problème de planification des acquisitions. Au sol, des contraintes contribuent à éliminer du plan de nombreuses acquisitions qui auraient pu être réalisées car les niveaux de ressources à bord sont souvent plus hauts que ceux prévus par ces contraintes. Dans un nouveau mécanisme de décision, le sol produit des plans conditionnels dans lesquels la réalisation des acquisitions de basse priorité est conditionnée par des niveaux d'énergie requis. Comparées à d'autres mécanismes de planification, ces deux approches flexibles permettent d'éviter le gaspillage des ressources et de réaliser plus d'acquisitions et de vidages tout en conservant de la prévisibilité. / Earth-observation satellites are space sensors which acquire data, compress and record it on board, and then download it to the ground. Some uncertainties make planning and scheduling satellite activities offline on the ground more and more arguable as worst-case assumptions are made about uncertain parameters and plans are suboptimal. This dissertation details our efforts at designing a flexible decision-making scheme that allows to profit from the realization of uncertain parameters on board while keeping a fair level of predictability on the ground. Our first contribution concerns the data download problem. A flexible decision-making mechanism has been designed where only high-priority acquisition downloads are scheduled with worst-case assumptions. Other acquisition downloads are scheduled with expected parameters and conditioned by resource availability. The plan is then adapted on board. Our second contribution concerns the acquisition planning problem. A lot of acquisitions that could have been done are eliminated when planning because of worst-case assumptions. In a new decision-making scheme, these high-level constraints are removed for low-priority acquisitions. Observation plans produced on the ground are conditional plans involving conditions for triggering low-priority acquisitions. Compared with pure ground and pure onboard methods, these two approaches avoid wastage of resource and allow more acquisitions to be executed and downloaded to the ground while keeping a fair level of predictability on the ground.

La réservation de ressources dans un réseau de communication est un domaine d'application très vaste, qui implique des problèmes algorithmiques nombreux et variés. La modélisation d'un réseau sous la forme d'un graphe permet, indépendamment de sa nature physique, de développer des algorithmes pour déterminer quels sont les noeuds et/ou les liens du réseau qui doivent être réservés. Il s'agit de gérer au mieux l'attribution de ces ressources pour les membres qui inter-agissent via le réseau. Pour la résolution de problèmes liés à la réservation de ressources au niveau d'un lien particulier, c'est la modélisation sous la forme d'un ordonnancement qui est alors particulièrement adaptée. Dans ce type de problèmes, il n'est pas toujours possible de connaître à l'avance toutes les données à traiter. En effet, les demandes de membres amenés à communiquer via le réseau ainsi que les demandes de réservation au niveau des liens arrivent en pratique au fils de l'eau. Pour prendre en compte cette difficulté, nous nous plaçons dans le contexte de l'algorithmique on-line (en ligne). Les données du problème à traiter ne sont donc pas connues dès le départ, mais révélées au fur et à mesure, sans aucune connaissance du futur. Pour chacun des problèmes on-lines traités, nous proposons des algorithmes que nous évaluons analytiquement, en fonction d'un (ou parfois plusieurs) critère(s) de performance.