• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 103
  • 51
  • 14
  • Tagged with
  • 170
  • 170
  • 83
  • 73
  • 56
  • 43
  • 39
  • 38
  • 36
  • 35
  • 34
  • 30
  • 29
  • 27
  • 26
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
131

Modélisation et guidage robuste et autonome pour le problème du rendez-vous orbital

Kara-Zaitri, Mounir 17 November 2010 (has links) (PDF)
Dans cette thèse, nous nous intéressons à deux composantes fondamentales de l'opération du rendez-vous orbital : la navigation relative et le guidage à consommation minimale de carburant. La première partie est consacrée à la modélisation du mouvement relatif de satellites dans un cadre linéaire. Une analyse bibliographique approfondie ainsi que les développements d'une méthode de modélisation et d'une transformation de variables d'état du mouvement relatif sont proposées dans cette partie. Ces développements sont entrepris dans le but de fournir des outils de navigation relative fiables et précis même en présence de perturbations orbitales. Le guidage est abordé dans la seconde partie de la thèse à travers l'élaboration de plusieurs algorithmes de génération de plans de manSuvres pour la mise en Suvre du rendez-vous en temps fixé. Chacun des algorithmes développés est fondé sur des outils théoriques différents tels que les méthodes indirectes de résolution de problèmes de commande optimale basées sur le principe du maximum ou les techniques directes exploitant la discrétisation des problèmes de commande optimale et la programmation linéaire. L'utilisation de ces outils permet de couvrir des objectifs divers, notamment la minimisation de la consommation de carburant et la robustesse vis-à-vis des erreurs de navigation. D'autres algorithmes sont conçus dans le but d'améliorer leur embarcabilité à travers l'utilisation des bases de la mécanique spatiale. Un ensemble de tests de validation et comparaison est réalisé, portant sur des missions réelles ou des exemples académiques issus de la littérature et permettant de mettre en valeur les avantages pratiques les plus pertinents des algorithmes développés.
132

Quelques sujets en contrôle déterministe et stochastique : méthodes de type LP, PDMP associés aux réseaux de gènes, contrôlabilité

