Le thème de ce mémoire est l'ordonnancement dans les ateliers de production. L'objectif est d'étudier différents modèles classiques en analysant les liens et différences entre ces modèles et les problèmes pratiques associés. Les méthodes utilisées sont l'analyse de problèmes de nos partenaires industriels, l'étude de la complexité des problèmes ou de la structure des solutions et la proposition de méthodes de résolution exactes ou approchées. Le premier axe de cette thèse est l'étude de problèmes d'ordonnancement avec contraintes de ressources d'entrée/sortie. Les environnements considérés sont les flowshops robotisés et le nouveau modèle d'indisponibilité des opérateurs. Le second axe abordé concerne l'ordonnancement avec high multiplicity où les pièces sont agrégées en catégories. La description complète d'un ordonnancement (c'est-à-dire les instants de fabrication des tâches) n'est que pseudo-polynomiale de la taille de l'instance.

Dans cette thèse, nous étudions trois problèmes d'ordonnancement de la chaîne logistique dans le modèle de production à la demande. Le premier problème est un problème d'ordonnancement de production et de distribution intermédiaire dans une chaîne logistique avec un producteur et un prestataire logistique. Le deuxième problème est un problème d'ordonnancement de production et de distribution aval avec des dates de début au plus tôt et des dates limites de livraison dans une chaîne logistique avec un producteur, un prestataire logistique et un client. Le troisième problème est un problème d'ordonnancement de production et de distribution aval avec des temps de réglage et des fenêtres de temps de livraison dans une chaîne logistique avec un producteur, un prestataire logistique et plusieurs clients. Pour les trois problèmes, nous étudions les problèmes d'ordonnancement individuels et les problèmes d'ordonnancement coordonnés. Nous proposons des algorithmes polynomiaux ou prouvons la NP-Complétude de ces problèmes, et développons des algorithmes exacts ou heuristiques pour résoudre les problèmes NP-Difficiles. Nous proposons des mécanismes de coordination et évaluons le bénéfice de la coordination. / In this dissertation, we aim at investigating three supply chain scheduling problems in the make-To-Order business model. The first problem is a production and interstage distribution scheduling problem in a supply chain with a manufacturer and a third-Party logistics (3PL) provider. The second problem is a production and outbound distribution scheduling problem with release dates and deadlines in a supply chain with a manufacturer, a 3PL provider and a customer. The third problem is a production and outbound distribution scheduling problem with setup times and delivery time windows in a supply chain with a manufacturer, a 3PL provider and several customers. For the three problems, we study their individual scheduling problems and coordinated scheduling problems: we propose polynomial-Time algorithms or prove the intractability of these problems, and develop exact algorithms or heuristics to solve the NP-Hard problems. We establish mechanisms of coordination and evaluate the benefits of coordination.

Du fait des énormes capacités de calculs des accélérateurs tels que les GPUs et les Xeon Phi, l’utilisation de machines multicoques pourvues d’accélérateurs est devenue commune dans le domaine du calcul haute performance (HPC). La complexité induite par ces accélérateurs a suscité le développement de systèmes d’exécution à base de tâches, dans lesquels les dépendances entre les applications sont exprimées sous la forme de graphe de tâches et où les tâches sont ordonnancées dynamiquement sur les ressources de calcul. La difficulté est alors de concevoir des stratégies d’ordonnancement qui font une utilisation efficace des ressources de calculs et le développement de telles stratégies, même pour un unique noeud hybride, est un enjeu essentiel de la performance des systèmes HPC. Nous considérons dans cette thèse l’ordonnancement de noyaux d’algèbre linéaire dense sur des noeuds complètement hétérogènes et constitués de CPUs et de GPUs. Les performances relatives des accélérateurs par rapport aux coeurs classique dépend très fortement du noyau considéré. Par exemple, les accélérateurs sont beaucoup plus efficaces pour les produits de matrices, par exemple, que pour les factorisations. Dans cette thèse, nous analysons les performances de stratégies statiques et dynamiques d’ordonnancement et nous proposons un ensemble de stratégies intermédiaires, en ajoutant des composantes statiques (respectivement dynamiques) à des stratégies d’ordonnancements dynamique (respectivement statiques). Récemment, une stratégie appelée HeteroPrio a été proposée, qui s’appuie sur les affinités entre les tâches et les ressources pour un petit ensemble de tâches différentes s’exécutant sur deux types de ressources. Nous avons étendu cette stratégie d’ordonnancement pour des graphes de tâches généraux pour deux types de ressources puis pour plus de deux types. De manière complémentaire, nous avons également démontré des facteurs d’approximation et des pires cas pour HeteroPrio dans le cas d’un ensemble de tâches indépendantes sur différents types de plates-formes. / Due to massive computation power of accelerators such as GPU, Xeon phi, multicore machines equipped with accelerators are becoming popular in High Performance Computing (HPC). The added complexity led to the development of different task-based runtime systems, which allow computations to be expressed as graphs of tasks and rely on runtime systems to schedule those tasks among all resources of the platform. The real challenge is to design efficient schedulers for such runtimes to make effective utilization of all resources. Developing good schedulers, even for a single hybrid node, and analyzing them can thus have a strong impact on the performance of current HPC systems. We consider the problem of scheduling dense linear algebra applications on fully hybrid platforms made of CPUs and GPUs. The relative performance of CPU and GPU highly depends on the sub-routine. For instance, GPUs are much more efficient to process matrix-matrix multiplications than matrix factorizations. In this thesis, we analyze the performance of static and dynamic scheduling strategies and we propose a set of intermediate strategies, by adding static (resp. dynamic) features into dynamic (resp. static) strategies. A resource centric dynamic scheduler, HeteroPrio, which is based on affinity between tasks and resources, has been proposed recently for a set of small independent tasks on two types of resources. We extend and analyze this scheduler for general task graphs first on two types of resources and then on more than two types of resources. Additionally, we provide approximation ratios and worst case examples of HeteroPrio for a set of independent tasks on different platform sizes.

