La majeure partie des travaux sur les problèmes d'ordonnancement se placent dans le contexte où les ressources sont disponibles en permanence. Ce qui en réalité n'est pas toujours le cas. Nous nous plaçons dans le contexte d'indisponibilités connues ; nous nous intéressons plus particulièrement aux problèmes de type job shop avec des périodes d'indisponibilité flexibles et des tâches pouvant éventuellement être interrompues par les périodes d'indisponibilité. L'intégration de ces contraintes rend les problèmes d'ordonnancement nettement plus difficiles à résoudre. La flexibilité que nous considérons peut être relative à au moins l'un des points suivants : déplacement de la période d'indisponibilité dans une fenêtre de temps, modification de la durée de la période d'indisponibilité, interruption d'une tâche par une période d'indisponibilité, ensuite reprise avec une éventuelle pénalité.Dans cette thèse, nous avons proposé des modèles mathématiques pour le problème. En plus de la résolution des problèmes considérés, le but de ces modélisations est de permettre d'analyser l'impact des différentes contraintes et d'évaluer la qualité des méthodes approchées que nous proposons. Ces dernières permettent de construire très rapidement un ordonnancement en se basant sur des règles de priorité. Les solutions sont aussi utilisées pour notre approche basée sur la génération de colonnes. Cette approche s'adapte bien à différents fonctions objectif et permet d'intégrer relativement facilement plusieurs contraintes. De nombreuses expérimentations ont été menées pour valider les méthodes proposées.

Cette étude répond au problème d'ordonnancement temps réel de composants logiciels s'exécutant sur un processeur de traitement du signal dans un contexte de radio logicielle. Elle vise ainsi à compléter l'offre en termes d'outillage de conception radio logicielle. Dans la pratique actuelle, l'ordonnancement temps réel des applications de traitement du signal flexibles s'exécutant sur un processeur donné, est effectué de manière manuelle, en utilisant des méthodes empiriques, et en prenant des marges non négligeables. Etant donnée l'augmentation pressentie du nombre de composants logiciels de la couche physique s'exécutant simultanément sur un même processeur dans les futures radios logicielles, ces méthodes seront sujettes à erreur, feront perdre beaucoup de temps et ne trouveront pas nécessairement de solutions d'ordonnancement valides même lorsqu'il en existera une. Pour cela, cette thèse définit un nouveau modèle de tâche représentant plus précisément le comportement des tâches dans certains contextes de radio logicielle : le modèle GMF (Generalized Multi-Frame) non cyclique. Pour ce modèle, nous présentons une formulation du calcul du temps de réponse des tâches, ainsi qu'un nouveau test de faisabilité suffisant pour des tâches s'exécutant sur un processeur avec la politique d'ordonnancement " Earliest Deadline First " (EDF). Nous fournissons aussi pour ce modèle de tâche un algorithme efficace, permettant la détermination exacte de la faisabilité temps réel. Nous présentons dans cette thèse un nouveau flot de conception IDM (Ingénierie Dirigée par les Modèles), permettant de spécifier les paramètres rendant possibles une analyse d'ordonnançabilité temps réel des composants logiciels s'exécutant sur un processeur dans une radio logicielle. Cette thèse propose des méthodes pour calculer les contraintes temporelles dans une radio logicielle. Elle présente les éléments du standard MARTE à utiliser pour renseigner les contraintes dans le modèle ainsi que les règles de transformations de modèles qui permettent d'obtenir un modèle exploitable par un outil d'analyse d'ordonnançabilité temps réel. Cette thèse présente une approche, implantée sous forme d'un outil de simulation, effectuant l'analyse d'ordonnancement temps réel des tâches de traitement du signal flexibles s'exécutant sur un processeur suivant une politique d'ordonnancement hybride. Cet outil est intégré au flot IDM proposé.

