Les services de maintenance interviennent pour maintenir ou remettre en état de bon fonctionnement les équipements. A travers la réduction de l'indisponibilité des équipements, ils participent à l'amélioration de la compétitivité des entreprises. Le service de maintenance est composé entre autre, de ressources humaines qui réalisent les tâches de maintenance. L'un des problèmes du manager de ce service est alors de trouver, pour chaque tâche, quelle ressource la traitera et quand. <br />Dans cette thèse, nous nous intéressons à un problème d'affectation et d'ordonnancement en prenant en compte les compétences des ressources humaines. Les différences de compétence sont peu intégrées dans les modèles de la littérature. Les ressources sont en effet souvent considérées comme identiques ou n'ayant qu'une compétence. Les différents types de tâches présentent aussi des spécificités qui sont peu retrouvées dans les approches de la littérature. Cette problématique se retrouve dans d'autre contexte que celui de la maintenance et touche plus généralement l'affectation et l'ordonnancement de l'activité d'un service.<br />Nous proposons une approche de résolution dynamique pour un problème mono-critère d'affectation et d'ordonnancement des activités de maintenance. Dans le contexte de la maintenance, différents critères concernant les ressources et les tâches sont importants. Nous proposons donc une extension de l'approche dynamique mono-critère au multi-critère. Certaines données utilisées dans l'affection et l'ordonnancement sont incertaines. Pour anticiper la présence de ces incertitudes nous proposons une approche dynamique, proactive à un problème multi-critère d'affectation et d'ordonnancement d'activité de maintenance en contexte incertain. Toutes ses approches font appel à une méthode d'amélioration par modification partielle de l'ordonnancement, inspirée de la méthode du kangourou.

Dans ce mémoire, nous nous intéressons à l'étude et la résolution de problèmes d'ordonnancement de type flowshop de permutation, en présence de contraintes d'écarts temporels (ou time lags), définies entre les couples d'opérations consécutives au sein des travaux. De telles contraintes généralisent les contraintes de précédence classiques et peuvent modéliser de nombreuses situations réelles. De nouveaux résultats de complexité sont démontrés et viennent compléter des résultats classiques tirés de la littérature. Nous présentons aussi un état de l'art assez détaillé sur les travaux concernant les problèmes d'ordonnancement avec time lags, qui met en évidence le manque d'attention reçu par ces problèmes. Nous développons ensuite un schéma générique de résolution exacte reposant sur une Procédure par Séparation et Evaluation et nous l'utilisons pour résoudre plusieurs problèmes de flowshop de permutation en présence de time lags. L'efficacité de cette approche de résolution est évaluée grâce à des séries d'expériences numériques. Enfin, des extensions permettant de prendre en compte des contraintes supplémentaires sont proposées.

Nos travaux portent sur la résolution de problèmes d'optimisation en ordonnancement d'ateliers de production, et plus particulièrement ceux relatifs à l'ordonnancement dynamique dans les industries agroalimentaires. <br />Les contraintes et les critères considérés sont spécifiques à ce type d'industrie qui présente certaines particularités, dues à la nature des produits manipulés et fabriqués, dont les durées de vie assez courtes. Ils concernent aussi le respect des dates de validité des composants primaires formant les opérations, des produits semi-finis et des produits finis. Les critères retenus sont aussi liés à ces particularités. On a distingué le coût des produits périmés, le coût du discount de distribution et la date de fin de l'ordonnancement, le makespan. Une méthode exacte et deux méthodes approchées ont été retenues et mises en œuvre, avec succès, pour les problèmes à une machine. <br />La méthode exacte, branch & bound, est appliquée pour la minimisation de la fonction de coût total. Les algorithmes génétiques, dotés d'un nouveau codage et hybridés avec l'approche Pareto-optimale, sont proposés pour la recherche de la solution optimale et pour aider le décideur de prendre une décision. Les algorithmes d'optimisation par colonie de fourmis, constituant la deuxième méthode approchée, est un processus stochastique qui, malgré la difficulté de paramétrage de l'algorithme correspondant, nous a permis de construire des solutions, en ajoutant des composants aux solutions temporaires.

Nous étudions quatre problèmes d'ordonnancement sur machines parallèles. Ces quatre problèmes diffèrent par le critère que l'on cherche à minimiser : la somme des dates de fin, la somme pondérée des dates de fin, le retard total ou le retard total pondéré. Les jobs à ordonnancer sout soumis à des dates de disponibilité. Nous avons proposé pour ces quatres problèmes plusieurs règles de dominance. Une étude des bornes<br />inférieures a également été réalisée. Enfin, nous avons proposé une méthode de résolution exacte utilisant les règles de dominance ainsi que les bornes inférieures.

