L'usage des plateformes de Cloud Computing offrant une Infrastructure en tant que service (IaaS) a augmenté au sein de l'industrie. Les infrastructures IaaS fournissent des ressources virtuelles depuis un catalogue de types prédéfinis. Les avancées dans le domaine de la virtualisation rendent possible la création et la destruction de machines virtuelles au fur et à mesure, avec un faible surcout d'exploitation. En conséquence, le bénéfice offert par les plate-formes IaaS est la possibilité de dimensionner une architecture virtuelle au fur et à mesure de l'utilisation, et de payer uniquement les ressources utilisées. D'un point de vue scientifique, les plateformes IaaS soulèvent de nouvelles questions concernant l'efficacité des décisions prises en terme de passage à l'échelle, et également l'ordonnancement des applications sur les plateformes dynamiques. Les travaux de cette thèse explorent ce thème et proposent des solutions à ces deux problématiques. La première contribution décrite dans cette thèse concerne la gestion des ressources. Nous avons travaillé sur le redimensionnement automatique des applications clientes de Cloud afin de modéliser les variations d'utilisation de la plateforme. De nombreuses études ont montré des autosimilarités dans le trafic web des plateformes, ce qui implique l'existence de motifs répétitifs pouvant être périodiques ou non. Nous avons développé une stratégie automatique de dimensionnement, capable de prédire le temps d'utilisation de la plateforme en identifiant les motifs répétitifs non périodiques. Dans un second temps, nous avons proposé d'étendre les fonctionnalités d'un intergiciel de grilles, en implémentant une utilisation des ressources à la demandes.Nous avons développé une extension pour l'intergiciel DIET (Distributed Interactive Engineering Toolkit), qui utilise un marché virtuel pour gérer l'allocation des ressources. Chaque utilisateur se voit attribué un montant de monnaie virtuelle qu'il utilisera pour exécuter ses tâches. Le mécanisme d'aide assure un partage équitable des ressources de la plateforme entre les différents utilisateurs. La troisième et dernière contribution vise la gestion d'applications pour les plateformes IaaS. Nous avons étudié et développé une stratégie d'allocation des ressources pour les applications de type workflow avec des contraintes budgétaires. L'abstraction des applications de type workflow est très fréquente au sein des applications scientifiques, dans des domaines variés allant de la géologie à la bioinformatique. Dans ces travaux, nous avons considéré un modèle général d'applications de type workflow qui contient des tâches parallèles et permet des transitions non déterministes. Nous avons élaboré deux stratégies d'allocations à contraintes budgétaires pour ce type d'applications. Le problème est une optimisation à deux critères dans la mesure où nous optimisons le budget et le temps total du flux d'opérations. Ces travaux ont été validés de façon expérimentale par leurs implémentations au sein de la plateforme de Cloud libre Nimbus et de moteur de workflow MADAG présent au sein de DIET. Les tests ont été effectuées sur une simulation de cosmologie appelée RAMSES. RAMSES est une application parallèle qui, dans le cadre de ces travaux, a été portée sur des plateformes virtuelles dynamiques. L'ensemble des résultats théoriques et pratiques ont débouché sur des résultats encourageants et des améliorations.