Les travaux présentés dans cette thèse portent sur l'exécution d'applications sur les environ- nements hétérogènes et distribués que sont les grilles de calcul. Nous étudions de bout en bout le processus permettant à des utilisateurs d'exécuter des applications scientifiques complexes. Les contributions de cette thèse se situent donc à plusieurs niveaux. 1) Déploiement d'inter- giciel hiérarchique : nous proposons dans un premier temps un modèle d'exécution pour les intergiciels hiérarchiques. À partir de ce modèle, nous présentons plusieurs heuristiques pour définir automatiquement la meilleure hiérarchie en fonction des exigences des utilisateurs et du type de plate-forme. Nous évaluons la qualité de ces heuristiques en conditions réelles avec l'intergiciel Diet. 2) Partitionnement de graphe : nous proposons un algorithme distribué et auto-stabilisant pour partitionner un graphe quelconque ayant des arêtes pondérées entre les nœuds. Le partitionnement est réalisé en fonction des distances pondérées entre les nœuds et forme des grappes au sein desquelles les nœuds sont à une distance maximale k d'un nœud élu dans la grappe. 3) Ordonnancement : nous étudions l'ordonnancement de tâches indépen- dantes sous des contraintes de limitation d'utilisation des ressources. Nous définissons des formulations en programme linéaire pour résoudre ce problème dans deux cas : lorsque les tâches arrivent toutes en même temps et lorsqu'elles ont des dates d'arrivée. 4) Simulations cosmologiques : nous avons étudié le comportement d'applications nécessaires à l'exécution de workflows de simulations cosmologiques. Puis, en se basant sur l'intergiciel de grille Diet, nous avons mis en place une infrastructure complète permettant à des utilisateurs non expérimentés de soumettre facilement des simulations cosmologiques sur une grille de calcul.

Les marchés actuels sont caractérisés par une grande compétitivité. Cette compétitivité a mis les entreprises, notamment celles d'envergure internationale, dans une situation de recherche de compromis entre des objectifs et des contraintes de plus en plus forts et contradictoires. Cet environnement nous a conduit à développer un système de pilotage et de contrôle de production qui ne soit pas seulement capable de réagir efficacement mais qui soit également en évolution permanente pour améliorer ses performances et la qualité des solutions qu'il propose en terme d'ordonnancement. Ce système doit pouvoir exploiter au mieux les ressources de production. Pour ce faire, ces ressources subissent régulièrement des entretiens préventifs ou des corrections suite aux pannes, ce qui les rend indisponibles à ces moments. Les systèmes de pilotage de production doivent prendre en considération ces indisponibilités afin de mieux contrôler et commander le système de production. Par conséquent, production et maintenance doivent être gérées conjointement au sein du système de pilotage. Dans ce cadre, l'objectif de cette thèse est de proposer un système de pilotage qui soit réactif et capable d'améliorer en permanence ses performances. Dans cet objectif, un système basé sur l'approche multi-agent et l'apprentissage par renforcement multi-objectifs a été développé, ces techniques permettent au système d'être réactif et adaptatif à son environnement. Le système développé a été testé sur un cas réel qui est une unité de fabrication des huiles finies. Les expérimentations ont donné des résultats satisfaisants ouvrant la porte à de nouvelles perspectives.

Les Systèmes sur Puce (SoC) ont vu leurs capacités en constante augmentation ce qui leur permet ainsi qu'aux applications s'exécutant dessus de devenir de plus en plus complexes grâce au pouvoir d'intégration de la technologie. Beaucoup de ces appareils fonctionnent sur batterie, mais puisque la technologie des batteries ne suit pas la même progression que l'intégration, à la fois le logiciel et le matériel de ces appareils doivent être économes en énergie. Nous proposons dans cette thèse un algorithme logiciel qui cherche à réduire la consommation énergétique en modifiant la fréquence et la tension des processeurs lorsque l'utilisation du système le permet. Cet algorithme n'a besoin d'aucune information sur les applications. Afin de tester et de déterminer l'efficacité de l'algorithme d'économie d'énergie proposé, nous avons besoin de plateformes de simulation rapides et précises qui supportent le changement de fréquence pour chaque processeur ou sous-système. Le bon niveau d'abstraction pour estimer la consommation d'énergie par la simulation n'est pas évident. Nous avons premièrement défini une stratégie de haut niveau de simulation qui combine la précision des simulateurs orientés matériel à la vitesse des simulateurs orientés comportement. Lorsque des estimations plus précises sont nécessaires, une simulation cycle accurate/bit accurate doit être utilisée. Toutefois, pour accélérer la simulation, des stratégies d'ordonnancement statique non compatibles avec le DVFS sont utilisées. Nous avons défini deux nouvelles approches supportant le DVFS dans ce contexte.

