La programmation par contraintes, carrefour de diverses disciplines, a montré son intérêt dans de nombreux domaines d'application. De nombreux problèmes réels sont dynamiques : le système de contraintes les définissant n'est donc pas figé. Pour résoudre un problème dynamique, il faut assurer une certaine incrémentalité et être capable de traiter les systèmes de contraintes contradictoires. En effet, il est souvent indispensable de fournir une solution quitte à ne pas respecter certaines contraintes. On parle alors de relaxation de contraintes.<br /><br />Durant cette thèse, nous nous sommes intéressés à la définition d'un système de relaxation de contraintes permettant de maintenir une propriété donnée dans un environnement dynamique. Nous avons mené ces travaux depuis une présentation abstraite d'un tel système jusqu'à son implémentation.<br /><br />Nous présentons un schéma algorithmique général abstrait de la recherche d'une solution à un problème sur-contraint basée sur l'exploration en meilleur d'abord d'un espace de configurations. Nous en donnons trois instances pour traiter les contraintes linéaires sur les rationnels, les Constraint Satisfaction Problems et les CSP numériques. Les deux dernières sont définies à l'aide d'un système de maintien de déduction dont la ma\^\itrise raisonnée nous a permis de donner une implémentation de ces instances ayant une bonne complexité : le système DECorum.<br /><br />Nous montrons, par le biais d'un certain nombre d'expérimentations, que l'utilisation de DECorum permet de retrouver les résultats classiques sur la transition de phase, de résoudre raisonnablement des problèmes de grande taille et d'utiliser la structure du problème résolu pour améliorer la recherche.<br /><br />Enfin, nous proposons la contrainte one-of permettant de modéliser et de résoudre une disjonction de contraintes en tirant profit du mécanisme d'exploration de DECorum. Nous validons l'intérêt de la contrainte one-of sur des problèmes d'ordonnancement : les Open-Shop.

Actuellement on assiste à une émergence des applications des systèmes embarqués destinées à un large public d'utilisateurs. Ces applications sont de plus en plus complexes et diversifiées. Elles nécessitent une capacité de calcul accrue et doivent satisfaire, dans leurs exécutions, la prise en compte du temps réel. De plus, ces systèmes sur puce fonctionnent dans des conditions souvent difficiles et perturbantes. Ainsi, certaines contraintes temporelles, contraintes de ressources, contraintes de précédence ainsi que d'autres caractéristiques des systèmes généraux peuvent changer au cours d'exécution. Pour respecter leurs contraintes, ces systèmes doivent être capables de supporter la nature dynamique du monde réel depuis la modélisation de l'application jusqu'à son implémentation sur la plateforme d'exécution. Dans cette thèse une nouvelle approche combinant la modélisation haut niveau et l'ordonnancement sur une architecture reconfigurable dynamiquement de nouveau type, a été proposée. Cette approche est originale depuis ça conception en ciblant des applications fortement dynamiques et flexibles. De plus, l'ordonnanceur ainsi développé intègre un nouveau service qui est responsable de la prédiction des variables dynamiques afin d'aboutir à une meilleure exploitation de l'architecture et meilleure performance d'exécution. Des expérimentations ont été présentées sur des applications temps réel.

Ce travail propose une méthode d'aide à la coopération inter-entreprises dans un contexte de production à la commande. L'objectif est de tendre les flux de production inter-entreprises grâce à une coopération entre les décideurs de chaque entreprise. L'approche retenue assimile le problème d'organisation globale à un processus de décision distribuée dans lequel l'organisation est progressivement construite par un ensemble de coopérations entre des couples d'acteurs du réseau d'entreprises. Nous étudions en particulier les couples d'entreprises client-fournisseur pour lesquels la coopération concerne les attributs des commandes passées entre eux. Nos objectifs sont de fournir aux décideurs un cadre plus formel qui contractualise la coopération et des outils d'aide à la décision pour la coopération permettant de les assister dans les diverses phases du processus.

