Les travaux de recherche effectués dans le cadre de cette thèse concernent un problème delotissement et de séquencement pour une ligne de production imparfaite. Deux types d'aléas sont prisen compte : le rendement aléatoire (à cause des rebuts) et le temps d'exécution aléatoire (à cause despannes machines). Les temps de changement de série dépendant de la séquence des produits sontégalement pris en compte.Le problème est issu de d'une fabrication automatisée (usine-automate) des circuits impriméset il a été posé lors de la conception du système de gestion de production de l'atelier fabriquant lespartons conducteurs de plusieurs types. Étant donné que l'usine était complètement automatisée,l'atelier (comme le reste de l'usine) travaillait la plupart de la journée sans personnel autre que celui demaintenance, alors il fallait construire un planning de production pour les 24 heures suivantes. Ceplanning devait être répété chaque jour. Le problème consistait à définir les quantités optimales deproduits à traiter (tailles de lots) et l'ordre de passage des lots dans une ligne de production afind'optimiser un critère.Le problème traité appartient à trois domaines de recherche: 1) lotissement optimale pour lessystèmes de production imparfaits (ou lotissement sous incertitudes); 2) ordonnancement etlotissement déterministe; 3) ordonnancement avec des temps ou (et) coût de changement de série (setup).Dans la littérature scientifique nous trouvons beaucoup d'exemples de problèmes appartenant auun ou à l'intersection de deux de ces domaines. Par contre, nous n'avons pas trouvé les travaux quitraites de problèmes identiques au notre.Etant donné que le problème est trop compliqué tel qu'il est, nous avons cherché des façonsde son modélisation qui nous permettrons le résoudre. Nous avons trouvé trois cas où le problèmeinitial peut être décomposé en plusieurs parties, chacune entre lesquelles peut être transformé dans unproblème connu de la Recherche Opérationnelle. Ensuite nous avons travaillé que sur la partielotissement du problème décomposé tout en montrant comment les autres partis peuvent être résolus.Les problèmes de ce type sont très importants pour l'optimisation d'une chaine logistique.Ces résolutions aident d'organiser la production à la manière efficace, que permet aux entreprises defaire des gains financiers importants.

Les systèmes contrôlés en réseau (SCR) ont fait l'objet de nombreux travaux de recherche au cours des dernières années, principalement pour ce qui concerne la synthèse de lois de commande. Les systèmes contrôlés en réseau présentent de nombreux avantages, notamment en terme de flexibilité, mais différent problèmes se posent quand une boucle de contrôle est fermée par un réseau de communication. (ex. retards et des pertes, contraintes de communication). Diagnostic et tolérance aux défauts sont des enjeux importants pour les systèmes de contrôle, particulièrement dans les systèmes de sécurité fondamentaux. La théorie et l'application des approches classiques de diagnostic et tolérance aux défauts doivent être re-visités lorsqu'il s'agit de SCR. L'objectif de cette thèse est de proposer de nouvelles approches de diagnostic pour les systèmes contrôlés en réseau en considérant la perte de paquets et la contrainte de communication. De plus, les algorithmes de l'ordonnancement et de diagnostic proposés sont implémentés dans un mini hélicoptère. Nous considérons d'abord les problèmes de perte de paquets et de contrainte de communication pour ensuite adapter un modèle où la détection des défauts et l'allocation des ressources de communication sont fortement liés. En interprétant ce modèle comme un modèle périodique, nous formalisons et résolvons le problème de détection et localisation de défauts avec un ordonnancement périodique et hors-ligne. L'approche proposée garantit la robustesse des résidus aux perturbations ainsi que perte de paquets sur la commande du système. Il est parfois nécessaire de fournir une séquence de communication prédéfinie avant de concevoir le système de détection de défauts. IL spécifie l'ordre de l'accès des capteurs et des actionneurs au réseau. Cependant, le choix d'une séquence de communication dépend forcément à la structure du système. Un algorithme graphique proposé dans cette thèse garantit la génération de séquences de communication permettant de préserver certaines propriétés structurelles du système. En outre, cet algorithme peut être utilisé sur les systèmes incertains et assez grands. Traditionnellement, allocation des ressources et l'ordonnancement sont basés sur les stratégies hors ligne. Mais la performance du système de diagnostic ne peut pas être garantie sous l'ordonnancement hors-ligne, si le système est objet à des perturbations imprévisibles. En plus, L'ordonnancement en ligne nécessite une grande charge de calcul qui ne peut être toujours possible en cas de système embarqué. Par conséquent, un ordonnancement semi-en ligne qui permet de préserver les avantages de l'ordonnancement en ligne et évite certaines limitations d'ordonnancement hors ligne peut être considéré comme une solution de compromis. Les drones ou UAVs pour Unmanned Aerial Vehicules font actuellement l'objet de beaucoup de recherches en raison de leurs utilités dans des situations qui nécessitent des opérations autonomes ou autopiloté. Ils peuvent être classés comme des systèmes dynamiques rapides. Par conséquent, ils peuvent être banc d'essai idéal pour étudier les effets du réseau sur les performances de contrôle/diagnostique en boucle fermée. Le dernier chapitre de cette thèse est dédié à implémentation d'une stratégie de commande tolérante aux défauts et les approches de détection et localisation des défauts proposées dans les chapitres précédents sur le drone.

Les services de soins hospitaliers sont soumis à de nombreux évènements de natures aléatoires rendant leur gestion et leur pilotage difficiles. Ces difficultés organisationnelles reposent essentiellement sur l'incertitude permanente pesant sur les évolutions futurs, principalement en termes d'arrivées et de départs de patients. Pourtant, une prise en charge rapide et efficace des patients est primordiale pour des services tels que les urgences. Ces services doivent pouvoir placer rapidement leurs patients ce qui n'est possible uniquement si (i) les arrivées ont été anticipées et des places sont laissées vacantes dans les services pour recevoir les patients urgents et/ou (ii) le planning d'occupation des services est construit de telle manière que l'insertion d'un nouveau patient est facilitée.Notre objectif va être de gérer les flux de patients séjournant dans les services de courts-séjours de l'hôpital, depuis le choix d'admission d'un nouveau patient jusqu'à sa sortie, et ce, en s'inspirant des deux postulats précédant. A l'aide de modèles d'optimisation stochastique, une succession de problèmes de décisions, ayant pour but de garantir le bon fonctionnement des structures hospitalières, est résolue. Une hiérarchie en trois niveaux est appliquée pour résoudre le problème de gestion: 1. Planification des admissions des patients réguliers, 2. Affectation des patients aux unités de soins et insertion des urgences, 3. Affectation des patients d'un service aux chambres.Les études de cas sont basées sur les données d'un établissement partenaire, le Centre Hospitalier de Firminy (France).

Les langages formels sont des séquences sur un ensemble discret de symboles appelé alphabet. On les spécifie souvent par des formules dans une certaine logique, par des expressions rationnelles ou bien par des automates discrets de types variés. La théorie actuelle est principalement qualitative, dans le sens où ses objets sont des séquence sur un temps discret, non-métrique, dans le sens où l'acceptation d'une séquence sur un automate dépend du fait que l'on visite ou non un état accepteur, et enfin dans le sens où la comparaison de langages est plus souvent considérée en termes d'inclusion, plutôt qu'en termes de mesures quantitatives. Cette thèse contribue à l'étude de ces aspects souvent négligés en présentant des résultats fondamentaux dans trois nouvelles classes de problèmes quantitatifs sur les langages formels. Dans la première partie, nous étudions une classe de problèmes d'ordonnancement qui combine les aspects structurels associés aux dépendances entre tâches avec les aspects dynamiques liés au fait qu'un flux de requêtes arrive en continu pendant l'exécution. Nous montrons que, dans cette classe de problèmes, certains flux, pourtant admissibles dans le sens que les requêtes ne représentent pas plus de travail que ce que les machines peuvent traiter, ne peuvent pas être ordonnancé avec une latence bornée. Cependant nous développons une politique d'ordonnancement que peut garantir une accumulation de retard bornée pour tout flux de requêtes admissible, même sans le connaître à l'avance. Nous montrons que si les flux sont sous-critiques, alors cette même politique peut garantir une latence bornée. En vérification quantitative, les états et transitions d'un système peuvent être associés à des coûts, et ceux-ci utilisés pour associer des coûts moyens aux comportements infinis. Dans cette seconde partie, nous proposons de définir des omega-langages par des requêtes booléennes sur les coûts moyens. Des spécifications concernant des moyennes, tels que " le taux de perte moyen de messages est inférieur à un certain seuil " ne sont pas omega-régulières, mais exprimables dans notre modèle. Ainsi, nous étudions l'expressivité et la complexité de Borel de telles spécifications. Nous montrons que pour la clôture par intersection, il est nécessaire de considérer des coûts multi-dimensionnels. Nous mettons en évidence que dans le cas général, les conditions d'acceptation portent sur l'ensemble des points d'accumulation de la séquence des coûts moyens des préfixes d'une exécution, et nous donnons une caractérisation précise de tels ensembles. Nous proposons une classe de langages de coût moyen à seuils multiples, comparant les coordonnées minimales et minimales des points de cet ensemble à des constantes. Nous montrons enfin que cette classe est close par opérations booléennes et analysable. Enfin, dans le dernier volet, nous définissons deux mesures pour un langage temporisé : le volume de ses sous-langages de mots à nombre d'événements fixe et l'entropie (vitesse de croissance), mesure asymptotique pour un nombre non borné d'événements. Ces mesures peuvent être utilisées pour la comparaison quantitative de langages, et l'entropie peut être vue comme la quantité d'information par événement dans un mot typique du langage temporisé. Pour les langages acceptés par des automates temporisés déterministes, nous donnons une formule exacte pour le volume. Ensuite, nous caractérisons l'entropie, en utilisant des méthodes d'analyse fonctionnelle, en tant que logarithme du rayon spectral d'un opérateur intégral positif. Nous établissons plusieurs méthodes pour calculer l'entropie : une symbolique pour les automates que nos appelons " à une horloge et demie ", et deux numériques : une utilisant les techniques d'analyse fonctionnelle, l'autre basée sur la discrétisation. Nous donnons une interprétation de l'entropie en théorie de l'information en termes de complexité de Kolmogorov.

Ce travail concerne la production cyclique de pièces identiques dans un flow-shop robotisé. La Conjecture des 1-cycles, proposée par Sethi et al., suppose que le taux maximum de production peut être atteint en répétant un cycle particulier qui produit une seule pièce. Cette conjecture simplifie la recherche du meilleur cycle de production. Nous présentons de nouvelles preuves (approche par les graphes et approche algébrique) de la validité de cette conjecture pour des cellules à 2 et 3 machines et nous montrons qu'elle est fausse à partir de 4 machines. Nous délimitons ensuite plus précisément son cadre de validité en imposant des restrictions sur les paramètres : distances inter-machines égales ou temps d'usinage égaux. Puis, nous étudions d'autres formes de cellules robotisées en relaxant des contraintes de la cellule robotisée de base. La première variante est l'association de l'entrée et de la sortie de la cellule. Nous proposons quelques remarques sur la recherche du meilleur cycle de production. La deuxième variante est le HSP (Hoist Scheduling Problem) : le temps pendant lequel une pièce peut rester sur une machine admet une borne supérieure. Nous montrons que des propriétés des cellules robotisées ne peuvent pas être étendues au HSP. La troisième variante est l'ajout de zones de stockage entre les machines. Nous montrons que la Conjecture des 1-cycles est vraie et nous analysons le gain par rapport à une cellule sans stockage. Enfin, nous supposons que les distances inter-machines sont quelconques. Nous montrons que trouver le meilleur cycle de production d'une pièce est un problème NP-complet. Ce travail a permis de résoudre complètement une conjecture ouverte depuis 1989 et de décrire l'influence de la relaxation de certaines contraintes des cellules robotisées sur la recherche du meilleur cycle de production. La principale perspective est, pour les cas où la conjecture est fausse, de trouver le meilleur cycle de production.

Ce travail de thèse de doctorat traite de l'étude d'un problème d'ordonnancement NP-difficile au sens fort à contraintes de ressource : le problème de la programmation des déplacements de processus. Ce problème, issu de l'industrie des télécommunications, est lié à l'opérabilité de certains systèmes temps réel répartis à haute disponibilité tels le BSCe3, un autocommutateur pour la téléphonie cellulaire commercialisé par Nortel.<br />En quelques mots, ce problème consiste, étant donnée une répartition arbitraire admissible de processus sur les processeurs d'un système réparti, à trouver une séquence d'opérations (migrations de processus sans effet sur le service ou arrêts temporaires) de moindre impact par le biais de laquelle une autre répartition arbitraire, et fixée à l'avance, peut être obtenue. La principale contrainte réside dans le fait que la capacité des processeurs du système ne doit pas être dépassée durant la reconfiguration.<br />Nous avons abordé ce problème d'ordonnancement sous différents angles. Tout d'abord, nous avons établi son caractère NP-difficile au sens fort et exhibé quelques cas particuliers polynomiaux. Puis, sur le plan de la résolution exacte dans le cas général, nous avons conçu deux algorithmes de recherche arborescente : le premier trouve ses fondements dans l'étude de la structure combinatoire du problème, le second dans des considérations polyédrales. De nombreux résultats expérimentaux illustrent la pertinence pratique de ces deux algorithmes. Enfin, en raison des contraintes imposées par le caractère temps réel de notre application industrielle, nous avons mis au point un algorithme efficace de résolution approchée basé sur la métaheuristique du recuit simulé et, en capitalisant sur nos travaux en résolution exacte, empiriquement vérifié sa capacité pratique à produire des solutions acceptables, en un sens bien défini.

Dans cette thèse, nous avons développé de nouvelles méthodes d'aide à la décision pour l'ordonnancement dans la chaîne logistique. Nous avons proposé des méthodes qui privilégient la coopération entre les différents acteurs de la chaîne logistique notamment en ce qui concerne la négociation avec les fournisseurs sur les dates d'arrivée des composants, et avec les clients sur les dates de livraisons des produits finis. Au niveau opérationnel, chaque acteur construit son ordonnancement par rapport à ses propres centres de production. Comme la production de produits finis dépend des composants, des négociations sont entamées entre les acteurs concernant les dates d'arrivées des composants (les fenêtres de temps). Une solution globale est obtenue par une approche itérative pour définir l'ordonnancement juste à temps minimisant la somme des pénalités (retards et avances par rapport aux dates fixées). Pour la résolution du problème d'ordonnancement juste à temps, local à chaque centre de production, nous avons proposé une méthode approchée basée sur les algorithmes génétiques. Chaque solution est évaluée grâce à un algorithme pseudo-polynomial basé sur le PERT coût. Un contrôle semi décentralisé est développé pour assurer la convergence des négociations. Par ailleurs, nous avons étudié un ensemble de problèmes concernant l'optimisation des transports dans les chaînes logistiques.

Cette thèse traite de l'ordonnancement dans les systèmes distribués. L'objectif est d'étudier l'impact de l'incertitude sur les ordonnancements et de proposer des techniques pour en réduire les effets sur les critères à optimiser. Nous distinguons plusieurs aspects de l'incertitude en considérant celle liée aux limites des méthodes employées (e.g., modèle imparfait) et celle concernant la variabilité aléatoire qui est inhérente aux phénomènes physiques (e.g., panne matérielle). Nous considérons aussi les incertitudes qui se rapportent à l'ignorance portée sur les mécanismes en jeu dans un système donné (e.g., soumission de tâches en ligne dans une machine parallèle). En toute généralité, l'ordonnancement est l'étape qui réalise une association ordonnée entre des requêtes (dans notre cas, des tâches) et des ressources (dans notre cas, des processeurs). L'objectif est de réaliser cette association de manière à optimiser des critères d'efficacité (e.g., temps total consacré à l'exécution d'un application) tout en respectant les contraintes définies. Examiner l'effet de l'incertitude sur les ordonnancements nous amène à considérer les aspects probabilistes et multicritères qui sont traités dans la première partie. La seconde partie repose sur l'analyse de problèmes représentatifs de différentes modalités en terme d'ordonnancement et d'incertitude (comme l'étude de la robustesse ou de la fiabilité des ordonnancements).

Nous présentons dans ce mémoire de thèse d'habilitation une étude sur des algorithmes distribués asynchrones de contrôle et d'ordonnancement. Un algorithme de contrôle établit une structure virtuelle sur un réseau de sites communicants. Nous faisons le choix %délibéré de faire un minimum d'hypothèses sur les connaissances de chaque site. De même, nous évitons autant que possible d'utiliser des mécanismes conduisant à des attentes qui peuvent être pénalisantes comme, par exemple, l'utilisation de synchroniseurs. Ces choix conduisent à privilégier les modes de fonctionnement essentiellement locaux. %dépendant le moins possible de l'état du reste du réseau. Nous introduisons toutefois une limite à cette démarche, dans ce travail, nous ne considérons que des algorithmes déterministes. Dans ces circonstances, un problème essentiel de l'algorithmique distribuée est l'établissement d'une structure de contrôle couvrant la totalité du réseau, dans laquelle chaque site distingue certains de ses voisins de façon spécifique. Après avoir rappelé des notions fondamentales en partie I, nous présentons dans la première partie, trois de nos algorithmes de construction d'arbre couvrant avec contraintes, ces dernières apportant une plus grande efficacité à la structure de contrôle établie. En particulier, nous considérons la contrainte de poids total minimum qui caractérise plutôt une recherche économique, celle de diamètre minimum qui concerne l'efficacité à la fois en temps mais aussi évidemment en messages et la contrainte de degré minimal qui permet par exemple d'utiliser des équipements d'interconnection moins coûteux. Dans la troisième partie nous présentons deux de nos heuristiques pour la résolution du problème de l'ordonnancement distribué en ligne, avec arrivées sporadiques, d'abord de tâches indépendantes puis de tâches avec dépendances non cycliques. Nous montrons que là encore, la structure d'arbre peut être utilisée de façon bénéfique. En particulier, dans des réseaux de taille arbitrairement grande, des arbres de plus courts chemins limités aux voisins relativement proches peuvent être utilisés pour définir un concept nouveau et prometteur ,: la Sphère de Calcul. Cette Sphère de Calcul limite le nombre de messages échangés et le temps de calcul. Tout au long de ce mémoire nous présentons des algorithmes nouveaux, voire pionniers dans leurs domaine. De nombreux développements sont possibles, certains déjà réalisés par nous-même ou par d'autres auteurs, d'autres sont des problèmes ouverts (recherche d'algorithmes optimaux par exemple).

Les travaux présentés dans cette thèse portent sur l'ordonnancement d'applications au sein d'un environnement de grille de calcul. Nous étudions comment mieux gérer les tâches au sein des intergiciels de grille, ceci dans l'objectif d'améliorer les performances globales de la plateforme. Les solutions que nous proposons se situent dans l'intergiciel, ce qui permet de conserver les architectures sous-jacentes sans les modifier. Dans un premier temps, nous proposons un mécanisme de réallocation permettant de prendre en compte dynamiquement les erreurs d'ordonnancement commises lors de la soumission de calculs. En effet, lors de la soumission sur une machine parallèle, il est souvent nécessaire de fournir une estimation du temps d'exécution afin que celle-ci puisse effectuer un ordonnancement. Cependant, les estimations ne sont pas précises et les décisions d'ordonnancement sont sans cesse remises en question. Le mécanisme de réallocation proposé permet de prendre en compte ces changements en déplaçant des calculs d'une machine parallèle à une autre. Le second point auquel nous nous intéressons dans cette thèse est l'ordonnancement d'une application de climatologie sur la grille. Afin de fournir les meilleures performances possibles nous avons modélisé l'application puis proposé des heuristiques spécifiques. Pour exécuter l'application sur une grille de calcul, l'intergiciel utilise ces connaissances sur l'application pour fournir le meilleur ordonnancement possible.