Le management de la chaîne logistique concerne un large éventail d'activités. Nombreuses ceux qui ont un caractère incertain apportant souvent des conséquences inattendues. Malgré cela, l'incertitude est fréquemment non considérée dans la gestion de la chaîne logistique traditionnelle. En plus de l'incertitude, l'indisponibilité des ressources augmentera la complexité du problème. En prenons en compte les contraintes d'incertitude et de disponibilité nous étudions le management de la chaîne logistique selon différents aspects. Cette thèse représente une tentative de recherche afin d'aborder ce problème d'une façon systématique et complète et nous espérons que notre travail contribuera aux futurs travaux de recherche et sera utile aux gestionnaires de la chaîne logistique. Nous nous concentrons sur trois sources classiques de l'incertitude ; celle de la demande, celle la fabrication et celle liée à la distribution. Pour chaque source d'incertitude, nous analysons ses causes et ses impacts sur les performances de la chaîne logistique. L'incertitude est spécifiée dans des problèmes classiques concrets et des approches sont proposées pour les résoudre. Nous nous sommes également focalisés sur le problème bi-niveau de vendeur de journaux qui représente une chaîne logistique miniature, concerné par une double incertitude. Les méthodes utilisées offrent une bonne démonstration du traitement des variables incertaines dans les problèmes de décision.

Avec l'émergence des systèmes multicœurs, le concept de mémoire transactionnelle (TM) a été renouvelé à la fois dans le domaine de la recherche et dans le monde industriel. En effet, en supportant les propriétés ACI (Atomicité, Consistance et Isolation) des transactions, le concept de TM facilite la programmation parallèle et évite les problèmes liés aux verrous tels que les interblocages et l'inversion de priorité. De plus, contrairement aux méthodes basées sur les verrous, une TM permet à plusieurs transactions d'accéder en parallèle aux ressources, et augmente ainsi la bande passante du système. Enfin, une TM intègre un ordonnanceur de transactions qui, soit ré-exécute (retry) la transaction en cas de détection de conflits, soit valide (commit) la transaction en cas de succès. L'objectif de cette thèse est d'étudier l'adaptation des TMs à des systèmes temps réel soft au sein desquels les processus doivent s'exécuter le plus souvent possible dans le respect de contraintes temporelles. Jusqu'à maintenant, l'ordonnancement de transactions temps réel au sein d'une TM n'a pas été étudié. Dans un premier temps, nous proposons une étude expérimentale comparative nous permettant de statuer sur l'adéquation des TMs aux systèmes temps réel multicœurs. Il s'agit en particulier d'évaluer si la variabilité du temps d'exécution des transactions est prohibitif à une utilisation dans un contexte temps réel lors de l'accès aux ressources partagées. Dans un second temps, nous introduisons un modèle transactionnel temps réel pour les TMs et nous décrivons la conception et l'implémentation d'une mémoire transactionnelle logicielle temps réel nommée RT-STM. Celle-ci intègre de nouveaux protocoles de synchronisation qui permettent de prioriser les accès aux ressources partagées en fonction de l'urgence des processus. Enfin, nous montrons comment adapter notre RT-STM à un environnement temps réel firm en proposant quelques pistes d'adaptation permettant de garantir aux processus un certain niveau de qualité de service (QoS) vis-à-vis des accès aux ressources partagées.