Cette thèse se focalise sur le développement des algorithmes d'ordonnancement sous contrainte (m, k)-firm, ainsi que leurs applications pour la gestion de la qualité de service (QdS) dans les réseaux et systèmes temps réel distribués. L'objectif recherché est la ga-rantie déterministe de la QdS tout en maintenant un fort taux d'utilisation des ressources.<br />Les contributions sont (1) l'établissement d'une condition suffisante d'ordonnançabilité d'un ensemble de tâches sous l'algorithme « distance based priority »; (2) la définition de R-(m, k)-firm, un nouveau modèle qui relâche la contrainte (m, k)-firm et qui permet de modéliser de façon plus juste des exigences du temps réel souple; (3) le développement d'un algorithme efficace de dimensionnement de ressources sous contrainte (m, k)-firm relâchée; (4) la proposition de « Double Leaks Bucket » pour la gestion active de files d'attente permettant de maintenir une QdS en cas de surcharge des réseaux.

Construire des modèles qui représentent fidèlement les systèmes temps réels complexes est indispensable pour l'analyse de leurs propriétés fonctionnelles et temporelles. Ce travail présente une méthodologie de modélisation pour les systèmes temps réels dans le contexte de la technologie Java. Le modèle est obtenu par la restriction du modèle fonctionnel du logiciel avec les informations temporelles appropriées. Nous établissons un sous ensemble du langage Java qui réglemente la structure concurrente de l'application, la communication et les pratiques de programmation au niveau des threads, des objets et du flot de contrôle. Le modèle fonctionnel est construit à partir de règles de réécriture basées sur la sémantique du langage. Les modèles non temporisés sont ensuite décorés par les informations relatives à la plate forme d'exécution, la dynamique de l'environnement et les échéances temps réel. La méthodologie de modélisation à été implémentée dans l'outil JediTool.

Les travaux de cette thèse, menés dans le cadre du projet RNRT A3S, intègrent la notion de composants au sein d'une méthodologie de conception de plates-formes SoC (System on Chip), basée sur le langage de modélisation UML (Unified Modeling Language). Cette méthodologie propose un environnement de conception haut-niveau, basé sur le profil UML A3S, développé pour apporter la sémantique du domaine des systèmes temps réel embarqués et en particulier celle relative aux applications Radio Logicielle. Elle repose sur une approche MDA ou l'architecture est dirigée par les modèles où chaque modèle correspond à un niveau d'abstraction, à un niveau de raffinement particulier.<br /><br />Une chaîne UMTS a permis la validation de l'outil réalisé, en confrontant les résultats estimés de l'outil, à ceux mesurés sur une plate-forme temps réel hétérogène (multi-DSP, multi-FPGA). Une partie du travail s'est concentré sur l'identification des composants utiles à la conception des systèmes SoC, et de leurs caractéristiques, en adéquation avec le niveau d'abstraction considéré. Une autre partie des travaux a porté sur la définition des modèles UML, et donc du profil, qui définissent la sémantique des différents composants identifiés en fonction de la configuration (PIM, PSM), ainsi que leurs relations. Une réflexion a été nécessaire afin d'élaborer les diverses règles de vérification et modèles d'exécution qui permettent d'informer le concepteur de ses erreurs et de la faisabilité du système modélisé. Un modèle de système d'exploitation a également été inclus, enrichissant la liste des éléments (composants) déjà définis et démontrant l'extensibilité du profil.

Cette thèse développe une méthodologie pour résoudre les problèmes d'ordonnancement de programmes conditionnels où savoir si une tâche doit être exécutée n'est pas connue à l'avance mais dynamiquement. Le modèle utilisé est à base d'automates temporisés représentant l'espace d'états à explorer. Le problème est donc formulé comme le calcul d'une stratégie gagnante (pire cas optimale) dans un jeu contre l'environnement. Dans un premier temps nous étudions le problème d'ordonnancement sur graphes de tâches déterministe puis nous étendons l'étude au problème d'ordonnancement avec incertitude conditionnelle. Pour les deux problèmes nous étudions différentes classes d'ordonnancements et de stratégies pour réduire l'espace d'états, des décompositions en chaînes pour réduire sa taille, puis nous investiguons plusieurs classes d'algorithmes exactes pour en évaluer l'efficacité et à partir desquels nous dérivons de bonnes heuristiques. Des résultats expérimentaux sur plusieurs exemples de benchmarks sont présentés afin de montrer l'efficacité de chaque algorithme et la précision des heuristiques proposées, puis des bornes théoriques sont déduites pour prouver la garantie de performance pire cas de chaque heuristique.

Thèse de doctorat : Informatique : Lille 1 : 2000. / Résumé en français et en anglais. Bibliogr. p. 177-188.

La méthode multipôle permet d'accélérer les produits matrices-vecteurs, utilisés par les solveurs itératifs pour déterminer le comportement électromagnétique, d'un objet soumis à une onde incidente. Nos travaux ont pour but d'adapter cette méthode pour la rendre efficace sur les architectures hétérogènes contenant des GPU. Pour cela, nous utilisons une ordonnanceur dynamique, StarPU, qui effectuera la distribution des tâches de calcul au sein d'un nœud. Pour la parallélisation en mémoire distribuée, nous effectuerons un ordonnancement statique des boîtes, couplé à un ordonnancement dynamique des interactions proches.