La plupart des méthodes d'ordonnancement considèrent un environnement déterministe où les données du problème sont connues. Néanmoins, en réalité, plusieurs sortes d'aléas peuvent être rencontrées et l'ordonnancement robuste permet en tenir compte. Dans cette thèse, notre intuition initiale est que, d'une part, un ordonnancement non robuste deviendra rapidement inefficace avec les incertitudes qu'un ordonnancement robuste, et d'autre part, un ordonnancement robuste sera moins efficace qu'un ordonnancement non robuste en l'absence d'incertitudes. Dans ce cadre, nous avons proposé un algorithme génétique pour l'ordonnancement robuste. Un nouveau mécanisme de résolution et un nouveau critère de robustesse permettant de trouver une solution de bonne performance et peu sensible aux incertitudes ont été développés. Une phase expérimentale a été menée, d'une part, pour vérifier l'efficacité de l'algorithme génétique pour l'ordonnancement déterministe, sans tenir compte des incertitudes, et d'autre part, pour valider l'algorithme génétique pour l'ordonnancement robuste par la simulation afin de juger la qualité de la robustesse face aux incertitudes. Nous avons intégré cette approche de robustesse dans une démarche méthodologique générique intégrant des techniques d'optimisation et de simulation pour l'aide au dimensionnement des systèmes de production basé sur des ordonnancements robustes. Les différents modules de la démarche ont été développés sous forme d'un outil d'aide au dimensionnement, dans le cadre d'un cas applicatif réel, celui du bloc opératoire dans le secteur hospitalier.

Les systèmes temps réel sont des systèmes informatiques composés de tâches auxquelles sont associées des contraintes temporelles, appelées échéances. Dans notre étude, nous distinguons deux familles de tâches : les tâches temps réel dur et les tâches temps réel souple. Les premières possèdent une échéance stricte, qu'elles doivent impérativement respecter. Elles sont de nature périodique, ou sporadique, et l'étude analytique de leur comportement fait l'objet d'un état de l'art conséquent. Les secondes sont de nature apériodique. Aucune hypothèse sur leur modèle d'arrivéée ni sur leur nombre n'est possible. Aucune garantie ne saurait être donnée sur leur comportement dès lors que l'on ne peut écarter les situations de surcharge, où la demande de calcul peut dépasser les capacités du système. La problématique devient alors l'étude des solutions d'ordonnancement mixte de tâches périodiques et apériodiques qui minimisent les temps de réponse des tâches apériodiques tout en garantissant les échéances des tâches périodiques. De nombreuses solutions ont été proposées ces vingt dernières années. On distingue les solutions basées sur la réservation de ressources, les serveurs de tâches, des solutions exploitant les instants d'inactivité du système, comme les algorithmes de vol de temps creux. La spécification Java pour le temps réel (RTSJ) voit le jour dans les années 2000. Si cette norme répond à de nombreux problèmes liés à la gestion de la mémoire ou à l'ordonnancement des tâches périodiques, celui de l'ordonnancement mixte de tâches périodiques et apériodiques n'est pas abordé. Nous proposons dans cette thèse d'apporter les modifications nécessaires aux algorithmes principaux d'ordonnancement mixte, le Polling Server (PS), le Deferrable Server (DS) et le Dynamic Approximate Slack Stealer (DASS) en vue de leur implantation avec RTSJ. Ces algorithmes ne peuvent en effet être implantés directement tels qu'ils sont décrits, car ils sont trop liés à l'ordonnanceur du système. Nous proposons des extensions aux APIs RTSJ existantes pour faciliter l'implantation de ces mécanismes modifiés, et nous fournissons les interfaces utiles à l'ajout d'autres solutions algorithmiques. Nous proposons également des modifications sur les APIs existantes de RTSJ afin de répondre aux problèmes d'intégration et d'implantation d'algorithmes d'analyse de faisabilité. Nous proposons enfin un algorithme d'estimation des temps creux, le Minimal Approximate Slack Stealer (MASS), dont l'implantation au niveau utilisateur, permet son intégration dans RTSJ