L'architecture des ordinateurs est maintenant dans l'ère des multiprocesseurs permettant le calcul en parallèle. Les systèmes embarqués les plus récents s'appuient sur plusieurs processeurs DSP (Digital Signal Processor) ou MPSoC (Multiprocessor System-on-Chip). Corrélativement, les algorithmes des applications de traitement du signal et de l'image deviennent de plus en plus sophistiqués. La mise en oeuvre de telles applications sur un système embarqué devient complexe. Aussi, les approches de prototypage rapide et de co-conception matérielle/logicielle sont souvent utilisées pour faciliter ce travail. Le problème de l'ordonnancement des tâches, étape importante du prototypage rapide, est discuté et traité dans cette thèse. Nous cherchons des modèles d'ordonnancement des tâches en considérant précisément les communications entre les tâches. Nous modélisons ainsi l'algorithme de l'application comme un graphe acyclique orienté (Directed Acyclic Graph ou DAG), et nous proposons un modèle avancé décrivant de façon appropriée l'architecture du système embarqué parallèle. Après la formalisation du problème de l'ordonnancement des tâches avec ce modèle d'architecture, nous présentons plusieurs heuristiques d'ordonnancement basées sur la méthode de la liste (list scheduling) pour améliorer les performances de l'ordonnancement. Nos résultats expérimentaux attestent d'une accélération de l'application dans un contexte de moyenne ou de forte communication. Comme le poids des communications va en croissant dans les applications les plus récentes, que ce soient en communication numérique ou en compression vidéo, nos méthodes s'avèrent efficaces dans la mise en oeuvre de ces applications sur systèmes embarqués parallèles. Nos méthodes d'ordonnancement sont intégrées dans PREESM, environnement de prototypage rapide basé sur Eclipse en "open source".

Face au défi que représente la programmation des architectures multi-cœurs/processeurs, il est devenu nécessaire de proposer aux développeurs des outils adaptés permettant d'abstraire les notions inhérentes au parallélisme et facilitant le portage d'une application sur différentes architectures. La méthodologie AAA (Adéquation Algorithme Architecture) propose au développeur d'automatiser les étapes de partitionnement, ordonnancement à partir d'une description haut niveau de l'application et de l'architecture. Cette méthodologie permet donc le prototypage rapide d'une application sur différentes architectures avec un minimum d'effort et un résultat approchant l'optimal. Les apports de cette thèse se situent à la fois au niveau du modèle de spécification et de ses optimisations relatives au contexte des architectures parallèles. Le modèle flux de données répond aux problèmes de modélisation des applications fortement synchronisées par les données. Le sous-ensemble SDF (Synchronous Data Flow), limite l'expressivité du modèle mais apporte un complément d'information permettant une optimisation efficace et garantissant l'intégrité du calcul dans tous les contextes. Les travaux développés dans ce mémoire introduisent un nouveau modèle de hiérarchie dans SDF afin d'améliorer l'expressivité tout en préservant les propriétés du modèle initial. Ce modèle basé sur des interfaces, permet une approche plus naturelle pour le développeur accoutumé au langage C. Ce nouveau modèle apportant un complément d'information, nous proposons également un ensemble de traitement améliorant la prise en charge des motifs de répétition imbriqués. En effet le modèle de hiérarchie introduit en première partie permet la spécification de motifs dit de " nids de boucles " pouvant masquer le parallélisme potentiel. Il est donc nécessaire d'associer au modèle des traitements permettant de révéler ce parallélisme tout en préservant l'aspect factorisé du calcul. Les méthodes présentées sont adaptées du contexte des compilateurs pour supercalculateurs et de l'univers des réseaux systoliques.

Dans cette thèse, nous nous intéressons au problème de chargement des laveurs dans un service de stérilisation de dispositifs médicaux réutilisables (DMR). Ce problème de chargement des laveurs a été considéré comme un problème d'ordonnancement par batch. Nous présentons, dans un premier temps, des études offline pour lesquelles nous avons développé des algorithmes, exacts et approchés, ainsi que des modèles PLNE pour certains cas particuliers et pour des cas généraux. Nous présentons ensuite des études semi-online et online pour lesquelles nous avons développé des heuristiques. Nous avons également conçu des modèles de simulation afin de tester l'impact de nos heuristiques sur l'ensemble du service de stérilisation. Nous proposons, en dernier lieu, l'implémentation d'une approche de type bin packing pour le cas d'un service de stérilisation externe afin de minimiser le nombre de cycles de lavage lancés.

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.

