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.

Cette thèse se situe dans le contexte des réseaux de communication temps-réel et son objectif est de proposer une architecture de communication pour la sous-couche MAC, qui définit des mécanismes pour assurer les contraintes temporelles du trafic temps-réel. Tout d'abord, une classification des protocoles MAC temps-réel existants, en mettant en exergue l'aspect ordonnancement de flux de messages ou ordonnancement de stations, est effectuée. En particulier, le protocole "jeton temporisé" et des mécanismes de la norme "ISA SP-50 / IEC-65C" sont détaillés. Ensuite, des contributions sur les mécanismes d'ordonnancement et les mécanismes protocolaires sont développées, à la fois en termes conceptuels et en termes de réflexions sur les normes existantes: proposition d'un algorithme non-préemptif ED avec, en particulier, une extension des conditions classiques d'ordonnançabilité; définition d'un algorithme de changement de mode de fonctionnement pour un système ordonnancé par l'algorithme RM; définition d'un protocole appelé "jeton temporisé régulier" qui améliore les performances temps-réel du protocole "jeton temporisé"; définition des conditions d'ordonnançabilité du trafic apériodique urgent dans le réseau FIP et proposition de deux profils de fonctionnement temps-réel pour le réseau Profibus. Enfin, nous proposons, modélisons avec le modèle "Réseaux de Petri Temporisés Stochastiques" et évaluons une architecture de communication pour la sous-couche MAC de réseaux locaux temps-réel. Cette architecture met en ¿uvre, de manière centralisée, un ordonnancement conjoint des trafics périodique et apériodique temps-réel, sur la base d'un algorithme non-préemptif pour le trafic périodique et d'une technique de jeton temporisé pour le trafic apériodique temps-réel. L'analyse permet, d'une part, d'évaluer l'ordonnancement en termes de taux d'utilisation permis et des limites de l'ordonnançabilité et, d'autre part, de montrer tout l'intérêt des modèles "Réseaux de Petri Temporisés Stochastiques" pour représenter et évaluer automatiquement l'ordonnançabilité d'un ensemble de configurations de flux de messages.

Cette thèse traite des lignes de traitement de surface qui sont des lignes dans lesquelles les pièces sont immergées dans une succession de cuves. Chaque cuve contient des bains qui affectent les propriétés mécaniques ou électriques des pièces. Ce type de ligne est utilisé, par exemple, pour la galvanoplastie. Les pièces sont montées sur des porteurs et transportées d'une cuve à l'autre par un robot. Le temps opératoire (ou temps pendant lequel la pièce reste dans la cuve) est borné. La borne inférieure est le temps minimum qui permet le traitement et la borne supérieure dépend du type de traitement (attaque acide, rinçage...).<br />Un objectif classique est de trouver les mouvements du robot qui maximisent la productivité, ce problème est communément appelé “hoist scheduling problem” (HSP). Lors de ce travail nous nous sommes attachés à une production cyclique. Nous avons proposé dans le cas d'une ligne à deux cuves une méthode permettant d'obtenir les cycles optimaux. Nous avons démontré, pour le cas d'une ligne équilibrée à trois cuves pour une production mono-produit, les caractéristiques des cycles optimaux ainsi qu'une méthode pour les obtenir. Ensuite, nous avons étudié le problème sur quatre machines dans le cas où les temps de trempe sont égaux et sans attente. Nous avons proposé les cycles optimaux dans le cas d'une production mono-produit. Enfin nous avons proposé une conjecture sur les cycles optimaux et en avons démontré certaines parties, dans le cas d'une ligne équilibrée avec un nombre de cuves quelconque et où les marges sur les temps de process sont nulles.