Goreac, Dan 16 September 2013 (has links) (PDF)
Le but de cette synthèse est de présenter mon activité de recherche couvrant la période de temps écoulée à partir de l'année terminale de ma thèse (c'est à dire, la période octobre 2008 - février 2013). Mes thèmes de recherche correspondent, en majeure partie, à trois directions principales, chacune présentée dans une section dédiée : - méthodes de programmation linéaire dans l'étude des problèmes de contrôle déterministe ou stochastique ; - méthodes de contrôle des processus Markoviens déterministes par morceaux et leurs applications dans la théorie des réseaux stochastiques de gènes. - propriétés de contrôlabilité des systèmes linéaires stochastiques et sujets connexes. Dans le premier chapitre, nous étudions plusieurs classes de problèmes de contrôle déterministe ou stochastique à coût discontinu. Dans le contexte stochastique, nous considérons le problème de type Mayer et l'arrêt optimal des diffusions contrôlées (correspondant à l'article [G10]), les principes de la programmation dynamique (correspondant à l'article [G6]), ainsi qu'une classe de problèmes de contrôle impliquant des contraintes d'état (correspondant à l'article [G2]). Nous étudions également : des problèmes de contrôle à coût escompté et en horizon infini, ainsi que la moyennisation en temps long (correspondant à [G12]), des systèmes régis par des inégalités variationnelles stochastiques (dans [G3]) et une caractérisation de type Zubov pour les domaines de stabilité asymptotique (toujours dans [G3]). Nous investiguons l'existence d'une fonction valeur limite pour une classe de problèmes de contrôle stochastique sous des hypothèses de non-expansivité, ainsi que des théorèmes Tauberiennes uniformes (correspondant à [G19]). Dans le cadre déterministe, nous considérons la linéarisation et les principes de la programmation dynamique pour des problèmes de type coût supremum (ce qui correspond à [G9]) et pour des systèmes à contraintes d'état (dans [G1]). Nous proposons une méthode de linéarisation pour des problèmes de type min-max (correspondant à [G18]). Le point commun entre ces articles réside dans la méthode employée basée sur des formulation linéaires et des techniques de viscosité. Nous présentons également des résultats de viabilité pour les perturbations singulières des systèmes contrôlés (correspondant à [G13]). Le deuxième chapitre est axé sur quelques contributions à la théorie des processus de Markov déterministes par morceaux (PDMP, acronyme anglais de "piecewise deterministic Markov process"). Nous investiguons des conditions géométriques pour la viabilité et l'invariance des ensembles fermés par rapport aux dynamiques PDMP contrôlées (correspondant à l'article [G5]). Nous proposons également des formulations linéaires pour certains problèmes de contrôle dans ce contexte (correspondant aux articles [G8] et [G4]). Ces résultats permettent d'en inférer certaines conditions d'atteignabilité (dans l'article [G5]) ainsi que de caractériser les domaines de stabilité asymptotique en généralisant la méthode de Zubov (dans l'article [G4]). Les résultats théoriques sont appliqués à une classe de systèmes associés à des réseaux stochastiques de gènes (des modèles On/Off, le modèle proposé par Cook pour l'haploinsuffisance, ainsi que le modèle de Hasty pour la bistabilité du phage lambda). Le dernier chapitre présente l'étude de différentes classes de contrôlabilité pour des systèmes linéaires de type diffusion à sauts (correspondant à l'article [G7]) ou des systèmes linéaires de contrôle à dynamique champs-moyen (correspondant à l'article [G20]). Les arguments font intervenir des techniques de viabilité ainsi que des équations différentielles de type Riccati. Une première étape dans l'étude des propriétés de contrôlabilité des systèmes ayant comme espace d'état un espace d'Hilbert est franchie dans l'article [G11]. Nous y proposons une approche de type quasi-tangence dans l'étude de la propriété de (presque)viabilité des systèmes semi-linéaires dans un cadre infini-dimensionnel. Nous avons essayé de rendre le manuscrit aussi autonome que possible. Pour en assurer la lisibilité, nous avons également essayé de garder l'indépendance des chapitres. Afin de garder une dimension raisonnable du manuscrit, nous avons fait le choix de limitation de la redondance. Pour cette raison, les problèmes de contrôle sous contraintes d'état ont été présentés uniquement dans le contexte stochastique. Aussi, les détails précis de la méthode de Zubov ont été spécifiés uniquement dans le cas des processus Markoviens déterministes par morceaux et les contributions aux diffusions Browniennes ont été seulement mentionnées.
133

Positionnement robuste et précis de réseaux d’images.

Moulon, Pierre 10 January 2014 (has links) (PDF)
Calculer une représentation 3D d'une scène rigide à partir d'une collection d'images est aujourd'hui possible grâce aux progrès réalisés par les méthodes de stéréo-vision multi-vues, et ce avec un simple appareil photographique. Le principe de reconstruction, découlant de travaux de photogrammétrie, consiste à recouper les informations provenant de plusieurs images, prises de points de vue différents, pour identifier les positions et orientations relatives de chaque cliché. Une fois les positions et orientations de caméras déterminées (calibration externe), la structure de la scène peut être reconstruite. Afin de résoudre le problème de calcul de la structure à partir du mouvement des caméras (Structure-from-Motion), des méthodes séquentielles et globales ont été proposées. Par nature, les méthodes séquentielles ont tendance à accumuler les erreurs. Cela donne lieu le plus souvent à des trajectoires de caméras qui dérivent et, lorsque les photos sont acquises autour d'un objet, à des reconstructions où les boucles ne se referment pas. Au contraire, les méthodes globales considèrent le réseau de caméras dans son ensemble. La configuration de caméras est recherchée et optimisée pour conserver au mieux l'ensemble des contraintes de cyclicité du réseau. Des reconstructions de meilleure qualité peuvent être obtenues, au détriment toutefois du temps de calcul. Cette thèse propose d'analyser des problèmes critiques au cœur de ces méthodes de calibration externe et de fournir des solutions pour améliorer leur performance (précision, robustesse, vitesse) et leur facilité d'utilisation (paramétrisation restreinte). Nous proposons tout d'abord un algorithme de suivi de points rapide et efficace. Nous montrons ensuite que l'utilisation généralisée de l'estimation robuste de modèles paramétriques a contrario permet de libérer l'utilisateur du réglage de seuils de détection, et d'obtenir une chaine de reconstruction qui s'adapte automatiquement aux données. Dans un second temps, nous utilisons ces estimations robustes adaptatives et une formulation du problème qui permet des optimisations convexes pour construire une chaine de calibration globale capable de passer à l'échelle. Nos expériences démontrent que les estimations identifiées a contrario améliorent de manière notable la qualité d'estimation de la position et de l'orientation des clichés, tout en étant automatiques et sans paramètres, et ce même sur des réseaux de caméras complexes. Nous proposons enfin d'améliorer le rendu visuel des reconstructions en proposant une optimisation convexe de la consistance colorée entre images.
134

Méthodes de résolution exactes et heuristiques pour un problème de tournées de techniciens

Mathlouthi, Ines 12 1900 (has links)
No description available.
135

Séquencement d’une ligne de montage multi-modèles : application à l’industrie du véhicule industriel / Mixed model assembly line sequencing : application in truck industry

Aroui, Karim 27 May 2015 (has links)
Dans cette thèse, nous considérons le problème du séquencement sur une ligne de montage multi-modèles de véhicules industriels. Pour équilibrer au mieux la charge dynamique des opérateurs, la minimisation de la somme des retards à l’issue de chaque véhicule est proposée.Deux approches peuvent être utilisées pour optimiser le lissage de charge dans un problème de séquencement : l’utilisation directe des temps opératoires ou le respect de règles. La plupart des travaux appliqués à l’industrie automobile utilisent l’approche de respect de règles. Une originalité de ce travail est d’utiliser l’approche de la prise en compte directe des temps opératoires.L’étude de la littérature de ce problème a dévoilé deux lacunes dans les travaux précédents : l’essentiel des travaux modélisent un seul type d’opérateurs d’une part, et proposent des heuristiques ou des métaheuristiques pour résoudre ces problèmes, d’autre part. L’originalité de ce travail est de tester des méthodes exactes pour des instances industrielles et de modéliser le fonctionnement de trois différents types d’opérateurs spécifiques au cas industriel.Deux méthodes exactes sont développées : la programmation linéaire mixte et la programmation dynamique. Une étude expérimentale des facteurs de complexité sur des instances académiques des deux modèles est développée. Les modèles sont aussi testés sur des instances du cas d’étude.Par ailleurs, le problème est traité par deux méthodes approchées : une heuristique basée sur la programmation dynamique d’une part, et des métaheuristiques (algorithme génétique, recuit simulé et un couplage des deux) d’autre part. Les deux approches sont testées sur des instances académiques et des instances du cas d’étude.Ce travail a permis d’apporter une solution intéressante d’un point de vue industriel puisqu’il prend en compte les caractéristiques de la ligne de montage (opérateurs spécifiques) et améliore significativement la qualité du séquencement en un temps de calcul raisonnable. / In this thesis, the problem of sequencing mixed model assembly lines (MMAL) is considered. Our goal is to determine the sequence of products to minimize the work overload. This problem is known as the mixed model assembly line sequencing problem with work overload minimization (MMSP-W). This work is based on an industrial case study of a truck assembly line.Two approaches can be used to minimize the work overload: the use of task operation times or the respect of sequencing rules. Most of the earlier works applied in car industry use the latter approach. The originality of this work is to employ the task operation times for the generation of the product sequence in a MMAL.The literature review has highlighted two main gaps in previous works: most of the papers consider a single type of operators, and propose heuristics or metaheuristics to solve the problem. The originality of this work is to test exact methods for industrial case instances and to model three different types of operators.Two exact methods are developed: the mixed integer linear programming and dynamic programming. The models are tested on industrial case study instances. An experimental study is developed for both approaches in order to understand the complexity factors.Moreover, the problem is treated by two approximate methods: a heuristic based on dynamic programming and metaheuristics (genetic algorithm, simulated annealing and a hybrid method based on both genetic algorithm and simulated annealing). All approaches are tested on academic instances and on real data from the industrial case study.
136

Traitement des objets 3D et images par les méthodes numériques sur graphes / 3D object processing and Image processing by numerical methods

El Sayed, Abdul Rahman 24 October 2018 (has links)
La détection de peau consiste à détecter les pixels correspondant à une peau humaine dans une image couleur. Les visages constituent une catégorie de stimulus importante par la richesse des informations qu’ils véhiculent car avant de reconnaître n’importe quelle personne il est indispensable de localiser et reconnaître son visage. La plupart des applications liées à la sécurité et à la biométrie reposent sur la détection de régions de peau telles que la détection de visages, le filtrage d'objets 3D pour adultes et la reconnaissance de gestes. En outre, la détection de la saillance des mailles 3D est une phase de prétraitement importante pour de nombreuses applications de vision par ordinateur. La segmentation d'objets 3D basée sur des régions saillantes a été largement utilisée dans de nombreuses applications de vision par ordinateur telles que la correspondance de formes 3D, les alignements d'objets, le lissage de nuages de points 3D, la recherche des images sur le web, l’indexation des images par le contenu, la segmentation de la vidéo et la détection et la reconnaissance de visages. La détection de peau est une tâche très difficile pour différentes raisons liées en général à la variabilité de la forme et la couleur à détecter (teintes différentes d’une personne à une autre, orientation et tailles quelconques, conditions d’éclairage) et surtout pour les images issues du web capturées sous différentes conditions de lumière. Il existe plusieurs approches connues pour la détection de peau : les approches basées sur la géométrie et l’extraction de traits caractéristiques, les approches basées sur le mouvement (la soustraction de l’arrière-plan (SAP), différence entre deux images consécutives, calcul du flot optique) et les approches basées sur la couleur. Dans cette thèse, nous proposons des méthodes d'optimisation numérique pour la détection de régions de couleurs de peaux et de régions saillantes sur des maillages 3D et des nuages de points 3D en utilisant un graphe pondéré. En se basant sur ces méthodes, nous proposons des approches de détection de visage 3D à l'aide de la programmation linéaire et de fouille de données (Data Mining). En outre, nous avons adapté nos méthodes proposées pour résoudre le problème de la simplification des nuages de points 3D et de la correspondance des objets 3D. En plus, nous montrons la robustesse et l’efficacité de nos méthodes proposées à travers de différents résultats expérimentaux réalisés. Enfin, nous montrons la stabilité et la robustesse de nos méthodes par rapport au bruit. / Skin detection involves detecting pixels corresponding to human skin in a color image. The faces constitute a category of stimulus important by the wealth of information that they convey because before recognizing any person it is essential to locate and recognize his face. Most security and biometrics applications rely on the detection of skin regions such as face detection, 3D adult object filtering, and gesture recognition. In addition, saliency detection of 3D mesh is an important pretreatment phase for many computer vision applications. 3D segmentation based on salient regions has been widely used in many computer vision applications such as 3D shape matching, object alignments, 3D point-point smoothing, searching images on the web, image indexing by content, video segmentation and face detection and recognition. The detection of skin is a very difficult task for various reasons generally related to the variability of the shape and the color to be detected (different hues from one person to another, orientation and different sizes, lighting conditions) and especially for images from the web captured under different light conditions. There are several known approaches to skin detection: approaches based on geometry and feature extraction, motion-based approaches (background subtraction (SAP), difference between two consecutive images, optical flow calculation) and color-based approaches. In this thesis, we propose numerical optimization methods for the detection of skins color and salient regions on 3D meshes and 3D point clouds using a weighted graph. Based on these methods, we provide 3D face detection approaches using Linear Programming and Data Mining. In addition, we adapted our proposed methods to solve the problem of simplifying 3D point clouds and matching 3D objects. In addition, we show the robustness and efficiency of our proposed methods through different experimental results. Finally, we show the stability and robustness of our methods with respect to noise.
137

Management de portefeuilles de projets : modèles multicritère d'évaluation, de sélection et d'argumentation / Project portfolio management : multicriteria models for evaluation, selection and argumentation

Dehouche, Nassim 14 May 2014 (has links)
Cette thèse traite du processus d’évaluation et de sélection de projets sur la base de critères multiples. Outre la capacité du modèle à permettre une identification efficace des meilleurs projets et leur intégration à un portefeuille, l’équité et la transparence sont des considérations importantes dans la conception de modèles d’appui à ce processus. Nous proposons un cadre de travail général pour l’évaluation de projets, Il reprend les codes de l’analyse SWOT, dont de nombreuses organisations orientées projets sont familières. Nos contributions apportent des éléments de réponse à la question de « l’après SWOT », à laquelle ces organisations peuvent éprouver des difficultés à répondre. Dans ce cadre de travail, nous introduisons et discutons un modèle de préférences permettant de mesurer l’importance des critères sur deux dimensions, représentant de manière indépendante leurs capacités de conviction et d’opposition. Suivant l’évaluation et en préalable à la sélection, le filtrage consiste à écarter les projets trop inadéquats. Nous proposons un mécanisme basé sur la dominance pour effectuer cette opération. Nous proposons, enfin, deux méthodes de sélection de projets, chacune étant basée sur une procédure d’agrégation multicritère originale. La première méthode, SPADE (pour Structure de Préférence pour l’Aide à la Décision) est une approche de surclassement, destinée à des contextes où les préférences exprimées concernent essentiellement les projets individuels, et dans lesquels les décisions concernant un projet peuvent être argumentées en référence à des projets tiers. Nous garantissons la validité théorique de SPADE, en amont, ce qui permet un temps de mise en œuvre réduit et une utilisation en temps réel. En pratique, nous illustrons l’application de SPADE, en la comparant à deux autres approches d’aide multicritères à la décision, MAUT et ELECTRE, en mettant en exergue ses spécificités. La seconde méthode, RADAR (Règles d’Aide à la Décision et à l’ARgumentation) est une approche à base de règles logiques. Elle est destinée à des contextes plus contraints dans lesquels les préférences exprimées concernent à la fois les projets individuels, mais aussi le portefeuille de projets (degré de diversification, budget total, etc.). De plus, l'argumentation des décisions est ici basée exclusivement sur la qualité intrinsèque des projets en référence à une norme fixe. RADAR permet également la construction automatique de tels arguments. Nous proposons un programme linéaire en variable mixtes permettant de valider théoriquement cette approche. Cependant, sa résolution est nécessaire à chaque mise en œuvre de RADAR, ce qui limite l’application de cette approche au temps différé. Nous illustrons une telle application sur un jeu de données représentant des évaluations de projets financés par le Fond des Nations Unies pour la Démocratie (UNDEF). / Project portfolio management (PPM) involves the use of methods and tools, allowing an organization to plan, evaluate, analyze and screen the execution of a set of projects or project proposals, sharing common resources or aiming at the attainment of common objectives. Multicriteria decision aid models are useful tools to support this process, given their ability to accurately model preferences, and rationally agregate points of view. However, existing models present some lacks that limit their use outside of academic circles : (i) They neglect the non-symetrical nature of the importance of some criteria that are relevant in PPM. (ii) The black box effect makes it hard to use them for the argumentation of decisions and to gain their acceptance by users (iii) They are implicitly fitted for private/for-profit projects, which limits their use in public organizations. In this thesis, our contribution consists in proposing two multicriteria methods for supporting the activities of evaluating, selecting and arguing decision, for project portfolio management. We propose: (i) An analysis of the specific features of public and private projects and their consequences for decision support (ii) A framework that allows an independent modeling of the abilities of a criterion to oppose and convince (iii) Two transparent multicriteria agregation procedures, fitted for different decision contexts. We ensure the theoretical validity of our approaches and illustrate their applicability on real data, with satisfying results.
138

Optimisation de la gestion des avions dans un aéroport : affectation aux points de stationnement, routage au sol et ordonnancement à la piste. / Optimization of airport operations : stand allocation, ground routing and runway sequencing

Guepet, Julien 03 December 2015 (has links)
Le cadre de cette thèse est l'optimisation des opérations aéroportuaires. Nous nous intéressons à trois problèmes de gestion des avions dans un aéroport : l'affectation aux points de stationnement, le routage au sol entre les pistes et les points de stationnement, et l'ordonnancement des décollages et des atterrissages.Ce travail a été réalisée en collaboration étroite avec la société Amadeus. Nos approches ont été testées et validées avec des données réelles provenant d'aéroports européens.Nous proposons une formulation en Programme Linéaire en Nombres Entiers (PLNE) du problème d'affectation aux points de stationnement. Nous montrons que trouver une affectation réalisable est un problème NP-Complet et nous proposons diverses améliorations visant à réduire le temps de résolution de notre modèle. Nous obtenons ainsi des solutions de meilleure qualité que celles de la littérature, tout en conservant un temps de calcul raisonnable.Le problème de routage au sol est modélisé en adaptant un PLNE de la littérature. Nous montrons que les indicateurs de l'industrie sont en contradiction avec l'objectif de réduction du temps de roulage, et donc des émissions de pollutions. Nous proposons de nouveaux indicateurs basés sur l'heure de décollage, et non sur l'heure de départ du point de stationnement.Enfin, nous nous intéressons à l'intégration de l'ordonnancement à la piste avec le routage au sol. Nous montrons qu'une meilleure intégration permet de réduire le temps de roulage et d'améliorer la gestion de la piste. Nous proposons une heuristique séquentielle basée sur une modélisation en PLNE innovante du problème d'ordonnancement à la piste. Nous montrons que cette heuristique fournit des solutions de bonne qualité en temps raisonnable, contrairement à l'approche exacte de la littérature. / In this thesis, we address the optimization of aircraft ground operations at airports, focusing on three main optimization problems: the stand allocation, the ground routing between stands and runways, and the sequencing of take-offs and landings.These works result from a close collaboration with Amadeus. Our approaches have been tested and validated with real data from European airports.The stand allocation problem is formulated as a Mixed Integer Program (MIP). We show that finding an allocation plan respecting operational requirements is NP-Complete and we strengthen our model in several directions. We obtain better solutions than the literature withing reasonable computation times for an industrial application.The ground routing problem is modeled by a MIP formulation adapted from the literature. We show that the main indicators of the industry are in contradiction with the objective of reducing taxi times and therefore air pollution. We propose new indicators based on take-off times instead of push back times.Lastly, we focus on the integration of the runway sequencing with the ground routing. We highlight that a better integration allows to reduce taxi times while improving the management of the runway. We propose a sequential heuristic based on an innovative MIP formulation of the runway sequencing problem. This heuristic is shown to provide high quality solutions in reasonable computation times, unlike the exact approach from the literature.
139

Scheduling and Advanced Process Control in semiconductor Manufacturing / Ordonnancement et contrôle avancé des procédés en fabrication de semi-conducteurs.

Obeid, Ali 29 March 2012 (has links)
Dans cette thèse, nous avons examiné différentes possibilités d'intégration des décisions d'ordonnancement avec des informations provenant de systèmes avancés des contrôles des procédés dans la fabrication de semi-conducteurs. Nous avons développé des idées d'intégration et défini des nouveaux problèmes d'ordonnancement originales : Problème d'ordonnancement avec des contraintes de temps (PTC) et problème d'ordonnancement avec l'état de santé des équipement (PEHF). PTC et PEHF ont des fonctions objectives multicritères.PTC est un problème d'ordonnancement des familles de jobs sur des machines parallèles non identiques en tenant compte des temps de setup et des contraintes de temps. Les machines non identiques signifient que toutes les machines ne peuvent pas traités (qualifiés) tous les types de familles d'emplois. Les contraintes de temps nommés aussi Thresholds sont inspirées des besoins de l'APC. Elle est liée à l'alimentation régulière des boucles de contrôle de l'APC. L'objectif est de minimiser la somme des dates de fin et les pertes de qualification des machines lorsqu'une famille de jobs n'est pas ordonnancée sur la machine donnée avant un seuil de temps donné.D'autre part, PEHF est une extension de PTC. Il consiste d'intégrer les indices de santé des équipements (EHF). EHF est un indicateur associé à l'équipement qui donne l'état de la. L'objectif est d'ordonnancer des tâches de familles de jobs différents sur les machines tout en minimisant la somme des temps d'achèvement, les pertes de qualification de la machine et d'optimiser un rendement attendu. Ce rendement est défini comme une fonction d'EDH et de la criticité de jobs considérés. / In this thesis, we discussed various possibilities of integrating scheduling decisions with information and constraints from Advanced Process Control (APC) systems in semiconductor Manufacturing. In this context, important questions were opened regarding the benefits of integrating scheduling and APC. An overview on processes, scheduling and Advanced Process Control in semiconductor manufacturing was done, where a description of semiconductor manufacturing processes is given. Two of the proposed problems that result from integrating bith systems were studied and analyzed, they are :Problem of Scheduling with Time Constraints (PTC) and Problem of Scheduling with Equipement health Factor (PEHF). PTC and PEHF have multicriteria objective functions.PTC aims at scheduling job in families on non-identical parallel machines with setup times and time constraints.Non-identical machines mean that not all miachines can (are qualified to) process all types of job families. Time constraints are inspired from APC needs, for which APC control loops must be regularly fed with information from metrology operations (inspection) within a time interval (threshold). The objective is to schedule job families on machines while minimizing the sum of completion times and the losses in machine qualifications.Moreover, PEHF was defined which is an extension of PTC where scheduling takes into account the equipement Health Factors (EHF). EHF is an indicator on the state of a machine. Scheduling is now done by considering a yield resulting from an assignment of a job to a machine and this yield is defined as a function of machine state and job state.
140

Algorithmique du Network Calculus / Network Calculus Algoritmics

Jouhet, Laurent 07 November 2012 (has links)
Le Network Calculus est une théorie visant à calculer des bornes pire-cas sur les performances des réseaux de communication. Le réseau est modélisé par un graphe orienté où les noeuds représentent des serveurs, et les flux traversant le réseau doivent suivre les arcs. S'ajoutent à cela des contraintes sur les courbes de trafic (la quantité de données passées par un point depuis la mise en route du réseau) et sur les courbes de service (la quantité de travail fournie par chaque serveur). Pour borner les performances pire-cas, comme la charge en différents points ou les délais de bout en bout, ces enveloppes sont combinées à l'aide d'opérateurs issus notamment des algèbres tropicales : min, +, convolution-(min, +)... Cette thèse est centrée sur l'algorithmique du Network Calculus, à savoir comment rendre effectif ce formalisme. Ce travail nous a amené d'abord à comparer les variations présentes dans la littérature sur les modèles utilisés, révélant des équivalences d'expressivité comme entre le Real-Time Calculus et le Network Calculus. Dans un deuxième temps, nous avons proposé un nouvel opérateur (min, +) pour traiter le calcul de performances en présence d'agrégation de flux, et nous avons étudié le cas des réseaux sans dépendances cycliques sur les flux et avec politique de service quelconque. Nous avons montré la difficulté algorithmique d'obtenir précisément les pires cas, mais nous avons aussi fourni une nouvelle heuristique pour les calculer. Elle s'avère de complexité polynomiale dans des cas intéressants. / Network Calculus is a theory aiming at computing worst-case bounds on performances in communication networks. The network is usually modelled by a digraph : the servers are located on the nodes and the flows must follow path in the digraph. There are constraints on the trafic curves (how much data have been through a given point since the activation of the network) and on the service curves (how much work each server may provide). To derive bounds on the worst-case performances, as the backlog or the end-to-end delay, these envelopes are combined thanks to tropical algebra operators: min, +, convolution... This thesis focuses on Network Calculus algorithmics, that is how effective is this formalism. This work led us to compare various models in the litterature, and to show expressiveness equivalence between Real-Time Calculus and Network Calculus. Then, we suggested a new (min, +) operator to compute performances bounds in networks with agregated flows and we studied feed-forward networks under blind multiplexing. We showed the difficulty to compute these bounds, but we gave an heuristic, which is polynomial for interesting cases.

Page generated in 0.4634 seconds