La logistique de gestion de crise fait de plus en plus parler d'elle. En effet, que ce soit au sujet de conflits géopolitiques ou de catastrophes naturelles, ou encore lorsqu'il s'agit d'urgences de proximité, on ne peut plus passer à côté de la gestion de crise pour faire face à des faits internationaux ou nationaux. La logistique de gestion de crise œuvre pour que les secours soient optimisés et que l'aide et le ravitaillement en nourriture, eau, médicaments, soit apportés rapidement aux zones sinistrées. Les travaux de recherche présentés dans cette thèse, dans le cadre d'une coopération avec le département logistique d'EADS, visent à apporter une réponse à ces défis. Nous présentons, dans ce contexte, des solutions basées sur une approche de modélisation, optimisation et simulation orientée agents de flux logistiques. Les problèmes de gestion de flux abordés nous ont permis d'étudier et développer trois volets d'investigation : un module d'aide au positionnement des zones logistiques qui permet de minimiser les distances entre les zones et d'optimiser leurs nombre et ce pour une meilleure circulation des flux, une approche innovante pour l'ordonnancement distribué des tâches de livraison qui permet d'apporter une solution à un problème de gestion des flux fortement distribué, et finalement un agent holonique qui permet de fournir une estimation de la consommation à venir d'un site logistique, en alliant l'expertise des logisticiens aux modèles à base de logique floue. Pour démontrer l'efficacité des approches utilisées, un démonstrateur baptisé OBAC (Optimisation à Base d'Agents Communicants) a été réalisé, intégrant toutes ces approches et applications militaires

L'évolution de l'environnement des entreprises a transformé la nature des relations entre elles, qui de simple relations d'achat entre clients et fournisseurs se sont transformées en des rapports plus contractualisés et plus durables. Ces derniers imposent à ces entreprises de revoir leurs méthodes de gestion et de production pour une meilleure synchronisation de leurs flux. Nous nous intéressons dans ce mémoire à une relation particulière entre clients et fournisseurs, celle fondée sur le principe de livraisons cycliques, selon lequel le fournisseur s 'engage à livrer des quantités de produits à des intervalles de temps fixes et de façon répétitive. L'intérêt de ce mode de livraison et qu'il permet, aux donneurs d'ordres, une gestion extrêmement simple des approvisionnements et facilite l'organisation des activités. Comme réponse à ce type de livraisons et afin de synchroniser leurs flux de production à ceux de livraisons, les entreprises adoptent la production cyclique. L'avantage de cette dernière est qu ;elle permet entre autres de réduire les coûts engendrés par la fabrication, et de simplifier l'organisation du travail. Notre travail consiste alors en l'évaluation et la mise en oeuvre d'un plan de production cyclique, pour un atelier de type Flow Shop pur fabricant plusieurs produits, lorsque les appels de livraisons sont cycliques. Nous proposons une nouvelle méthode déterminant un plan de production cyclique minimisant des coûts de lancements, coûts de stockage et des coûts de fabrication. Nous introduisons dans un premier temps le contexte -de notre travail en précisant les différentes hypothèses que 1 'on pose. Nous proposons par la suite une revue de la littérature sur les différents travaux réalisés, et proposons une classification des problèmes traitant de la production cyclique étudiés par la communauté scientifique. Nous exposons également la méthode que l'on propose pour la détermination d'un plan de production cyclique minimisant les différents coûts que l'on considère. Nous présentons une analyse des résultats issus de l'application de notre approche ainsi que ses variantes sur un ensemble de benchmarks générés aléatoirement et respectant les traits caractéristiques des problèmes réels. Nous réalisons une étude comparative d?s approches que l'on propose à 1 'une de celles proposées dans la littérature. Nous terminons ce mémoire par une conclusion et un ensemble de voies de recherches futures.

Dans le cadre de cette thèse, nous nous intéressons à la modélisation et à la résolution de différents problèmes de tournées de véhicules et d'ordonnancement. Nous proposons des méthodes approchées qui ont pour but de résoudre les problèmes de manière rapide et efficace. Nous traitons cinq problèmes. Le premier est un problème d'ordonnancement de projet sous contrainte de ressources (RCPSP) que nous résolvons à l'aide d'un multiflot. Nous envisageons également des méthodes de résolution pour des extensions de ce problème (contraintes temporelles ou financieres). Le second est un problème de placement en deux dimensions. Nous utilisons une approche originale basée sur sa relaxation en RCPSP. Le troisième est le Stacker Crane Problem (SCP). Il fait parti des problèmes de pickup and delivery, dans lesquels des marchandises doivent être transportées depuis des origines vers des destinations à l'aide d'une flotte de véhicules. Dans le SCP, un unique véhicule de capacité unitaire est disponible. Nous proposons une résolution originale à base d'arbres pour le cas préemptif. Le quatrième est un problème de transport à la demande avec contraintes financières. Nous résolvons ce problème grâce à une heuristique d'insertion et une technique de propagation de contraintes. Le cinquième mêle problème de tournées et placement en deux dimensions. Il s'agit du 2L-CVRP dans lequel des colis doivent être livrés à des clients. Nous proposons un schéma GRASPxELS pour ce problème. Des résultats expérimentaux montrent la pertinence des approches proposées.

non disponible

Ce travail de thèse s'inscrit dans le cadre d'une collaboration industrielle avec la société Volume Software pour le développement du module d'ordonnancement du logiciel "DirectPlanning". Dans ce travail, nous étudions le problème de job shop flexible multicritère et le problème de job shop multiressource multicritère. Notre objectif est de déterminer une approximation du front de Pareto. Nous avons proposé des algorithmes de résolution approchés et plus particulièrement des algorithmes de recherche Tabou et des algorithmes génétiques. Nous avons proposé différentes versions de nos méthodes pour les deux problèmes considérés. Des expérimentations ont été réalisées et montrent les bonnes performances de nos algorithmes, à la fois d'un point de vue qualité des résultats et d'un point de vue de la rapidité des méthodes.

Cette thèse est consacrée à l'étude de l'ordonnancement en contexte incertain. La première partie précise la notion de contexte incertain en optimisation et présente les outils les plus connus pour prendre en compte l'incertitude. Le problème d'ordonnancement en contexte incertain est présenté sous sa forme prédictive et sous sa forme réactive, sans prise en compte explicite du caractère incertain des données. La deuxième partie traite des méthodes de prise en compte explicites de l'incertain avec garantie de performance. Les notions de robustesse et de flexibilité sont définies et illustrées par des exemples. La troisième partie présente la modélisation d'un atelier de photolithographie, et replace le problème de sa configuration dans le cadre de l'ordonnancement. Ce problème est traité sous trois hypothèses concernant les incertitudes. La première hypothèse est traitée dans la troisième partie. La quatrième partie est consacrée à la configuration de l'atelier lorsque la charge ou le temps de traitement de la commande n'est pas affecté par les perturbations. Le rayon de stabilité est présenté pour augmenter la robustesse de cette configuration. Enfin, la cinquième partie traite du même problème sans hypothèse particulière concernant les perturbations que subit la commande de l'atelier.

Le travail présenté dans cette thèse aborde le problème de la planification et de l'ordonnancement des<br />ressources dans les services de soins. Nous avons commencé par recenser différents travaux qui ont porté<br />sur l'un des aspects de ce problème. Cette revue de la littérature nous a permis d'opter pour une approche<br />par processus de soins dans l'objectif de minimiser le délai de séjour du patient dans l'hôpital ainsi que les<br />coûts de sa prise en charge, et ce dans le respect de la qualité des soins. Cette approche a été<br />particulièrement illustrée dans le cas de processus de soins passant par un service de chirurgie.<br />Afin de tenir compte des aspects aléatoires, l'une des caractéristiques importantes de l'environnement<br />hospitalier, nous avons proposé de traiter le problème de la planification et de l'ordonnancement des<br />ressources suivant une structure hiérarchique qui porte sur quatre niveaux décisionnels. Le premier niveau<br />porte sur la planification des admissions qui consiste à fixer les dates d'hospitalisation des patients pour une<br />intervention chirurgicale. Cependant, la planification des admissions fournit au patient une date<br />d'hospitalisation qui risque de ne pas être très fiable à cause de la possibilité d'occurrence de différentes<br />perturbations. Nous avons ainsi proposé d'adopter un processus de confirmation des dates d'hospitalisation<br />conformément au programme opératoire construit sur l'horizon de T jours. Le troisième niveau décisionnel<br />consiste dans la construction du programme opératoire journalier. Cette construction est à double objectifs :<br />d'une part, mettre à jour le programme opératoire établi sur l'horizon de T jours en intégrant les différents<br />aléas qui ont pu avoir lieu dans la système de soins tel que le report d' interventions à cause d'admissions de<br />cas urgents, non programmées à l'avance ; d'autre part, préciser l'ordre de réalisation des interventions en<br />considérant les ressources critiques utilisées dans le processus opératoire. Ensuite, nous avons proposé une<br />approche temps-réel pour aider au pilotage du bloc opératoire devant l'occurrence d'aléas nécessitant de<br />repenser le programme opératoire journalier, en cours de réalisation. Parmi les différents types d'aléas<br />auxquels doit faire face le système de soins, nous avons traité ici de près le cas de la prise en compte de<br />l'urgence.

Le besoin de solutions de test en-ligne intégré est de plus en plus important. Malgré la complexité croissante de systèmes numériques, ces solutions doivent garantir un surcoût raisonnable en temps de conception, en ressources impliquées et en performance. Cela nécessite le développement de nouvelles méthodes de synthèse de haut niveau qui doivent garantir deux contraintes. La première est la possibilité de traiter des systèmes complexes à un coût raisonnable. La deuxième est la prise en compte des contraintes de test en-ligne dans les premières tâches du flot de la synthèse de haut niveau. Pour s'accommoder à ce besoin, la présente étude propose deux axes de travail. Le premier axe consiste à proposer deux méthodes de test en-ligne, non-concurrent et semi-concurrent, présentées comme solutions intégrées (BIST). Le deuxième axe consiste à proposer une nouvelle méthode de synthèse de haut niveau (HLS) qui tient compte de la testabilité en-ligne. La prise en compte des contraintes de test en-ligne est effectuée au niveau de la compilation de la description comportementale en graphe de flot de données (DFG). Selon les contraintes imposées au système, une des méthodes de test en-ligne développées dans le premier axe est intégrée au système au niveau ordonnancement. Un système numérique donné par sa description comportementale forme l'entrée de la méthode. Dans un premier temps, une optimisation orientée testabilité adresse les équations arithmétiques dans la description comportementale du système. Outre l'amélioration de la testabilité, cette optimisation peut permettre d'améliorer les performances du design final. La description optimisée est compilée en graphe de flot de données ordonnancé. La tâche de la compilation et de l'ordonnancement est résolue par une exploration de l'espace de solutions. Dans cette exploration nous introduisons le développement d'un algorithme génétique (AG) adapté à ce type de problèmes. Les contraintes de test en-ligne, de surface et de délai sont considérées à cette étape pour produire une solution satisfaisante. Une fois que le graphe de flot de données ordonnancé est obtenu, la méthode qui répond le mieux aux contraintes de test en-ligne est insérée dans l'ordonnancement nominal du système. L'allocation de ressource et l'assignation permettent la génération d'une architecture testable en-ligne au niveau RTL. Mots clés : synthèse de haut niveau, compilation, ordonnancement, testabilité en-ligne, DFG, BIST, AG.

Planifier, au sens large du terme, consiste à déterminer quoi faire et comment le faire pour atteindre des objectifs fixés. Jusqu'à présent ces deux questions ont été étudiées de manière relativement indépendante : la question du quoi faire par la synthèse de plans d'actions, celle du comment le faire par la gestion de ressources. <br />Cette thèse vise à intégrer les deux problématiques dans un même système de planification au sens large, nommé IXTET, qui offre une représentation riche et homogène supportée par une algorithmique saine et complète permettant de mener de front les processus de synthèse de plans et de gestion de ressources.<br />Au niveau de la représentation, IXTET permet d'exprimer des contraintes temporelles symboliques et numériques, une large gamme de ressources (partageables ou non, consommables, productibles), des opérateurs de planification complexes et des environnements pouvant avoir une dynamique indépendante des actions planifiées.<br />En cours de résolution, le plan partiel courant est analysé et représenté sous la forme d'un ensemble de défauts sous-buts pendants, menaces sur une protection et conflit de ressources – auxquels sont associés des résolvantes - contraintes temporelles, contraintes sur les variables atemporelles, insertion d'un lien causal ou d'une tâche. Le développement de l'arbre de recherche s'effectue alors par l'insertion de résolvantes pour résoudre les défauts du plan courant. L'algorithme original de détection des conflits de ressource est basé sur la recherche de cliques particulières sur un graphe d'intersections possibles. Les choix non-déterministes – prochain défaut à résoudre, résolvante à insérer – sont justifiés par une stratégie de moindre engagement et d'opportunisme de la recherche. Afin de structurer la recherche pour en améliorer les performances, une approche hiérarchique est développée. Un ordre partiel définissant un ensemble de hiérarchies d'abstraction est automatiquement généré à partir de la description syntaxique des tâches. Cet ordre partiel est ensuite utilisé, en cours de planification, pour remettre à jour dynamiquement le niveau d'abstraction courant.<br />L'approche IXTET, codée en C++, a été confrontée à de nombreux domaines qui ont permis de la valider, de caractériser ses points forts et de dégager des perspectives de recherche prometteuses.