Les travaux de cette thèse sont les fruits de collaboration depuis 2008 entre l'ICL et le Centre Ingénierie et Santé (CIS) de l'Ecole des Mines de Saint Etienne. CIS et ICL sont tous deux membres de l'Institut Fédératif de Recherche en Science, Ingénierie et Santé (IFRESIS) et participent tous deux aux travaux du Cancéropôle Lyon Auvergne Rhône-Alpes (CLARA) dont Franck Chauvin animait l'axe IV sur Epidémiologie, SHS, Information du Patient et Organisation des Soins. Cette thèse a été initiée avec la volonté de développer une recherche originale sur l'optimisation de la production de soins en cancérologie.Nous nous intéressons à différentes problématiques de la gestion de soins des patients dans un hôpital de jour en cancérologie. Nous visons à équilibrer au mieux les besoins journaliers en lits tout en prenant en compte l'adhérence aux protocoles de soins, les contraintes des oncologues et les aléas des flux de patients. Pour un hôpital de jour en oncologie, nous avons identifié et étudié les décisions suivantes : I. Le planning médical une fois par an afin de déterminer les périodes de travail des oncologues dans une semaine. Nous avons proposé une formulation originale sous forme d'un modèle de programmation linéaire en nombres mixtes (MIP) et une approche en 3-étapes. II. L'affectation des nouveaux patients qui détermine le jour de la chimiothérapie pour chaque patient entrant. Nous avons présenté trois stratégies de planification et nous avons décrit un algorithme de simulation pour évaluer ces stratégies de planification. Les stratégies de planification proposées exploitent les informations contenues dans les protocoles de soins des patients et utilisent l'optimisation Monte Carlo III. La planification des rendez-vous. Nous avons présenté deux méthodes pour la résolution de ce problème : une approche basée sur la relaxation Lagrangienne et une heuristique basée sur une optimisation par recherche localeIV. La planification des jours fériés : permet de remédier au problème des semaines comportant des jours fériés. Nous avons développé un modèle en programmation linéaire en nombres mixtes permettant de répartir rapidement la charge du jour férié sur les jours en amont et en aval sans trop dégradé l'efficacité du traitement, ni surcharger le travail de l'HDJ.

Ce document est la synthèse des travaux menés pour la résolution d'un problème d'ordonnancement, celui posé par le système temps-réel spectre (divers types de ressources, plusieurs ressources par type, relations de précedence, arrivées échelonnées, dates critiques...) La méthode utilisée pour parvenir a la solution et les réflexions successives y sont décrites et analysées. de plus, ce travail décrit l'algorithme solution depuis sa définition jusqu'à sa programmation, en passant par la démonstration de sa validité.