Nous présentons des solutions algorithmiques pour deux problèmes liés à l'interfé-rence de réseau sans fil. D'abord on propose de ordonnancer les liens d'un ensemble de routes données en vertu de l'hypothèse d'un modèle à fort trafic. Nous considérons un protocole TDMA qu'offre une source d'intervalles de temps synchronisés et cherchent à ordonnancer les itinéraires des liens afin de maximiser le nombre de paquets qui sont livrés à leurs destinations par chaque intervalle de temps. Notre approche consiste à construire un graphe non orienté $G$ et à obtenir multiples colorations pour les noeuds de $G$ qui peuvent induire aux ordonnancement de liens efficaces. En $G$ chaque noeud représente un lien à être ordonnancer et les arcs sont mis en place pour représenter toutes les interférences possibles pour un ensemble d'hypothèses d'interférence. Nous présentons deux heuristiques de multiples colorations et étudions leurs performances grâce à de nombreuses simulations. L'un des deux heuristiques est fondée sur l'assouplissement des dynamiques de multiples colorations en exploitant la disponibilité des possibilités de communication qui seraient autrement perdues. Nous avons constaté que, par conséquent, sa performance est nettement supérieure à la celle des autres. Dans la deuxième proposition, nous considérons les réseaux maillés sans fil et le problème de routage bout à bout du trafic sur les chemins multiples pour la même paire origine-destination avec un minimum d'interférences. Nous introduisons une heuristique pour la détermination des chemins avec deux caractéristiques distinctives. Tout d'abord, il fonctionne par le raffinage d'un ensemble existant de chemins, préalablement déterminée par un algorithme de routage de multiples chemins. Deuxièmement, il est tout à fait locale, dans le sens où il peut être exécuté par chacune des origines sur l'information qui est disponible plus loin dans le réseau de voisinage immédiat du noeud. Nous avons mené de nombreuses expériences avec la nouvelle heuristique, en utilisant le protocole OLSR et AODV ainsi que leurs variantes de chemins multiples. Nous avons démontré que la nouvelle heuristique est capable d'améliorer le débit moyen du réseau à l'échelle en utilisant un protocole TDMA sous l'exécution d'un algorithme de ordonnancement des liens orienté à routes et de deux différents paramètres de fonctionnement du protocole CSMA 802.11. En travaillent à partir des trajectoires générées par le chemin provenaient de algorithmes de multiples chemins, l'heuristique est également capable de fournir un modèle de trafic plus équitablement répartie.

Cette HDR concerne l'ordonnancement en présence de divers communications

La démocratisation des nouvelles plateformes d'exécution parallèles et distribuées, notamment les grilles de calcul, a engendré l'émergence de nouvelles d'architectures constituées en grande partie par des ressources fournies par des personnes/organisations volontaires. Ces machines ne sont pas disponibles tout le temps. Elles sont sujettes à des perturbations liées aux incertitudes sur les dates de début et de fin de disponibilités. Pour générer des ordonnancements adaptés à ces plateformes, nous cherchons à optimiser, en plus des fonctions objectifs classiques, un nouveau critère qui caractérise l'aptitude de l'ordonnancement à absorber l'effet des perturbations (la stabilité). Nous nous sommes intéressés dans le cadre de ce travail au problème de l'ordonnancement avec contraintes d'indisponibilité de ressources et d'incertitudes sur les dates d'occurrence des évènements. Nous commençons par étudier le cas préliminaire de ce problème où une seule indisponibilité est possible par machine et où l'incertitude porte sur la durée de l'indisponibilité. Nous généralisons ensuite cette étude pour le cas où plusieurs indisponibilités peuvent être envisagées sur les machines et où l'incertitude porte sur les dates d'occurrences des évènements. Pour l'ensemble de ces problèmes, nous utilisons une technique de tampon pour fournir une famille d'ordonnancements qui optimisent simultanément la performance et la stabilité des ordonnancements générés. Une vaste campagne de simulation des heuristiques proposées conduit à la sélection de configurations qui aboutissent à des résultats satisfaisants en terme de compromis. Mots clés : Parallélisme, ordonnancement, incertitude, disponibilité, stabilité