L' evolution constante des applications, que ce soit en complexit e ou en besoin de performances, impose le d eveloppement de nouvelles architectures. Parmi l'ensemble des architectures propos ees se d emarquent les architectures recon gurables. Ce type d'architectures o re des performances proches d'un circuit d edi e tout en proposant davantage de exibilit e. Si originellement ces architectures ne pouvaient ^etre con gur ees qu' a leur d emarrage, elles sont d esormais con gurables partiellement a tout moment. Cette fonctionnalit e, nomm ee " recon guration dynamique ", permet de multiplexer temporellement et spatialement l'ex ecution de plusieurs applications, rapprochant ainsi l'utilisation des architectures recon gurables de celle d'un processeur g en eraliste. A l'instar des ordinateurs pourvus d'un processeur g en eraliste, il s'av ere donc n ecessaire de disposer d'un syst eme d'exploitation pour architectures recon gurables. Cette th ese se focalise sur la cr eation d'ordonnanceurs destin es a ce type d'architectures. Parce que nous ciblons l'ex ecution d'applications complexes - compos ees de plusieurs t^aches dont l'ordre d'ex ecution n'est pas connu a l'avance - les algorithmes d'ordonnancement doivent ^etre ex ecut es en ligne et les solutions obtenues en des temps tr es brefs. A cette n, nous r ealisons nos algorithmes d'ordonnancement en nous basant sur des r eseaux de neurones de Hop eld. Ce type de r eseaux a et e utilis e pour r esoudre des probl emes d'optimisations (tels que des probl emes d'ordonnancement) o u il a et e constat e qu'ils produisaient des solutions rapidement. De plus, leur simplicit e de fonctionnement (peu de structures de contr^ole) permet de les impl ementer e cacement sur des architectures recon gurables de type FPGA. Le premier chapitre de ce document introduit les concepts sur lesquels sont bas es nos travaux, a savoir, les architectures recon gurables ainsi que l'ordonnancement temporel et spatial destin e a ce type d'architectures. Le second chapitre pr esente les r eseaux de neurones de Hop eld. Dans le troisi eme chapitre, nous pr esentons un ordonnanceur temporel pour architectures h et erog enes recon gurables. Le quatri eme chapitre pr esente deux ordonnanceurs spatiaux, fond es sur des hypoth eses mat erielles di erentes. Le premier, bas e sur un r eseau de Hop eld, ne requiert que des m ecanismes de recon guration simples et est donc utilisable avec les outils fournis par les fabricants. Le second, quant a lui, n ecessite des m ecanismes actuellement non fournis par les fabricants, mais permet d'exploiter plus nement l'architecture. Le dernier chapitre pr esente des travaux relatifs aux r eseaux de neurones de Hop eld, a savoir l' evaluation parall ele de neurones, ainsi que des propri et es de tol erance aux fautes de ces r eseaux.

On étudie certaines méthodes de résolution de problèmes d'ordonnancement sur des calculateurs spécialisés qui simulent le fonctionnement du cerveau humain lors de la résolution de problèmes hautement combinatoires. On présente l'optimateur de la société CYBCO et le combinateur optimisant de la SNCF. Enfin on présente et on compare les solutions de divers problèmes traités par les calculateurs spécialisés et par des méthodes logicielles traditionnelles.

Notre objectif est la conception d'algorithmes d'ordonnancement temps réel en-ligne faisables (i.e., garantissant le respect des contraintes temporelles imposées au systèmes) optimisant 1) l'utilisation de la plate-forme d'exécution (i.e., utiliser au mieux le potentiel de la plate-forme d'exécution tout en garantissant le respect des contraintes temporelles imposées au système) et/ou 2) optimisant des critères de performances<br />propres à l'application.<br /> <br />Deux cas ont été analysés : le cas de tâches indépendantes périodiques s'exécutant sur un processeur et le cas de flux de messages indépendants périodiques sur un réseau de terrain avec accès au médium priorisé.<br /><br />Nous avons donc proposé pour traiter les deux problèmatiques abordées :<br />1) des méthodes de configurations permettant d'optimiser l'utilisation de la plate-forme d'exécution en fixant d'une manière appropriée les paramètres : des politiques ou des activités du système considéré. Deux études ont été conduites dans ce cadre~: l'allocation des ``offsets'' dans les systèmes ``offset free'' et l'allocation de priorités, de politiques et de quantum dans<br />les systèmes conformes au standard Posix~1003.1b,<br />2) une nouvelle classe de politiques d'ordonnancement permettant<br />d'optimiser des critères de performances propres à l'application.