Cette thèse présente de nouveaux résultats liant la théorie des systèmes dits insensibles à la latence, à une sous-classe des réseaux de Pétri dénommée Marked Event Graph et son extension dite Synchronous Data Flow. Ces travaux sont intimement associés avec le problème d'ordonnancement général dénommé problème central répétitif. Nous introduisons les modèles synchrones, Marked Event Graphs, Synchronous Data Flow (SDF) et Latency Insensitive. Après, nous discutons des liens existants entre les modèles synchrones, Marked Event Graphs et Latency Insensitive ; nous montrons que le modèle Latency Insensitive est un cas particulier du modèle Marked Event Graph. Nous présentons ensuite une implémentation vérifiée formellement de Latency Insensitive. Après, nous rappelons un résultat connu : tout Marked Event Graph ayant au moins une partie fortement connexe (et s'évaluant avec une règle d'exécution As Soon As Possible (ASAP)) a un comportement ultimement répétitif : c'est à dire qu'il existe un ordonnancement statique. À partir de ce résultat, nous construisons une technique d'ordonnancement particulière dénommée Égalisation qui altère virtuellement la topologie des communications du système afin de ralentir des chemins trop rapides en rajoutant des "registres", tout en conservant les performances en terme de débit du système originel. Enfin, nous introduisons une notion de contrôle limité au modèle Latency Insensitive, avec des noeuds appelés select et merge dont les conditions sont connueset indépendantes des flots de données, plus exactement les conditions d'aiguillage des données sont dirigées par des mots binaires ultimement périodiques (comme dans le cadre de l'ordonnancement statique). Nous effectuons ensuite une abstraction sur le modèle SDF afin de déterminer si le modèle accepte un ordonnancement où la taille de toute place est bornée. Nous pouvons vérifier ensuite la vivacité du système grâce à une simulation, si le modèle originel disposait d'au moins d'une partie fortement connexe. Finalement, nous concluons et discutons des possibilités de travaux futurs.

Afin de résoudre les problèmes liés à l'intégration d'un nombre croissant d'appareils programmables, nous proposons un langage d'agents mobiles. Ces agents mobiles sont capables de migrer d'un appareil ou ordinateur à l'autre afin d'exploiter au mieux ses ressources, ce qui permet de profiter au mieux des capacités de chaque appareil à partir d'un unique programme. Ce langage est ULM: Un Langage pour la Mobilité. Nous présentons dans cette thèse ses fonctionnalités, ses particularités, ainsi que sa mise en œuvre. ULM est un dérivé du langage Scheme, auquel nous avons ajouté les fonctionnalités liées à la mobilité ainsi qu'à l'interaction entre les agents mobiles. ULM possède un ensemble de primitives permettant la création d'agents à mobilité forte, avec un ordonnancement coopératif déterministe, et des primitives de contrôles telles que la suspension ou la préemption faible. Nous présentons dans cette thèse l'intégration de ces primitives dans le langage Scheme, ainsi que leur interaction et l'ajout de certaines nouvelles primitives telles que la préemption forte ou la migration sûre. Nous présentons ensuite la sémantique dénotationnelle du langage et sa mise en œuvre au moyen d'un compilateur vers code-octet, et de deux machines virtuelles: une écrite en Bigloo Scheme pour exécution sur des ordinateurs traditionnels, l'autre écrite en Java ME pour les téléphones portables. Nous présentons ensuite l'utilisation possible d'ULM comme remplacement de programmes écrits pour des boucles d'évènements, l'interface entre ULM et des langages externes, quelques exemples d'utilisation d'ULM, puis les travaux futurs avant de conclure.

Le contexte de notre travail s'intéresse à l'ordonnancement des activités de maintenance dans les systèmes de production. L'objectif de la thèse concerne l'élaboration de méthodes de résolution minimisant un critère regroupant les deux aspects production et maintenance. Les règles de priorité ainsi que les algorithmes génétiques ayant fait leur preuve dans le domaine seront à la base de notre étude. Etude faite tout d'abord sur un problème à une machine puis étendue au cas du Flow Shop. Notre contribution comporte tois volets. Le premier volet prend appui sur les solutions générées à l'aide d'une règle de dominance reliant les tâches de production et les tâches de maintenance. Le deuxième volet propose un algorithme par séparation et évaluation permettant de générer des ordonnancements de permutation du problème conjoint de la production et de la maintenance au sein du FLow Shop à deux machines. Le troisième volet étend l'étude au cas du Flow Shop à plusieurs machines. Nous proposons dans ce cas un algorithme génétique avec un codage approprié. Cet algorithme a l'avantage de balayer tout l'espace de recherche et par conséquent de générer des ordonnancements de très bonne qualité. Nous optons pour la maintenance préventive systématique pour l'appliquer dans notre étude. L'une des difficultés majeures de ce type de maintenance est le choix des périodes d'interventions optimales. Nous proposons dans ce cadre une méthode de choix de périodes systématiques.