Dissertations / Theses: 'Recherche opérationnelle'

1

Cizaire, Yves. "Popularisation de méthodes de recherche opérationnelle en Chine populaire." Paris 7, 1986. http://www.theses.fr/1986PA070023.

Full text

Abstract:

Premiere partie: exemples (tires de la presse chinoise) d'utilisation de la recherche operationnelle dans la chine antique. Deuxieme partie: historique des mouvements de popularisation de methodes de recherche operationnelle. A l'origine, rien ne differencie la recherche operationnelle chinoise de la recherche operationnelle occidentale. Mais en chine, sa courte histoire est immediatement baignee dans la politique. En effet, elle penetre le pays a un moment crucial de son histoire: le lancement du grand bond en avant (la popularisation se fera a travers de grands mouvements de masse). Le premier mouvement est lance sous la pression de l'echec du grand bond en avant. Il faut eviter la famine, et tous les secteurs d'activite sont invites a aider l'agriculture. Les mathematiciens sont aussi convies a participer a l'effort national, et ils introduisent une certaine rationalisation dans le travail a l'aide de methodes de programmation lineaire. Le deuxieme mouvement de popularisation est centre sur une methode: la "methode de planification d'ensemble" (methode d'ordonnancement du travail). Ce mouvement, lance en juin 1965, est rapidement interrompu par le debut de la grande revolution culturelle proletarienne. Le troisieme mouvement commence dans le debut des annees soixante-dix. On popularise essentiellement deux methodes crees par le mathematicien hua luogeng: la "methode de planification d'ensemble". . .
First part: some examples (from chinese mainland press) of the use of operation research during ancient china. Second part: historical account of the popularization of operation research. At the beginning, there was no difference between chinese operation research and occidental operation research. But in china, operation research is soon involved in political problems (due to the failure of the great leap forward). Under the leadership of the communist government, all the efforts are concentrated on the popularization of existing methods and on the research of other methods easily used by people. This popularization is made through mass movements. The first movement of popularization is launched (after the failure of the great leap forward) when the whole country is fighting against famine. The mathematicians help people by using linear programming methods. The second movement of popularization is based on the "overall planning method". This movement, launched in june 1965, is soon interrupted by the beginning of the cultural revolution. The third movement of popularization starts on the beginning of the seventhies. It concernes mainly two methods created by the mathematician hua luogeng: the "overall planning method" and the "optimal seeking method". . .

APA, Harvard, Vancouver, ISO, and other styles

2

Vanderpooten, Daniel. "L'approche interactive dans l'aide multicritère à la décision : aspects conceptuels, méthodologiques et informatiques." Paris 9, 1990. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1990PA090007.

Full text

Abstract:

L'évolution des sciences de la décision vers une reconnaissance accrue du rôle du décideur est particulièrement sensible dans le domaine de l'analyse multicritère. Le prolongement d'une telle tendance conduit naturellement à l'idée séduisante de l'intégration du décideur comme élément actif du processus d'aide à la décision. C'est ainsi qu'une nouvelle branche de l'aide multicritère à la décision - l'approche interactive - s'est développée au cours des deux dernières décennies. La multitude de procédures multicritères interactives présentées dans la littérature, le nombre croissant d'applications réelles ainsi même que l'émergence de prises de position critiques traduisent un succès que les tendances actuelles ne semblent guère démentir. S'il parait donc légitime de distinguer une approche spécifique, il est plus difficile de la caractériser dans la mesure où elle regroupe des procédures fondées sur des démarches et des concepts fort variés. L'objet de ce travail est donc de définir un cadre général permettant de mieux caractériser l'approche interactive, de resituer les méthodes jusqu'ici proposées, mais aussi de guider la conception de nouvelles procédures. Les aspects mathématiques, la manière d'intégrer l'information préférentielle progressivement émise par le décideur, la façon de régir l'interaction homme-machine, les considérations liées à l'implémentation informatique, tels sont par ailleurs les points principalement étudiés permettant de dégager certaines exigences ou lignes directrices. C'est sur ces bases qu'une nouvelle procédure a été élaborée, implémentée puis expérimentée

APA, Harvard, Vancouver, ISO, and other styles

3

Zaourar, Sofia. "Optimisation convexe non-différentiable et méthodes de décomposition en recherche opérationnelle." Thesis, Grenoble, 2014. http://www.theses.fr/2014GRENM099.

Full text

Abstract:

Les méthodes de décomposition sont une application du concept de diviser pour régner en optimisation. L'idée est de décomposer un problème d'optimisation donné en une séquence de sous-problèmes plus faciles à résoudre. Bien que ces méthodes soient les meilleures pour un grand nombre de problèmes de recherche opérationnelle, leur application à des problèmes réels de grande taille présente encore de nombreux défis. Cette thèse propose des améliorations méthodologiques et algorithmiques de méthodes de décomposition. Notre approche est basée sur l'analyse convexe et l'optimisation non-différentiable. Dans la décomposition par les contraintes (ou relaxation lagrangienne) du problème de planification de production électrique, même les sous-problèmes sont trop difficiles pour être résolus exactement. Mais des solutions approchées résultent en des prix instables et chahutés. Nous présentons un moyen simple d'améliorer la structure des prix en pénalisant leurs oscillations, en utilisant en particulier une régularisation par variation totale. La consistance de notre approche est illustrée sur des problèmes d'EDF. Nous considérons ensuite la décomposition par les variables (ou de Benders) qui peut avoir une convergence excessivement lente. Avec un point de vue d'optimisation non-différentiable, nous nous concentrons sur l'instabilité de l'algorithme de plans sécants sous-jacent à la méthode. Nous proposons une stabilisation quadratique de l'algorithme de Benders, inspirée par les méthodes de faisceaux en optimisation convexe. L'accélération résultant de cette stabilisation est illustrée sur des problèmes de conception de réseau et de localisation de plates-formes de correspondance (hubs). Nous nous intéressons aussi plus généralement aux problèmes d'optimisation convexe non-différentiable dont l'objectif est coûteux à évaluer. C'est en particulier une situation courante dans les procédures de décomposition. Nous montrons qu'il existe souvent des informations supplémentaires sur le problème, faciles à obtenir mais avec une précision inconnue, qui ne sont pas utilisées dans les algorithmes. Nous proposons un moyen d'incorporer ces informations incontrôlées dans des méthodes classiques d'optimisation convexe non-différentiable. Cette approche est appliquée avec succès à desproblèmes d'optimisation stochastique. Finalement, nous introduisons une stratégie de décomposition pour un problème de réaffectation de machines. Cette décomposition mène à une nouvelle variante de problèmes de conditionnement vectoriel (vectorbin packing) où les boîtes sont de taille variable. Nous proposons des heuristiques efficaces pour ce problème, qui améliorent les résultats de l'état de l'art du conditionnement vectoriel. Une adaptation de ces heuristiques permet de construire des solutions réalisables au problème de réaffectation de machines de Google
Decomposition methods are an application of the divide and conquer principle to large-scale optimization. Their idea is to decompose a given optimization problem into a sequence of easier subproblems. Although successful for many applications, these methods still present challenges. In this thesis, we propose methodological and algorithmic improvements of decomposition methods and illustrate them on several operations research problems. Our approach heavily relies on convex analysis and nonsmooth optimization. In constraint decomposition (or Lagrangian relaxation) applied to short-term electricity generation management, even the subproblems are too difficult to solve exactly. When solved approximately though, the obtained prices show an unstable noisy behaviour. We present a simple way to improve the structure of the prices by penalizing their noisy behaviour, in particular using a total variation regularization. We illustrate the consistency of our regularization on real-life problems from EDF. We then consider variable decomposition (or Benders decomposition), that can have a very slow convergence. With a nonsmooth optimization point of view on this method, we address the instability of Benders cutting-planes algorithm. We present an algorithmic stabilization inspired by bundle methods for convex optimization. The acceleration provided by this stabilization is illustrated on network design andhub location problems. We also study more general convex nonsmooth problems whose objective function is expensive to evaluate. This situation typically arises in decomposition methods. We show that it often exists extra information about the problem, cheap but with unknown accuracy, that is not used by the algorithms. We propose a way to incorporate this coarseinformation into classical nonsmooth optimization algorithms and apply it successfully to two-stage stochastic problems.Finally, we introduce a decomposition strategy for the machine reassignment problem. This decomposition leads to a new variant of vector bin packing problems, where the bins have variable sizes. We propose fast and efficient heuristics for this problem that improve on state of the art results of vector bin packing problems. An adaptation of these heuristics is also able to generate feasible solutions for Google instances of the machine reassignment problem

APA, Harvard, Vancouver, ISO, and other styles

4

Dakhli, Jean-Loup. "Le prototypage." Paris 9, 1997. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1997PA090072.

Full text

Abstract:

Dans cette recherche, nous sommes partis d'un constat : l'impact des technologies de l'information sur les organisations, et la persistance du phénomène de crise du logiciel dont les effets sont à la fois économiques, humains et sociaux-organisationnels. Nous avons alors analysé cette crise ainsi que les solutions préconisées pour y remédier. Notre analyse nous a permis alors de modéliser le génie logiciel comme un ensemble de quatre espaces inter reliés correspondant chacun a un sous ensemble des différents aspects du logiciel et des acteurs d'un projet. Par ailleurs, nous avons mis en évidence le rôle prépondérant du prototypage dans la réduction des effets de la crise du logiciel et pour aider les organisations à réaliser des applications informatiques capables de supporter leurs processus opérationnels et décisionnels. Dans ce cadre nous avons étudié d'une part, les fondements du prototypage et les principales définitions de cette approche utilisées à ce jour ; d'autre part nous avons proposé une typologie du prototypage et enfin, comme l'adoption d'une approche de prototypage ne signifie pas l'abandon de la rigueur qui prévalait dans les processus de développements linéaires, nous avons examiné les différentes tentatives d'intégration du prototypage dans la conduite de projet. Notre analyse de la crise du logiciel nous a conduit à identifier qu'un des problèmes majeurs rencontres en génie logiciel consiste à choisir la solution la plus appropriée pour développer un système informatique. Aussi, dans un premier temps, nous nous sommes consacrés à une évaluation du prototypage à travers un bilan empirique de l'utilisation de cette approche, dans un deuxième temps nous avons proposé une méthode d'évaluation du prototypage comme outil d'aide à la décision ; et enfin, nous avons élaboré une méthode d'évaluation permettant de sélectionner l'ensemble des solutions, méthodes et outils les plus adéquats, ou le prototypage joue un rôle prépondérant.

APA, Harvard, Vancouver, ISO, and other styles

5

Daher, Christian. "Quelques applications des méthodes de contrôle stochastique en finance mathématique." Paris 9, 1993. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1993PA090001.

Full text

Abstract:

La thèse se compose de plusieurs articles indépendants. Les deux premiers articles examinent un problème de sélection de portefeuille en horizon fini qui est ensuite applique à l'évaluation d'options, d'abord dans un cas complet, puis dans un cas incomplet. Le troisième article considère un problème de contrôle optimal où l'objectif est la norme infinie d'un processus de diffusion. Les deux derniers articles présentent divers schémas et preuves de convergence de méthodes numériques pour des équations issues de la finance mathématique et du contrôle singulier. La théorie des solutions de viscosité est systématiquement employée

APA, Harvard, Vancouver, ISO, and other styles

6

Costa, Alberto. "Applications of Reformulations in Mathematical Programming." Phd thesis, Palaiseau, Ecole polytechnique, 2012. https://pastel.hal.science/docs/00/74/60/83/PDF/Phd_Costa.pdf.

Full text

Abstract:

La programmation mathématique est une technique qui peut être utilisée pour résoudre des problèmes concrets où l'on veut maximiser, ou minimiser, une fonction objectif soumise à des contraintes sur les variables décisionnelles. Les caractéristiques les plus importantes de la programmation mathématique sont la création d'un modèle pour décrire le problème (aussi appelé formulation), et la mise en œuvre d'algorithmes efficaces pour le résoudre (aussi appelés solveurs). Dans cette thèse, on s'occupe du premier point. Plus précisemment, on étudie certains problèmes qui proviennent de domaines diffèrents, et en commençant par les modèles les plus naturels pour les décrire, on présente des formulations alternatives, qui partagent certaines propriétés avec le modèle original mais qui sont en quelque sorte meilleures (par exemple au niveau du temps d'exécution nécessaire pour obtenir la solution par le solveur). Ces nouveaux modèles sont appelés reformulations. On suit la classification des reformulations proposée par Liberti dans [Reformulations in Mathematical Programming: Definitions and Systematics, RAIRO-OR, 43(1):55-86, 2009]: exact reformulations (aussi appellées opt-reformulations), narrowings, relaxations. Cette thèse concerne trois applications de la programmation mathématique où les reformulations ont été fondamentales pour obtenir une bonne solution. Le premier problème étudié est le partitionnement de graphes sur la base de la maximisation de la modularité. Comme ce problème est NP-difficile, plusieurs heuristiques sont proposées. On s'occupe d'un algorithme séparatif hiérarchique qui fonctionne en divisant récursivement une classe en deux nouvelles classes de façon optimale. Cet étape de division est accomplie en résolvant un programme binaire quadratique et convexe. Il est reformulé de manière exacte pour obtenir une forme plus compacte sans modifier l'ensemble des solutions optimales (exact reformulation). On considère aussi l'impact donné par la réduction du nombre des solutions symétriques globalement optimales. Les temps d'exécution sont considérablement réduits par rapport à la formulation originelle. Le deuxième problème étudié dans cette thèse est le placement de cercles égaux dans un carré (Packing Equal Circles in a Square, ou PECS), où l'on veut placer des cercles égaux dans un carré de côté 1 sans avoir de superposition et en maximisant le rayon commun. L'une des raisons pour laquelle le problème est difficile à résoudre vient de la présence de plusieurs solutions symétriques optimales, et par conséquent un arbre de séparation-et-évaluation (ou Branch-and-Bound) très large. Certaines solutions symétriques optimales sont rendues irréalisables en ajoutant des contraintes pour briser les symétries (Symmetry Breaking Constraints, ou SBCs) à la formulation, en obtenant ainsi un narrowing. Le temps d'exécution et la dimension de l'arbre de Branch-and-Bound sont tous les deux meilleurs par rapport à la formulation originelle. La troisième application considérée dans cette thèse est le calcul de la relaxation convexe pour des problèmes multilinéaires, et la comparaison de la formulation ''primale'' avec celle obtenue par une représentation ''duale''. Bien que ces deux relaxations soient déjà connues, il est intéressant de voir que la relaxation duale conduit à des meilleures performances de calcul
Mathematical programming is a technique that can be used to solve real-world optimization problems, where one wants to maximize, or minimize, an objective function subject to some constraints on the decision variables. The key features of mathematical programming are the creation of a model for describing the problem (the so called formulation), and the implementation of efficient algorithms to solve it (also called solvers). In this thesis, we focus on the first point. More precisely, we study some problems arising from different domains, and starting from the most natural models for describing them, we propose alternative formulations, which share some properties with the original models but are somehow better (for instance in terms of computational time needed to obtain the solution by the solver). These new models are called reformulations. We follow the classification of reformulations proposed by Liberti in [Reformulations in Mathematical Programming: Definitions and Systematics, RAIRO-OR, 43(1):55-86, 2009]: exact reformulations (also called opt-reformulations), narrowings, relaxations. This thesis is concerned with three mathematical programming applications where the reformulation was crucial to obtain a good solution. The first problem tackled herein is graph clustering by means of modularity maximization. Since this problem is NP-hard, several heuristics are proposed. We focus on a divisive hierarchical algorithm which works by recursively splitting a cluster into two new clusters in an optimal way. This splitting step is performed by solving a convex binary quadratic program. This is reformulated exactly to a more compact form without changing the optimal solutions set (exact reformulation). We also evaluate the impact provided by the reduction of the number of symmetric global optima of the problem, which is also an important topic of the next part of this thesis. The computational times are considerably reduced with respect to the original formulation. The second problem tackled in the thesis is the Packing of Equal Circles in a Square (PECS), where one wants to place non-overlapping equal circles in a unit square in such a way as to maximize the common radius. One of the reasons why the problem is hard to solve is the presence of several symmetric optimal solutions, and consequently a very large Branch-and-Bound tree. Some of the symmetric optima are made infeasible by adjoining some Symmetry Breaking Constraints (SBCs) to the formulation, thereby obtaining a narrowing. Both computational time and size of the Branch-and-Bound tree outperform the ones provided by the original formulation. The third application considered in the thesis is that of computing the convex relaxation for multilinear problems, and to compare the "primal" formulation and another one obtained using a "dual" representation. Although these two relaxations are both already known in the literature, we make a striking observation, i. E. , that the dual relaxation leads to a faster and more stable solution process as regards CPU time

APA, Harvard, Vancouver, ISO, and other styles

7

Costa, Alberto. "Applications of Reformulations in Mathematical Programming." Phd thesis, Ecole Polytechnique X, 2012. http://pastel.archives-ouvertes.fr/pastel-00746083.

Full text

Abstract:

La programmation mathématique est une technique qui peut être utilisée pour résoudre des problèmes concrets où l'on veut maximiser, ou minimiser, une fonction objectif soumise à des contraintes sur les variables décisionnelles. Les caractéristiques les plus importantes de la programmation mathématique sont la création d'un modèle pour décrire le problème (aussi appelé formulation), et la mise en œuvre d'algorithmes efficaces pour le résoudre (aussi appelés solveurs). Dans cette thèse, on s'occupe du premier point. Plus précisemment, on étudie certains problèmes qui proviennent de domaines diffèrents, et en commençant par les modèles les plus naturels pour les décrire, on présente des formulations alternatives, qui partagent certaines propriétés avec le modèle original mais qui sont en quelque sorte meilleures (par exemple au niveau du temps d'exécution nécessaire pour obtenir la solution par le solveur). Ces nouveaux modèles sont appelés reformulations. On suit la classification des reformulations proposée par Liberti dans [Reformulations in Mathematical Programming: Definitions and Systematics, RAIRO-OR, 43(1):55-86, 2009]: exact reformulations (aussi appellées opt-reformulations), narrowings, relaxations. Cette thèse concerne trois applications de la programmation mathématique où les reformulations ont été fondamentales pour obtenir une bonne solution. Le premier problème étudié est le partitionnement de graphes sur la base de la maximisation de la modularité. Comme ce problème est NP-difficile, plusieurs heuristiques sont proposées. On s'occupe d'un algorithme séparatif hiérarchique qui fonctionne en divisant récursivement une classe en deux nouvelles classes de façon optimale. Cet étape de division est accomplie en résolvant un programme binaire quadratique et convexe. Il est reformulé de manière exacte pour obtenir une forme plus compacte sans modifier l'ensemble des solutions optimales (exact reformulation). On considère aussi l'impact donné par la réduction du nombre des solutions symétriques globalement optimales. Les temps d'exécution sont considérablement réduits par rapport à la formulation originelle. Le deuxième problème étudié dans cette thèse est le placement de cercles égaux dans un carré (Packing Equal Circles in a Square, ou PECS), où l'on veut placer des cercles égaux dans un carré de côté 1 sans avoir de superposition et en maximisant le rayon commun. L'une des raisons pour laquelle le problème est difficile à résoudre vient de la présence de plusieurs solutions symétriques optimales, et par conséquent un arbre de séparation-et-évaluation (ou Branch-and-Bound) très large. Certaines solutions symétriques optimales sont rendues irréalisables en ajoutant des contraintes pour briser les symétries (Symmetry Breaking Constraints, ou SBCs) à la formulation, en obtenant ainsi un narrowing. Le temps d'exécution et la dimension de l'arbre de Branch-and-Bound sont tous les deux meilleurs par rapport à la formulation originelle. La troisième application considérée dans cette thèse est le calcul de la relaxation convexe pour des problèmes multilinéaires, et la comparaison de la formulation ''primale'' avec celle obtenue par une représentation ''duale''. Bien que ces deux relaxations soient déjà connues, il est intéressant de voir que la relaxation duale conduit à des meilleures performances de calcul.

APA, Harvard, Vancouver, ISO, and other styles

8

García, Manuel. "Adaptation des methodes de controle de gestion a une conception de la productivite integrant la dimension qualite." Lyon 2, 1998. http://www.theses.fr/1998LYO22010.

Full text

Abstract:

Notre recherche avait pour objectif d'identifier les possibilites et les limites des systemes de controle de gestion proposes dans la litterature et utilises dans un echantillon de 103 entreprises et organisations ou nous sommes intervenus. L'application approximative des methodes de controle de gestion est assez souvent expliquee par une perte de pertinence en regard d'une part, des nouvelles conditions de la concurrence, qui ne portent plus seulement sur les couts, mais aussi sur la qualite et les delais, et d'autre part, des modifications de structure des organisations qui operent de plus en plus en reseaux ou en favorisant des modalites de fonctionnement transversales. Pourtant les organisations fonctionnent, ce qui semble indiquer qu'il existe une certaine normalisation economique et professionnelle des comportements, prenant en quelque sorte le relais du systeme de controle de gestion formalise. L'integration de la qualite et de la productivite dans le controle de gestion semble repondre a un besoin a la fois individuel et collectif, qui ne peut trouver de reponses que dans un systeme d'information multifocalise. La recherche d'une plus grande precision et d'une meilleure pertinence du systeme d'information, nous a conduit a proposer d'associer au calcul des couts, des procedures d'actions a proximite des actes de travail quotidiens, puis d'operer des agregations successives afin de disposer d'un systeme global de controle
The main objective of our research was to identify the possibilities and the limits of management control systems suggested by the management literature and also used in a sample of 103 organisations in which we intervened. The general application of management control methods is often explained by a loss of aptness as regards on the one hand, the new conditions of competition which no longer focus on costs alone, but also on quality and time limits, and on the other hand the modifications in organization structure with more activities organized as a network, or by favouring transversal way of production. However, the fact that organizations run, that seems to show that there exists some professional and economic behaviour norms in place of formalised management control. But this way of activity regulation appears as non optimal. The integration of quality and productivity seems to respond to both individual and collective needs, which can only be satisfied by a multi-focused information system. The research of more precision and relevant information system leads us to suggest associating between cost accounting and action proceedings and also operating successive aggregations, in order to process a global control system

APA, Harvard, Vancouver, ISO, and other styles

9

Richard, Pascal. "Contribution des réseaux de Petri à l'étude de problèmes de recherche opérationnelle." Tours, 1997. http://www.theses.fr/1997TOUR4022.

Full text

Abstract:

Un réseau de Petri est un modèle mathématique utilisé pour modéliser et analyser les systèmes à événements discrets. Nous présentons dans ce mémoire leur utilisation pour des problèmes de recherche opérationnelle. L'état de l'art montre l'intérêt de cet outil pour aborder cette problématique. L'étroit lien entre la programmation mathématique et les réseaux de Petri est ensuite mis en évidence. Précisément, nous montrons que le problème de programmation mathématique se réduit polynomialement à un problème d'ordonnancement dans les réseaux de Petri. Ce résultat repose sur une nouvelle condition nécessaire et suffisante d'accessibilité pour l'équation des marquages. Nous présentons enfin une application industrielle de ces résultats dans le cadre d'un logiciel d'aide à la décision pour la planification de production dans l'industrie du verre.

APA, Harvard, Vancouver, ISO, and other styles

10

Zaourar, Lilia Koutchoukali. "Recherche opérationnelle et optimisation pour la conception testable de circuits intégrés complexes." Grenoble, 2010. http://www.theses.fr/2010GRENM055.

Full text

Abstract:

Le travail de cette thèse est à l'interface des dom aines de la recherche opérationnelle et de la micro -électronique. Il traite de l'utilisation des techniques d'optimisation combinatoire pour la DFT (Design For Test) des Circuits Intégrés (CI). Avec la croissance rapide et la complexité des CI actuels, la qualité ainsi que le coût du test sont devenus des paramètres importants dans l'industrie des semi-conducteurs. Afin de s'assurer du bon fonctionnement du CI, l'étape de test est plus que jamais une étape essentielle et délicate dans le processus de fabrication d'un CI. Pour répondre aux exigences du marché, le test doit être rapide et efficace dans la révélation d'éventuels défauts. Pour cela, il devient incontournable d'appréhender la phase de test dès les étapes de conception du CI. Dans ce contexte, la conception testable plus connue sous l'appellation DFT vise à améliorer la testabilité des CI. Plusieurs problèmes d'optimisation et d'aide à la décision découlent de la micro-électronique. La plupart de ces travaux traitent des problèmes d'optimisation combinatoire pour le placement et routage des circuits. Nos travaux de recherche sont à un niveau de conception plus amont, la DFT en présynthèse au niveau transfert de registres ou RTL (Register Transfer Level). Cette thèse se découpe en trois parties. Dans la première partie nous introduisons les notions de bases de recherche opérationnelle, de conception et de test des CI. La démarche suivie ainsi que les outils de résolution utilisés dans le reste du document sont présentés dans cette partie. Dans la deuxième partie, nous nous intéressons au problème de l'optimisation de l'insertion des chaîne s de scan. A l'heure actuelle, le "scan interne" est une des techniques d'amélioration de testabilité ou de DFT les plus largement adoptées pour les circuits intégrés numériques. Il s'agit de chaîner les éléments mémoires ou bascules du circuit de sorte à former des chaînes de scan qui seront considérées pendant la phase de test comme points de contrôle et d'observation de la logique interne du circuit. L'objectif de notre travail est de développer des algorithmes permettant de générer pour un CI donné et dès le niveau RTL des chaînes de scan optimales en termes de surface, de temps de test et de consommation en puissance, tout en respectant des critères de performance purement fonctionnels. Ce problème a été modélisé comme la recherche de plus courtes chaînes dans un graphe pondéré. Les méthodes de résolution utilisées sont basées sur la recherche de chaînes hamiltoniennes de longueur minimale. Ces travaux ont été réalisés en collaboration avec la start-up DeFacTo Technologies. La troisième partie s'intéresse au problème de partage de blocs BIST (Built In Self Test) pour le test des mémoires. Le problème peut être formulé de la façon suivante : étant données des mémoires de différents types et tailles, ainsi que des règles de partage des colliers en série et en parallèle, il s'agit d'identifier des solutions au problème en associant à chaque mémoire un collier. La solution obtenue doit minimiser à la fois la surface, la consommation en puissance et le temps de test du CI. Pour résoudre ce problème, nous avons conçu un prototype nommé Memory BIST Optimizer (MBO). Il est constitué de deux phases de résolution et d'une phase de validation. La première phase consiste à créer des groupes de compatibilité de mémoires en tenant compte des règles de partage et d'abstraction des technologies utilisées. La deuxième phase utilise les algorithmes génétiques pour l'optimisation multi-objectifs afin d'obtenir un ensemble de solutions non dominées. Enfin, la validation permet de vérifier que la solution fournie est valide. De plus, elle affiche l'ensemble des solutions à travers une interface graphique ou textuelle. Cela permet à l'utilisateur de choisir la solution qui lui correspond le mieux. Actuellement, l'outil MBO est intégré dans un flot d'outils à ST-microelectronics pour une utilisation par ses clients
This thesis is a research contribution interfacing operations research and microelectronics. It considers the use of combinatorial optimization techniques for DFT (Design For Test) of Integrated Circuits (IC). With the growing complexity of current IC both quality and cost during manufacturing testing have become important parameters in the semiconductor industry. To ensure proper functioning of the IC, the testing step is more than ever a crucial and difficult step in the overall IC manufacturing process. To answer market requirements, chip testing should be fast and effective in uncovering defects. For this, it becomes essential to apprehend the test phase from the design steps of IC. In this context, DFT techniques and methodologies aim at improving the testability of IC. In previous research works, several problems of optimization and decision making were derived from the micro- electronics domain. Most of previous research contributions dealt with problems of combinatorial optimization for placement and routing during IC design. In this thesis, a higher design level is considered where the DFT problem is analyzed at the Register Transfer Level (RTL) before the logic synthesis process starts. This thesis is structured into three parts. In the first part, preliminaries and basic concepts of operations research, IC design and manufacturing are introduced. Next, both our approach and the solution tools which are used in the rest of this work are presented. In the second part, the problem of optimizing the insertion of scan chains is considered. Currently, " internal scan" is a widely adopted DFT technique for sequential digital designs where the design flip-flops are connected into a daisy chain manner with a full controllability and observability from primary inputs and outputs. In this part of the research work, different algorithms are developed to provide an automated and optimal solution during the generation of an RTL scan architecture where several parameters are considered: area, test time and power consumption in full compliance with functional performance. This problem has been modelled as the search for short chains in a weighted graph. The solution methods used are based on finding minimal length Hamiltonian chains. This work was accomplished in collaboration with DeFacTo Technologies, an EDA start-up close to Grenoble. The third part deals with the problem of sharing BIST (Built In Self Test) blocks for testing memories. The problem can be formulated as follows: given the memories with various types and sizes, and sharing rules for series and parallel wrappers, we have to identify solutions to the problem by associating a wrapper with each memory. The solution should minimize the surface, the power consumption and test time of IC. To solve this problem, we designed a prototype called Memory BIST Optimizer (MBO). It consists of two steps of resolution and a validation phase. The first step creates groups of compatibility in accordance with the rules of abstraction and sharing that depend on technologies. The second phase uses genetic algorithms for multi-objective optimization in order to obtain a set of non dominated solutions. Finally, the validation verifies that the solution provided is valid. In addition, it displays all solutions through a graphical or textual interface. This allows the user to choose the solution that fits best. The tool MBO is currently integrated into an industrial flow within ST-microelectronics

APA, Harvard, Vancouver, ISO, and other styles

11

Nzatse, Pouna Jean-Baptiste. "Sur quelques méthodes de traitement des délais en gestion des stocks." Paris 9, 1986. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1986PA090017.

Full text

Abstract:

Détermination de la politique optimale en temps continu, pour un problème de commande impulsionnelle associe à la gestion des stocks de n produits (n = 1,2) avec retard de livraison, dans le cas stationnaire déterministe. Approximation dans le cas stationnaire discret, de la solution d'un problème de gestion de stock d'un produit, avec un procédé croissant (solution minimum) et avec un procédé décroissant (solution maximum)

APA, Harvard, Vancouver, ISO, and other styles

12

Roy, Daniel M. "Une architecture hiérarchisée multi-agents pour le pilotage réactif d'ateliers de production." Metz, 1998. http://www.theses.fr/1998METZ001S.

Full text

Abstract:

Le monde industriel est en constante évolution en raison des besoins de l'industrie lies à la compétitivité. Le tout automatique n'ayant pas donné les résultats escomptés, une nouvelle approche doit être définie. Il faut un système qui puisse être adapté lorsque les méthodes de production, les procédures de contrôle de l'ordonnancement etc. Changent mais qui reste capable de gérer la production en temps-réel. Certaines méthodologies tentent de répondre à ce problème, cependant, il subsiste quelques défauts tels que la gestion des accidents ou des aléas de production, la nécessité de reconfigurer l'installation si l'organisation de l'entreprise change et la concurrence totale entre tous les agents intervenant dans la processus. Le but de ce travail est de proposer une autre approche, visant, en particulier, a résoudre les problèmes de gestion dynamique en temps réel de la production (postes de travail en panne, commandes urgentes, etc. ), à automatiser autant que possible le processus visant à adapter le système aux modifications de l'entreprise et à rationaliser la prise de décision par une hiérarchisation accrue. Pour cela, nous nous sommes appuyés sur une plate-forme multi-agents doublement hybride. Premièrement, la conduite est hiérarchisée alors que la commande est centralisée ce qui nous positionne entre les architectures centralisée et hiérarchisée. La centralisation nous a permis d'éviter la concurrence entre agents lors du traitement d'un problème et la hiérarchisation, a contrario, a permis à chaque agent de ne s'occuper que de la conduite d'un seul produit. Deuxièmement, nous effectuons un ordonnancement prévisionnel total, mais pouvant être remis partiellement (voire totalement) en cause au cours du processus. Ainsi, nous ne perdons pas de temps en cours de production, même si, en cas d'aléas, il est nécessaire de refaire un ordonnancement partiel (voire total). Nous avons ainsi gagné en rapidité et en réactivité grâce à la double hybridation du système
For competitiveness reasons, the industrial world is in permanent evolution. The first stage of this evolution was massive automation, but because this solution did not meet all expectations, a new approach is required. In other words, it is necessary to have a system which could be adapted when methods of production, procedures of scheduling, etc. Change but which remains capable to manage the production in "real time". Some methods tempt to solve this problem. However, some defects subsist such as accidents or production risk management, the necessity to re-configure the installation if the organization of the enterprise changes and the total competition between agents. Our goal is to propose an alternate approach, especially, aiming, at solvin dynamic production management problems in real-time (workstation breakdowns, urgent orders. . . ), to automate as much as possible the process in order to adapt the system to modifications of the enterprise and to rationalize the decision-making by a strong hierarchical structure. To make this, we have based the system on a doubly hybrid multi-agent platform. First, the conduct is hierarchized and the command is centralized, then we are placing between the centralized and hierarchised architectures. The centralization allow us to avoid the competition between agents to solve a problem and the hierarchization allow to each agent to take care of only one product. Secondary, we realize a complete scheduling at the start of the process, but it could be partially (or totally) modified during the process. Thus, we don't lost time during the production, even if, in case of problem, it is necessary to make again a partially (or totally) scheduling. So, we have gain in rapidity and reactivity thanks to the doubly hybridization

APA, Harvard, Vancouver, ISO, and other styles

13

Rahmani, Khaled. "Les déterminants de la qualité des infrastructures : Le cas des routes nationales françaises. Evaluations économétriques et stratégies d'entretien." Marne-la-vallée, ENPC, 1997. http://www.theses.fr/1997ENPC9713.

Full text

Abstract:

Avec la diminution des crédits budgétaires routiers et le souci permanent d'offrir aux usagers un niveau de service élevé, la programmation et la planification des activités de construction, d'entretien et de remise en état des chaussées ainsi que l'évaluation de leurs diverses conséquences en terme technique, économique et financier sont devenues indispensables pour une gestion efficace et rationnelle d'un réseau routier. Cette nouvelle préoccupation a mis l'accent sur la nécessite de recourir à la systématisation de la gestion routière. En d'autres termes, il faut entreprendre des opérations d'auscultation de l'état des chaussées pour l'évaluation de leur niveau de qualité en termes fonctionnel et structurel mais il faut aussi assurer le suivi de leur comportement et appréhender l'évolution de leur performance. L’élaboration et le développement de modelés d'analyse et de prévision des dégradations de la qualité des chaussées à partir de l'analyse économétrique des lois d'évolution deviennent à cet effet nécessaire. Les modèles de prévision des dégradations de la qualité des chaussées nous permettent en effet, d'analyser le comportement des différents types de structures et d'évaluer ainsi leurs performances en terme physique et financier. L’évaluation économétrique des résultats de la modélisation peut également aider à la détermination des besoins financiers compte tenu de l'évolution des dégradations des chaussées et a la définition de stratégies et de politique optimales pour la gestion d'un réseau routier important. Cette optimisation est essentielle pour assurer une allocation rationnelle des ressources financières disponibles. C’est la voie qui a été explorée par notre étude. Cette étude aborde en premier lieu l'expérience française dans le domaine de la gestion routière. Viennent ensuite tous les aspects qui sont liés à la systématisation de la gestion routière. Cette partie est destinée à mettre en évidence l'importance des systèmes de gestion des chaussées dans la programmation des travaux d'entretien et l'optimisation de leurs couts. Elle traite ensuite des diverses considérations qui sont lies a la notion d'évolution de la qualité des chaussées. L’étude indique également les grandes orientations de la nouvelle politique routière de la direction des routes pour la gestion de son réseau routier et fait une description du système d'évaluation de l'état des routes nationales qui a servi à la définition des notes qualité des chaussées. Afin d'analyser ces notes de qualité et suivre leur évolution en fonction des différents facteurs explicatifs, l'étude suggère plusieurs types de modèles de prévision pour appréhender les causes et les conditions des dégradations de la qualité des chaussées. L'application de ces modèles de dégradation (évaluation économétrique des résultats de régressions) nous a permis d'analyser le comportement des différents types de structures de chaussées en terme physique et financier, d'établir des équivalences de dégradations entre les différents facteurs explicatifs et l'évolution de la qualité, d'évaluer à partir des différentes implications techniques et économiques, les couts de la dégradation annuelle de la qualité des chaussées et de déterminer ainsi, les besoins financiers pour une gestion optimale des chaussées. Enfin l'étude propose un calcul technico-économique pour l'optimisation de stratégies d'entretien des routes nationales.

APA, Harvard, Vancouver, ISO, and other styles

14

Rossi, André. "De l'optimisation dans les réseaux." Habilitation à diriger des recherches, Université de Bretagne Sud, 2012. http://tel.archives-ouvertes.fr/tel-00746435.

Full text

Abstract:

Ce mémoire d'habilitation à diriger des recherches traite de problèmes d'optimisation dans les réseaux, dont la modélisation et la résolution reposent sur les outils de la recherche opérationnelle. Le premier chapitre retrace brièvement mon parcours de formation, ainsi que mes activités d'enseignement et de recherche. Le second chapitre est consacré aux réseaux de capteurs sans fil. La minimisation du défaut de couverture, la maximisation de la durée de vie et l'exploration de compromis entre ces deux objectifs sont abordés à l'aide d'un algorithme de génération de colonnes combiné à un algorithme génétique. Le troisième chapitre traite de la configuration robuste d'un réseau de distribution d'électricité visant à le prémunir des effets néfastes d'une augmentation de la demande. Un algorithme basé sur la génération de plans coupants associé à des inégalités valides est notamment proposé, puis comparé avec une formulation basée sur la programmation linéaire en nombres entiers et une heuristique. Le quatrième chapitre aborde le problème du déploiement (ou la mise à niveau) d'un réseau de fibre optique permettant la communication multicast, avec pour but de minimiser le coût des équipements opto-électroniques à installer. Deux versions du problème, qui se distinguent par l'expression du coût des équipements en question, sont abordés à l'aide d'un algorithme de plans coupants enrichi par une fonction de réparation et une recherche tabou, illustrant l'efficacité d'une étroite collaboration entre méthodes exactes et approchées. Enfin, ce mémoire est clos par un chapitre consacré à la présentation de perspectives ouvertes par ces travaux, ainsi qu'une réflexion plus personnelle sur l'exercice de la direction de recherche au niveau individuel, dans l'encadrement doctoral, et dans la direction d'équipe.

APA, Harvard, Vancouver, ISO, and other styles

15

Canon, Cyril. "Application des techniques de recherche opérationnelle à la planification de centres de contacts en milieu multicompétent." Tours, 2005. http://www.theses.fr/2005TOUR4039.

Full text

Abstract:

Le travail présenté dans cette thèse s’est déroulé dans le cadre d’une convention CIFRE entre le Laboratoire d’Informatique de l’Université François-Rabelais de Tours et la société Vitalicom. Ce travail porte sur la planification de personnel dans les centres d’appels (ou centres de contacts clients). La planification de personnel est devenue un enjeu économique très important, surtout dans les sociétés de services telles que les centres d’appels. En effet, la réactivité dans ce secteur est très importante, car il faut répondre au client dans des délais très courts. Toutefois, la planification de personnel dans un centre d’appels ne se résume pas à la création des horaires des employés. Le client envoie les prévisions d’appels au centre qui doit ensuite planifier le personnel afin de répondre à ces appels, tout en assurant une certaine qualité. Deux problèmes majeurs se profilent alors : -Déduire le nombre d’agents requis pour répondre aux appels, période par période. Ce problème est appelé dimensionnement. - Créer les horaires des agents sur un horizon d’une semaine. Ce problème est le Shift Design Problem. Le but de cette thèse est de résoudre ces problèmes de manière à obtenir un outil complet d’aide à la planification de personnel. La thèse est organisée de la façon suivante. Le chapitre 1 définit le contexte des centres d’appels. De nombreux aspects de cette industrie sont évoqués. Une méthode de planification en quatre phases est proposée. Elle sera suivie dans les chapitres suivants. Le chapitre 2 présente un état de l’art sur les deux problèmes majeurs traités dans cette thèse : le dimensionnement et la planification de personnel. Pour le problème de dimensionnement, les lois les plus usuelles sont données, ainsi que les formules de calcul de la qualité de service. Ensuite, des extensions du modèle de base sont données, avec leurs algorithmes respectifs. Pour le problème de planification de personnel, une notation des problèmes est proposée, inspirée de la notation à trois champs des problèmes d’ordonnancement. Ensuite, diverses méthodes de résolution de la littérature sont présentées, en expliquant pour chacune les inconvénients qui empêche d’appliquer cette méthode au problème qui nous concerne directement. Le chapitre 3 traite du dimensionnement des centres d’appels. Une modélisation déterministe est proposée et justifiée. Ensuite plusieurs méthodes de résolution sont proposées : un programme linéaire en nombre entiers, un programme par contraintes, des algorithmes de listes et des descentes locales. Des tests sont présentés et les méthodes de résolution sont comparées entre elles. Enfin, un moteur de simulation est présenté, ainsi que la simulation des résultats fournis par les algorithmes. Le chapitre 4 traite de la création des horaires des employés. Le problème est tout d’abord modélisé à l’aide de la PLNE et de la PPC. Ensuite deux méthodes heuristiques de résolution sont proposées : une méthode Tabou et une méthode de recherche sur de multiples voisinages, appelée Runner. Les méthodes sont testées et comparées. Enfin, le chapitre 5 traite de l’outil d’aide à la planification. Le problème de l’annualisation du temps de travail est d’abord traité. Un PLNE est mis en place pour résoudre ce problème. Ensuite, un outil de gestion de contraintes personnelles des employés est mis en place. Enfin, un exemple complet de planification est déroulé entièrement
The aim of a call center is to manage the contacts between their clients and their customers. Agents are not equivalent. Knowing the forecasted incoming calls for four weeks and knowing the data concerning the agents, the problem is to determine the detailed planning of the agents, for each week. Firstly the forecasted number of calls is used to determine for each eriod the number of agents needed to satisfy the required quality of service. Then knowing the constraints related tothe labor code, the number of working hours for each week per agent has tobe deterined. Then the shifts of all the agents plus the position of the breaks and the days-off, with respect of the loading curve, have to be determined. Finally, we have to assign the activities to agents. In case of unfeasibility, some constraints are added to the third phase, and the process iterates until a feasible solution is found. Heuristic approaches are proposed and tested on randomly generated instances

APA, Harvard, Vancouver, ISO, and other styles

16

Buljubasic, Mirsad. "Efficient local search for several combinatorial optimization problems." Thesis, Montpellier, 2015. http://www.theses.fr/2015MONTS010/document.

Full text

Abstract:

Cette thèse porte sur la conception et l'implémentation d'algorithmes approchés pour l'optimisation en variables discrètes. Plus particulièrement, dans cette étude nous nous intéressons à la résolution de trois problèmes combinatoires difficiles : le « Bin-Packing », la « Réaffectation de machines » et la « Gestion des rames sur les sites ferroviaires ». Le premier est un problème d'optimisation classique et bien connu, tandis que les deux autres, issus du monde industriel, ont été proposés respectivement par Google et par la SNCF. Pour chaque problème, nous proposons une approche heuristique basée sur la recherche locale et nous comparons nos résultats avec les meilleurs résultats connus dans la littérature. En outre, en guise d'introduction aux méthodes de recherche locale mise en œuvre dans cette thèse, deux métaheuristiques, GRASP et Recherche Tabou, sont présentées à travers leur application au problème de la couverture minimale
This Ph.D. thesis concerns algorithms for Combinatorial Optimization Problems. In Combinatorial Optimization Problems the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. Specifically, in this research we consider three different problems in the field of Combinatorial Optimization including One-dimensional Bin Packing (and two similar problems), Machine Reassignment Problem and Rolling Stock Problem. The first one is a classical and well known optimization problem, while the other two are real world and very large scale problems arising in industry and have been recently proposed by Google and French Railways (SNCF) respectively. For each problem we propose a local search based heuristic algorithm and we compare our results with the best known results in the literature. Additionally, as an introduction to local search methods, two metaheuristic approaches, GRASP and Tabu Search are explained through a computational study on Set Covering Problem

APA, Harvard, Vancouver, ISO, and other styles

17

Fournier, David. "Metro regenerative braking energy : optimization through rescheduling : mathematical model and greedy heuristics compared to MILP and CMA-ES." Paris 7, 2014. http://www.theses.fr/2014PA077144.

Full text

Abstract:

The use of regenerative braking is a key factor to reduce the energy consumption of a metro line. In the case where no device can store the energy produced during braking, only the metros that are accelerating at the same time can benefit from it. Maximizing the power transfers between accelerating and braking metros thus provides a simple strategy to benefit from regenerative energy without any other hardware device. In this thesis, we use a mathematical timetable model to classify various metro energy optimization rescheduling problems studied in the literature and prove their NP-hardness by polynomial reductions of SAT. We then focus on the problem of minimizing the global energy consumption of a metro timetable by modifying the dwell times in stations. We present a greedy heuristic algorithm which aims at locally synchronizing braking metros along the timetable with accelerating metros in their time neighbourhood, using a non-linear approximation of energy transfers. On a benchmark of six small size timetables, we show that our greedy heuristics performs better than CPLEX using a MILP formulation of the problem, even when it is able to prove the optimality of a linear approximation of the objective function. We also show that it runs ten times faster than a state-of-the-art evolutionary algorithm, called the covariance matrix adaptation evolution strategy (CMA-ES), using the same non-linear objective function on these small size instances. On real data leading to 10000 decision variables on which both MILP and CMA-ES do not provide solutions, the dedicated algorithm of our thesis computes solutions with a reduction of energy consumption ranging from 5% to 9%
The use of regenerative braking is a key factor to reduce the energy consumption of a metro line. In the case where no device can store the energy produced during braking, only the metros that are accelerating at the same time can benefit from it. Maximizing the power transfers between accelerating and braking metros thus provides a simple strategy to benefit from regenerative energy without any other hardware device. In this thesis, we use a mathematical timetable model to classify various metro energy optimization rescheduling problems studied in the literature and prove their NP-hardness by polynomial reductions of SAT. We then focus on the problem of minimizing the global energy consumption of a metro timetable by modifying the dwell times in stations. We present a greedy heuristic algorithm which aims at locally synchronizing braking metros along the timetable with accelerating metros in their time neighbourhood, using a non-linear approximation of energy transfers. On a benchmark of six small size timetables, we show that our greedy heuristics performs better than CPLEX using a MILP formulation of the problem, even when it is able to prove the optimality of a linear approximation of the objective function. We also show that it runs ten times faster than a state-of-the-art evolutionary algorithm, called the covariance matrix adaptation evolution strategy (CMA-ES), using the saure non-linear objective function on these small size instances. On real data leading to 10000 decision variables on which both MILP and CMA-ES do not provide solutions, the dedicated algorithm of our thesis computes solutions with a reduction of energy consumption ranging from 5% to 9%

APA, Harvard, Vancouver, ISO, and other styles

18

Antonio, Julien. "Les problèmes de placement : étude et résolution de quelques problèmes réels." Metz, 1997. http://docnum.univ-lorraine.fr/public/UPV-M/Theses/1997/Antonio.Julien.SMA9702.pdf.

Full text

Abstract:

L'objectif de cette thèse consiste à caractériser les problèmes de découpe tels qu'ils se présentent dans l'industrie et d'apporter des méthodes efficaces pour résoudre ces problèmes. Tel qu'ils se présentent dans la littérature, ces problèmes consistent à positionner un sous-ensemble de barres filles sur un sous-ensemble de barres mères de plus grandes tailles de façon à minimiser le nombre de barres mères utilisées. Cependant, pour résoudre les problèmes de notre partenaire industriel, nous avons dû prendre en compte un large éventail de contraintes et de critères. Afin de les satisfaire, nous avons développé deux groupes de méthodes: (I) les méthodes par construction, applicables lorsque les couts ne sont pas mesurables. Elles réalisent le placement pas à pas en fonction des paramètres de contrôle du système fournis par les utilisateurs. Elles s'apparentent aux méthodes de traitement des problèmes avec critères qualitatifs souvent utilisées par les industriels ; (II) les méthodes inspirées de la programmation dynamique (dynamic programming oriented methods - dpo) sont utilisées lorsque des couts peuvent être associes aux solutions. Elles sont utilisées lorsque l'ensemble des critères à optimiser peuvent s'exprimer à l'aide d'un cout unique. Les algorithmes développés ont été implantes avec succès chez notre partenaire industriel. Les méthodes dpo sont particulièrement efficaces (gain de 8% sur nos exemples) pour résoudre des problèmes comportant de nombreux critères
The purpose of this thesis is to characterize real life cutting stock( or packing) problems and to provide efficient methods for a large spectrum of industrial problems. Usually, the packing problem consists in assigning a subset of out put bars to a subset of input bars to minimize the number of input bars used. Since our concern is to solve industrial problems, we have been obliged to take into account a large number of contraints and criteria. To face this complex situation, two types of approaches have been introduced, that is : building methods, used in the case of criteria which are not precisely defined ; in this case, we propose some parameters which can influence the characteristics of the solutions. These methods are close to the way of thinking of the users. The dynamic programming oriented methods (DPO), which are put at work when the various criterion values can be combined into a unique cost. The developed methods are set up successfully in the factories of our industrial partner. The DPO methods are particularly efficient (8% saving on ours examples) for solving problems with several real-life criteria

APA, Harvard, Vancouver, ISO, and other styles

19

Simon, François. "Evaluation de la performabilité des systèmes de production et des systèmes temps réel par réseaux de Petri stochastiques géneralisé." Mulhouse, 1996. http://www.theses.fr/1996MULH0456.

Full text

Abstract:

Cette thèse décrit les travaux réalisés dans le domaine de la modélisation et de l'évaluation de la performabilité (performance-disponibilité) de systèmes informatiques temps réel et des systèmes de production à l'aide de modèles bases sur les réseaux de Petri stochastiques généralisés (rdpsg). Le modèle du système est décomposé en deux sous-systèmes, l'un décrivant le comportement vis-à-vis des fautes et des réparations (modèle de structure), l'autre modélisant l'aspect performance et les caractéristiques temps réel. Nous montrons la génération automatique du modèle de structure qui donne les multiples cas de défaillances pour lesquels nous proposons une méthode pour réduire le nombre de vérification du critère d'opportunité (probabilité de respect de la contrainte temporelle spécifiée). L'analyse se concentre en premier sur les configurations de fonctionnement dégradées. Cette étape du processus de modélisation est appelée vérification intra configuration. Ensuite, la vérification inter configurations concerne les passages entre les configurations qui sont classées par type d'éléments défaillants. La méthode est illustrée sur trois exemples ayant fait l'objet de publications. Le premier système est un atelier flexible de production de tambour d'impression ayant une structure à tolérance de fautes avec machines redondantes et fonctionnant en parallèle. Le deuxième est un système de production de portière à structure série qui est analysé par modèles équivalents. Le troisième système à base de transputers présente des caractéristiques temps réel pour lequel l'aspect répartition de taches est approfondi.

APA, Harvard, Vancouver, ISO, and other styles

20

Wahl, François. "Un environnement d'aide aux ingénieurs basé sur une architecture en taches et sur un module de visualisation de courbes. Application à la conception de procédés de raffinage." Marne-la-vallée, ENPC, 1994. https://pastel.archives-ouvertes.fr/tel-00529958.

Full text

Abstract:

Dans le domaine du génie chimique, les ingénieurs tracent des courbes pour analyser les données recueillies. Une fois validée, cette connaissance est exploitée, en combinaison avec d'autres savoirs, sous forme de taches. Cette thèse présente une architecture capable d'enchainer n'importe quel type de taches et de visualiser des courbes, appliquée à un problème d'aide à la conception de procédé de raffinage. L'architecture proposée repose sur une analyse objets des raisonnements, ou figurent les notions de relations (inversibles ou non) et de flux du point de vue statique, de problèmes et de taches du point de vue dynamique. Le module de visualisation exploite toutes les sortes de relations entre les variables et s'appuie sur des méthodes élaborées de tracé, dont deux sont nouvelles: la première s'inspire d'exemples a priori comme dans le raisonnement à base de cas, la seconde utilise les notions de monotonie et de concavité pour déduire des lignes dans un ensemble de points. L'application est exposée dans le détail et conduit à une analyse des problèmes de conception, et nous avons développé notamment une nouvelle classification de ces systèmes

APA, Harvard, Vancouver, ISO, and other styles

21

Arkhipov, Dmitrii. "Planification socio-responsable du travail dans les chaînes de montage d'aéronefs : comment satisfaire à la fois objectifs ergonomiques et économiques." Thesis, Toulouse 3, 2019. http://www.theses.fr/2019TOU30107.

Full text

Abstract:

Dans cette thèse, le problème de planification des tâches dans les chaînes de montage des aéronefs est étudié. Ces lignes de production sont principalement manuelles et tactées. L'échec de la livraison dans les délais pouvant entraîner des pénalités importantes pour le fabricant, il est essentiel de respecter le calendrier de chaque poste de travail en tenant compte à la fois de critères économiques et ergonomiques. Ce problème de planification peut être considéré comme un problème généralisé de planification de projets avec contraintes de ressources (RCPSP). Dans un premier temps, nous passons en revue les méthodes ergonomiques existantes qui peuvent être utilisées pour évaluer la charge de travail physique dans les lignes de production et examinons leur applicabilité au contexte des chaînes de montage d'aéronefs avec des temps de cycle longs. Sur la base de cette évaluation, nous développons des modèles mathématiques à introduire dans les problèmes considérés du RCPSP afin de prendre en compte l'impact ergonomique sur les opérateurs. Tenant compte de ces contraintes ergonomiques, le problème industriel initial est modélisé comme un RCPSP avec des contraintes et des objectifs spéciaux intégrant à la fois des aspects économiques et ergonomiques. Plusieurs formulations avec des opérateurs polyvalents, des ressources avec des capacités dépendantes du temps, des contraintes sur les facteurs ergonomiques et des tâches multimodales ordonnées par des relations de précédence complexes sont considérées. Des modèles de programmation par contraintes et de programmation linéaire en nombres entiers ont été développés pour ces formulations. Afin d'améliorer les procédures de solution, de nouvelles techniques de propagation de contraintes sont proposées et mises en œuvre. Un nouvel algorithme pour le calcul de la borne inférieure est également développé. L'efficacité des modèles et méthodes présentés est validée par des expériences numériques
In this thesis, the scheduling problem of tasks in aircraft assembly lines is studied. These production lines are mainly manual and paced. Since the failure of delivery on time may result in significant penalties for the manufacturer, it is crucial to meet the schedule at each workstation taking into account both economic and ergonomic criteria. This scheduling problem can be considered as a generalized Resource-Constraints Project Scheduling Problem (RCPSP). Firstly, we review the existing ergonomic methods that can be used to evaluate the physical workload in production lines and examine their applicability to the context of aircraft assembly lines with long takt times. On the basis of this evaluation, we develop mathematical models to be introduced in considered RCPSP problems in order to take into account the ergonomic impact on the operators. Taking into consideration these ergonomic constraints, the original industrial problem is modeled as a RCPSP with special constraints and objectives integrating both economic and ergonomic aspects. Several formulations with multi-skilled operators, resources with time-dependent capacities, constraints on ergonomic factors and multi-mode tasks ordered by precedence relations with time lags are considered. Constraint Programming and Integer Linear Programming models are developed for these formulations. In order to enhance the solution procedures, novel constraint propagation techniques are proposed and implemented. A new algorithm for lower bound calculation is developed as well. The efficiency of presented models and methods are validated through numerical experiments

APA, Harvard, Vancouver, ISO, and other styles

22

Djerid-Zahra, Lamia. "Hybridation d'algorithmes génétiques et de méthodes classiques de recherche opérationnelle pour résoudre des problèmes d'ordonnancement." Vandoeuvre-les-Nancy, INPL, 1997. http://www.theses.fr/1997INPL103N.

Full text

Abstract:

Afin de résoudre de manière efficace des problèmes d'ordonnancement (de type disjonctif) NP-difficiles, nous avons conçu une famille de méthodes hybrides intégrant des algorithmes génétiques dans des méthodes classiques de recherche opérationnelle (procédure par séparation et évaluation ou PSE). Un nouveau codage direct (à tout chromosome correspond une et une seule solution du problème) ternaire (et non pas binaire) sert de structure de données à toutes les méthodes utilisées. De nouveaux operateurs génétiques définis sur ce codage permettent de conserver des sous-ensembles de contraintes de précédence imposés par la PSE ou par des propriétés de dominance. Ces nouveaux concepts ont été implémentés de manière différente sur un problème d'ordonnancement de projet avec des ressources existant en un seul exemplaire (minimisation de la durée totale) et sur le problème de base à une machine pour la minimisation de la somme des retards. Par ailleurs, nous avons étudié la conservation des (bons) schémas symboliques pour les problèmes de permutation de manière analytique et expérimentale (espérance mathématique d'indicateurs de performance appliqués à des croisements génétiques), ceci afin d'améliorer les performances de l'algorithme génétique par le bon choix de ses opérateurs internes.

APA, Harvard, Vancouver, ISO, and other styles

23

Bostel, Nathalie. "Méthodes de simulation et d'optimisation appliquées à la gestion opérationnelle des chantiers de transbordement rapide." Châtenay-Malabry, Ecole centrale de Paris, 1996. http://www.theses.fr/1996ECAP0461.

Full text

Abstract:

Nous nous sommes interessés dans cette thèse, à résoudre dans sa globalité le problème de gestion opérationnelle des chantiers de transbordement rapide fer-fer. Pour cela nous avons étudié les deux problématiques principales, qui constituent les deux parties de cette recherche : l'optimisation des emplacements de chargement initial et de reprise des conteneurs, l'ordonnancement des mouvements des équipements, et nous avons recherché des solutions appropriées satisfaisantes.

APA, Harvard, Vancouver, ISO, and other styles

24

Perrot, Nancy. "Stratégies de génération de colonnes en programmation entière pour le problème de découpe et ses variantes." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2005. http://tel.archives-ouvertes.fr/tel-00011657.

Full text

Abstract:

This thesis gives a comprehensive view of the scope of formulations and
related solution approaches for the cutting stock problem (CSP) and its
variants. The focus is on branch-and-price approaches. Specialized
algorithms are developed for knapsack subproblems that arise in the
course of the algorithm. Thorough numerical tests are used to identify good strategies
for initialization, stabilization, branching, and producing
primal solutions. Industrial variants of the
problem are shown to be tractable for a branch-and-price approach.

The models studied are the following: the standard cutting stock and
bin packing problems, a variant in which the production levels lie in
a prescribed interval of tolerance, the multiple width cutting stock
problem in which stock pieces are of different size, a variant with
additional technical constraints that arise typically in industrial
applications, and a variant where the number of distinct cutting
patterns used is minimized given a waste threshold.

First, we consider various formulation of the Cutting Stock Problem
(CSP): different models of the knapsack subproblem can be exploited to
reformulate the CSP. Moreover, we introduce different ways of
modeling local exchanges in the solution (primal exchanges imply dual
constraints that stabilize the column generation procedure). Some
models are shown to be valid integer programming (IP) reformulations while others define
relaxations. The dual bounds defined by their LP solution are compared
theoretically.

Then, we study the variants of the knapsack subproblem that arise
in a column generation approach to the CSP. The branching constraints
used in the branch-and-price algorithm can result in class bound and
setup cost or the need for a binary decomposition in the subproblem.
We show how standard knapsack solvers (dynamic programming approach and specialized
branch-and-bound algorithm) can be extended to these variants of the
knapsack problem.

Next, we discuss some branch-and-price implementation strategies. We compare
different modes of initialization of the column generation procedure, we present our numerical study of various stabilization
strategies to accelerate convergence of the procedure. We compare in particular the impact of the various ways of introducing
local exchanges in our primal model and other stabilization techniques
such as dual solution smoothing techniques or penalization from a
stability center that prevent the fluctuation of the dual variables.
To generate the columns we study different strategies based on the use of heuristic columns or on a multiple generation of columns.
We also consider the use of heuristics based on column generation to find a primal bound. These are compared to a classic constructive heuristic. Then, we compare the different branching rules that are used in the branch-and-price procedure.

Finally, we present numerical results on two industrial applications that
correspond to the variant with technical restrictions for which we
minimize first the waste and then the number of setups.

APA, Harvard, Vancouver, ISO, and other styles

25

Stoica, Dragos Constantin. "Analyse, représentation et optimisation de la circulation des avions sur une plate-forme aéroportuaire." Phd thesis, Toulouse, INPT, 2004. http://oatao.univ-toulouse.fr/7298/1/stoica.pdf.

Full text

Abstract:

Au cours des dernières décennies, la demande de trafic au niveau des aéroports a augmenté régulièrement à tel point que le trafic au sol est devenu critique pour la sécurité et l'efficacité des opérations aéroportuaires. Cette thèse propose une approche à deux niveaux pour l'analyse et l'optimisation du trafic avion au sol sur les aéroports. Elle est divisée en trois parties : - La première partie introduit la problématique générale et son environnement - La deuxième partie traite la gestion à moyen terme du trafic au sol des avions. Une approche globale pour estimer la capacité théorique et la capacité pratique du trafic avion est proposée. Celle-ci met en oeuvre une approche d'optimisation du flux dans un réseau qui conduit à la formulation de différents problèmes de programmation mathématique - La troisième partie traite du niveau tactique et une approche adaptative est développée pour définir les routes et les horaires associés aux mouvement d'arrivée ou de départ des avions. Une approche de résolution opérationnelle est alors proposée.

APA, Harvard, Vancouver, ISO, and other styles

26

Gueye, Serigne Abdoulaye. "Linéarisation et relaxation lagrangienne pour problèmes quadratiques en variables binaires." Avignon, 2002. http://www.theses.fr/2002AVIG0131.

Full text

Abstract:

Un problème quadratique en variables binaires est un problème d'optimisation en variables binaires consistant à minimiser une fonction objectif quadratique sous des contraintes linéaires. Dans le cas général, c'est un problème dificile à résoudre de manière exacte (NP- difficile), trouvant de nombreuses applications pratiques. La résolution exacte du problème passe par la détermination de bornes inférieures qu'il convient d'intégrer dans des schémas de séparation et évaluation progressive (ou Branch-and-Bound). Plusieurs techniques, allant de la programmation semi-définie positive à l'optimisation globale, sont utilisées pour déterminer ces bornes. Nous nous sommes particulièrement intéressés aux méthodes lagrangiennes et aux techniques de linéarisation. Nous avons traité dans cette thèse deux instances particulières du problème : "la bipolarisation de graphes avec contrainte de cardinalité" et "le problème quadratique en variables binaires sans contrainte". Pour la bipartition de graphes, nous avons proposé une démarche hybride mêlant relaxation lagrangienne et linéarisation de problème. Les tests numériques, issus de l'algorithme résultant, ont montré des améliorations significatives par rapport à certaines techniques existantes. Pour le problème quadratique en variables binaires sans contrainte, des études sur les techniques de linéarisation ont été effectuées. Elles consistent à remplacer la fonction objectif quadratique par une forme linéaire, grâce à l'ajout de variables permettant de remplacer les parties quadratiques de la fonction. L'ajout de ces variables entraînent [sic] aussi l'ajout de contraintes visant à s'assurer de la validité du remplacement. Après étude et tests des linéarisations existantes, nous unifions ces techniques dans un schéma général de linéarisation. De nouveaux modèles ont, grâce à ce schéma , vu le jour et améliorent significativement les résultats numériques des formulations linéaires précédentes
A quadratic 0/1 problem is an optimization problem where a quadratic objective function, subject to linear contraints, have to be minimized. In the general case, the problem is NP-Hard and arises in mathematical modeling of several real world applications. Exact methods, for solving the problem, are based on Branch-and-Bound scheme for which the corresponding lower bands may be divided in four groups : Semidefinite Relaxations, Lagrangean Relaxations, Posiform Methods and Linearization Techniques. In this thesis, linearization and lagrangean relaxation techniques have been particularly studied. Two instances of the general quadratic problem have been considered : "the graph bipartitioning problem and the unconstrained quadratic 0/1 problem". For the graph bipartitioning problem, an hybrid scheme, mixing linearization and lagrangean relaxations, have been proposed. The new scheme provides significative improvements compared to the state-of-the-art approaches. For the unconstrained quadratic 0/1 problem, a general linearization framework, unifying and generalizing the existing linearization techniques have been proposed. Based on this new framework, including many linear models, some new linearizations have been tested. In comparison with existing linearizations, many encouraging results have been noticed in the numerical tests

APA, Harvard, Vancouver, ISO, and other styles

27

Assane, Soumare. "Gestion de la production à coûts concaves : quelques problèmes liés à la possibilité de rupture de stock." Paris 9, 1986. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1986PA090014.

Full text

Abstract:

On étudie les équations de la programmation dynamique dans le cas déterministe avec des couts concaves en horizon infini et avec possibilité de rupture de stock. Ces équations sont utilisées dans le cas stationnaire en vue d'obtenir la formule de Wilson avec possibilité de rupture. On aborde ensuite le même problème dans les cas impulsionnel et stochastique

APA, Harvard, Vancouver, ISO, and other styles

28

Régnier, Pascal. "Conduite réactive des systèmes de production : intégration des régimes périodique et événementiel." Bordeaux 1, 1998. http://www.theses.fr/1998BOR10520.

Full text

Abstract:

De par la forte evolution de l'environnement de l'entreprise, cette derniere doit faire face aux evenements omnipresents de maniere reactive, c'est a dire de maniere rapide et coherente. Des solutions existent pour la prise en compte des evenements au niveau strategique et au niveau de conduite temps-reel de l'entreprise. A l'inverse, la zone intermediaire (gestion de production) reste aujourd'hui encore peu etudiee. Pour cette zone, nous proposons une structure de conduite mixte multi-niveaux, ayant un regime de fonctionnement a la fois periodique (objectif de coherence) et evenementiel (objectif de promptitude) : une formalisation des liens entre les evenements et la notion de periode est proposee ainsi qu'une evaluation du delai de reaction. La periode de decision, definie dans le modele grai, est ainsi etendue : nous definissons notamment les notions de periode semantique et dynamique pour une caracterisation du niveau de conduite devant reagir, lors du processus de reaction aux evenements. Suite a une caracterisation des evenements, basee sur la notion de criticite, trois types de reaction sont proposes : la reaction hors periode, la modification structurelle (evolution des valeurs de periodes des niveaux de decision), la mise en place de centres de decision adhoc (cooperation entre differents centres de decision). La demarche definie structure l'utilisation des outils proposes dans la mise en oeuvre des reactions. Deux applications industrielles permettent d'illustrer et de valider la methode de conduite mixte proposee.

APA, Harvard, Vancouver, ISO, and other styles

29

Vignier, Antony. "Contribution à la résolution des problèmes d'ordonnancement de type monogamme, multimachine (Flow-Shop Hybride)." Tours, 1997. http://www.theses.fr/1997TOUR4026.

Full text

Abstract:

Ce travail s'intéresse aux problèmes qui se posent dans les ateliers production en ligne et plus précisément sur ceux ou les gammes de fabrication de produits fabriqués sont identiques pour tous les produits (Flow-Shop). De plus, une opération de la gamme peut être réalisée par une ou plusieurs machines à chaque étage. L'atelier comporte K étages. En vue d'une plus grande efficacité d'intervention, une notation est proposée. L'état de l'art permet de mettre en évidence le peu de problèmes actuellement résolus et surtout l'ensemble de ceux qui restent à traiter des méthodes de résolution sont proposées pour résoudre différents problèmes prenant en compte des contraintes et de critères divers. Enfin, une plateforme d'aide à la construction progressive de procédures par séparation et évaluation et de tests (PCPSET) pour résoudre les problèmes de Flow-Shops Hybrides.

APA, Harvard, Vancouver, ISO, and other styles

30

Duquesne, Christophe-Marie. "Intégration du déploiement de flotte et du service aux passagers dans la gestion de la planification pour compagnie aérienne." Phd thesis, Université de Grenoble, 2013. http://tel.archives-ouvertes.fr/tel-00953136.

Full text

Abstract:

Étant donnés un planning aérien et des prévisions de demande, le problème d'affectation de flotte aérienne consiste à déterminer la meilleure façon de répartir les types d'appareils sur les vols. Cette répartition a un impact majeur sur le profit d'une compagnie aérienne, puisqu'elle détermine les quantités de places disponibles sur les itinéraires du réseau aérien, ainsi que le coût de fonctionnement de celui-ci. Des décennies de recherche ont rendues les modélisations de ce problème de plus en plus réalistes. Cette thèse s'inscrit dans la continuité de ces recherches en considérant le problème d'affectation de flotte dans un contexte où les demandes des passagers sont incertaines. Nous proposons dans un premier temps une étude autour des deux modèles de la littérature les plus utilisés dans l'industrie, FAM et IFAM. Nous montrons que FAM peut être vu comme une Relaxation Lagrangienne de IFAM, avec des multiplicateurs Lagrangiens particuliers. Nous implémentons cette relaxation, et nous appliquons des résultats connus pour l'étendre en une génération de colonnes basée sur une décomposition de Dantzig-Wolfe de IFAM. Nous étudions ensuite les effets que l'imprécision des prévisions peut avoir sur la performance d'IFAM, et nous présentons au terme de cette étude une nouvelle approche pour modéliser le problème d'affectation de flotte. Notre modèle, Market Driven Fleet Assignment Model (MDFAM), intègre les demandes par itinéraires comme variables de décision, et contraint ces demandes plutôt que de les considérer comme une entrée fixe. Nous appelons les contraintes résultantes des contraintes de Marché. Nous illustrons la flexibilité de cette approche à travers divers exemples, et nous proposons une série d'expériences visant à déterminer quelles sont les contraintes de marché donnant les meilleurs résultats. Nous comparons les différents modèles, et nous montrons que MDFAM peut atteindre des niveaux de performance similaires à ceux offert par IFAM, tout en étant plus facile à utiliser et à implémenter.

APA, Harvard, Vancouver, ISO, and other styles

31

Levasseur, Nicolas. "Heuristiques de recherche pour la résolution des WCSP." Caen, 2008. http://www.theses.fr/2008CAEN2071.

Full text

Abstract:

Les Weighted Constraint Satisfaction Problem (WCSP) qui sont une généralisation à l’optimisation des CSP, sont souvent résolus par des méthodes de recherche arborescentes combinées avec des algorithmes de filtrage ou recherches locales. Bien que de nombreuses heuristiques génériques aient été proposées dans les CSP, cela est loin d’être le cas pour les WCSP. L’objectif de ce travail consistait à mettre en oeuvre de nouvelles heuristiques génériques, adaptées aux WCSP et guidant efficacement les méthodes de résolution. Pour les recherches arborescentes, nous avons proposé plusieurs heuristiques de choix de valeur et de variable basées sur un critere global, la H-Quality, moins indépendant du mécanisme de filtrage (critère local). Pour les méta-heuristiques à voisinage variable (VNS), nous avons proposé diféerentes heuristiques de voisinage basées sur la notion de degré de liberté qui dépendent de la topologie du graphe de contraintes. Puis, nous avons proposé d'étendre celles-ci aux WCSP afin de tenir compte du coût des contraintes. Afin de valider nos contributions, nous avons réalisé des expérimentations sur des problèmes réels d’affectation de liens radio (CELAR), aléatoires avec structures (GRAPH) et purement alétoires. De ces expérimentations, il ressort que le critère d’H-Quality est pertinent pour guider les heuristiques de choix de valeur, et intéressant pour les heuristiques de choix de variable sur les instances à forte connectivité et forte densité. Les heuristiques de choix de voisinage augmentant le degré de liberté des variables et tenant compte des coûts des contraintes offrent de meilleurs résultats
Weighted Constraint Satisfaction Problem (WCSP) which are a generalization to the optimization of CSP, are usually solved by tree search methods combined with filtering algorithms or local search methods. Although many generic heuristics have been proposed for such methods in the CSP framework, this is not the case for WCSP yet. Our objective was to define and implement new generic heuristics dedicated to WCSP in order to efficiently guide search methods. For tree search methods, we have proposed several value ordering and variable ordering heuristics based on a global criterion, the H-Quality, which is less dependent on filtering mechanisms. For VNS based metaheuristics, we have proposed new neighborhood heuristics based on the concept of degree of freedom wich depend on the topology of graph of constraints. Then, we have proposed to extend them to the WCSP framework in order to take into account cost of constraints. In order to validate our contribution, we have made experiments on real-world problems (Radio Link Frequency Assignment Problem) (CELAR), random structured instances (GRAPH) and random instances. From these experiments, it appears that the concept of H-Quality is a relevant criterion to guide value ordering heuristics and interesting to guide variable ordering heuristics for high connectivity and high density instances. Neighborhood heuristics based degree of freedom and taking into account cost constraints offer better performance

APA, Harvard, Vancouver, ISO, and other styles

32

Simonin, Cécile. "Planification de ressources multiples pour la recherche d’information." Rennes 1, 2008. ftp://ftp.irisa.fr/techreports/theses/2008/simonin.pdf.

Full text

Abstract:

Ce travail de thèse s’inscrit dans le domaine de la théorie de la recherche (Search Theory). Cette discipline traite du problème de la recherche de cibles (mobile ou non) par placement optimisé des moyens de détection affectés à cette recherche. Elle a été introduite par B. O. Koopman durant la seconde guerre mondiale, pour la lutte anti-sousmarine. Nous considérons ici le problème de détection de cibles markoviennes dans le cas où les ressources disponibles (capteurs) sont peu nombreuses au regard de la taille de l’espace de recherche dans lequel la ou les cibles sont cachées. Il est alors nécessaire de diviser l’espace de recherche en zones, auxquelles les ressources doivent ensuite être allouées. Cela nous conduit à considérer des problèmes d’optimisation hiérarchiques, peu étudiés dans la littérature. Par ailleurs, deux problématiques majeures de la recherche du renseignement, jusqu’alors peu considérées, sont étudiées. Il s’agit d’une part de la détection-confirmation de cibles et d’autre part de la détection de cibles multiples
This PhD is related to Search Theory, which is the field of Operations Research which deals with maximizing the detection of one or more (static or moving) targets, by optimizing the detection resources placement. Our work deals with the detection of Markovian targets, when search resources are scarce compared to the size of the space of search where targets are hidden. The space of search must then be partitioned into search zones, to which search resources (sensors) must be allotted. It results in hierarchical search problems, which have not been much studied in the literature. Two problems of importance for the Intelligence community are stated. First, we consider cross-cueing search. In such problems, a target needs to be detected at the same time by two different sensors. We also consider the cross-cueing search in a monosensor framework: a target must be detected by the same sensor at consecutive time periods. Then, the multitarget search is detailed. In this kind of problems, the goal is to optimize search of more than one targets by means of a unique sensor

APA, Harvard, Vancouver, ISO, and other styles

33

Hijazi, Hassan. "Optimisation non-linéaire mixte en nombres entiers pour la conception de réseaux en télécommunications." Thesis, Aix-Marseille 2, 2010. http://www.theses.fr/2010AIX22107/document.

Full text

Abstract:

Dans cette thèse, nous nous basons sur les outils apportés par la programmation mathématique afin de modéliser et résoudre des problèmes relevant du domaine des télécommunications. Notre premier objectif consiste à se conformer aux contraintes réelles, prenant en compte les aléas courants, afin de définir des stratégies optimales de routage et de planification dans les réseaux. Les contributions théoriques concernent l'optimisation convexe non linéaire mixte en nombres entiers. Parmi les résultats majeurs, nous établissons en particulier : *une formulation compacte des contraintes de type "on/off" qui s'écrivent f(x) ≤ 0 si z = 1,I ≤ x ≤ u si z = 0, basée sur une nouvelle caractérisation de l'enveloppe convexe de l'union d'un hyper-rectangle et d'un ensemble convexe dans l'espace des variables d'origine. * Une prise en compte de l'incertitude au niveau des fonctions additives ∑i(fi(xi) + vi) ≤ 0 où vi représente une perturbation bornée de chaque fonction univarée fi(xi). * Un algorithme spécialisé pour les problèmes d'optimisation non-linéaires mixtes en nombres entiers faisant intervenir des fonctions additives. D'un point de vue industriel, ces apports théoriques nous permettent de nous rapprocher de notre objectif consistant à définir des stratégies de gestion optimales pour des réseaux de télécommunications plus fiables. La qualité de service perçue par le client est modélisée par une fonction délai de bout en bout, différentiée selon le type de service et dépendant de la congestion au niveau de chaque lien
In our work, we rely on the powerful arsenal of mathematical programming theory to model telecommunication problems and devise efficient methods for solving them. Our goal is to comply to real life constraints when defining optimal routing strategies and designing efficient capacity planning tools. Theoretical contributions apply the field of Mixed Integer Non-Linear Optimization. Among relevant results, let us mention :Explicit formulations of convex hulls in disjunctive programming, generalizing the famous perspective formulationsTractable compact formulations of problems featuring inerval uncertainty in Robust OptimizationAn efficient Outer-Inner approximation algorithm for solving large families of separable mixed Integer Non-Linear Programs (MINLPs) and Second Order Cone Programs (SOCPs), outperforming state-of-the-art commercial solvers.In the application part, our work aims at introducing reliable telecommunication networks, offering appropriate and guaranteed Quality of Service to all its customers. Today, Wide Access Networks (WAN), Virtual Private Networks (VPN) or IP-based Backbones carry a wide range services, namely: voice, video streaming and data traffic. Each one of these contents has its own performance requirements. Unfortunately, best effort algorithms are implemented at all levels, offering no guarantee for delay sensitive applications. Is it possible to build routing strategies guaranteeing upper bounds on source-to-destination delays? Can we make these routing protocols to delay variation ? Does service differentiation affect capacity planning decisions ? Answers to these questions will be developed in this thesis

APA, Harvard, Vancouver, ISO, and other styles

34

Toumi, Khaled. "Aide à la décision dans le cadre de la problématique de la description : une approche inductive pour décrire et expliquer." Paris 9, 1996. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1996PA090074.

Full text

Abstract:

Le travail effectué dans cette thèse s'inscrit dans le cadre de l'aide à la décision et plus précisément dans celui de la problématique de la description. Prenant appui sur les méthodes inductives et les concepts de la théorie des ensembles approximatifs, notre travail a consisté à décrire et à expliquer les informations représentées par une collection d'exemples. La connaissance que l'on peut en extraire est tributaire de la méthode utilisée. L'explication et la description passent alors par l'extraction des régularités, les tendances fortes, les schémas dominants qui se trouvent dans les données, et ce eu égard au niveau d'expertise de l'utilisateur et/ou ses exigences. Dans ce cadre d'étude, nous nous sommes particulièrement intéressé au traitement des valeurs manquantes et nous avons proposé une nouvelle approche. Nous illustrons les réflexions générales constituant notre thèse par une application relative au problème des choix modaux pour le transport de marchandises.

APA, Harvard, Vancouver, ISO, and other styles

35

Lebbar, Maria. "Résolution de problèmes combinatoires dans l'industrie : apport de la programmation mathématique et des techniques de décomposition." Châtenay-Malabry, Ecole centrale de Paris, 2000. http://www.theses.fr/2000ECAP0674.

Full text

Abstract:

L'optimisation des ressources dans l'industrie conduit à résoudre des problèmes combinatoires complexes et de grande taille. L'objectif de notre travail est de proposer des solutions à des problèmes industriels réels. Pour cela, des algorithmes ont été développés dans le cadre de modèles exacts basés sur les techniques de la programmation linéaire en nombre entiers et la programmation linéaire généralisée. Des approches de décomposition temporelle ont été également étudiées. Nous avons eu l'occasion de traiter dans cette thèse quatre problèmes qui s'inscrivent dans le cadre de problèmes d'affectation de ressources et de planification : - un problème d'affectation de ressources avec contraintes de maintenance. C'est un problème NP-Difficile à cause notamment des contraintes de maintenance et de la propriété de substitution. Nous l'avons résolu avec la technique de génération de colonnes. - un problème de planification d'un système de télécommunication par satellites. Nous avons proposé un modèle exact pour ce problème nouveau. L'approche de résolution adoptée est basée sur une technique de génération de colonnes et de contraintes, associée à une heuristique de décomposition temporelle. - un problème de construction d'horaires de bus « Graphicage automatique », pour lequel nous proposons un modèle exact sous forme d'un programme linéaire en nombres entiers. La méthode de résolution choisie est basée sur une heuristique de décomposition temporelle associée au programme linéaire en nombres entiers. - un problème de planification de la fabrication de véhicules a moyen et court terme : problème de séquencement de voitures généralisé. Il s'agit d'une nouvelle définition du problème par rapport à celles des travaux relevés dans la littérature. Il a été décomposé en deux sous problèmes résolus respectivement par la programmation linéaire en nombres entiers et une heuristique d'optimisation locale.

APA, Harvard, Vancouver, ISO, and other styles

36

Melliti, Tarek. "Interopérabilité des services Web Complexes : Application aux systèmes multi-agents." Paris 9, 2004. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=2004PA090024.

Full text

Abstract:

Ce travail porte sur la formalisation de l'interopérabilité opérationnelle entre deux systèmes communicants et plus particulièrement entre les services Web composites. La formalisation retranscrit la possibilité d'une interaction correcte entre deux systèmes communicant utilisant des spécifications différentes. Cette formalisation se matérialise en trois étapes: Premièrement, nous définissons l'observabilité comme référence d'abstraction pour exprimer la sémantique de différentes spécifications. Ensuite, nous proposons une relation de conformité sur les états de deux systèmes qui retranscrit la notion d'interaction correcte. Enfin, nous définissons un algorithme de synthèse qui, étant données la spécification d'un service composite et sa sémantique observable soit génère un client correct soit détecte une ambiguïté. Le travail a donné lieu à la réalisation d'une plate-forme de gestion d'interaction pour les services composites et un environnement d'intégration de systèmes multi-agents
This work concerns the formalization of operational interoperabilility between two communicating systems and particularly between the composite services. Formalization retranscribes the possibility of a correct interaction between two communicating systems using different specifications. This formalization materializes in three steps: Firstly, we define the observability as a reference of abstraction to express the semantics of different specification. Then, we propose a relation of conformity on the states of two systems which retranscribes the concept of correct interaction. Lastly, we define a synthesis algorithm which, being given the specification of a composite service and its observable semantics, either generates a correct client or detect an ambiguous behaviour. This work lead to a realisation of a composite Web services interaction plate-form and an environment of multi-agent systems integration

APA, Harvard, Vancouver, ISO, and other styles

37

Quadri, Dominique. "Résolution du problème du multi-sac-à-dos quadratique en variables entières." Paris 9, 2006. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=2006PA090027.

Full text

Abstract:

L’objet de cette thèse est la résolution d’un problème d’optimisation combinatoire discrète, le problème du multi-sac-à-dos quadratique en variables entières, que nous notons (QMKP). Ce problème est NP-difficile. Nous étudions, dans un premier temps, un cas particulier du problème (QMKP) : le problème du multi-sac-à-dos quadratique en variables entières dont la fonction économique est concave et séparable. Dans ce contexte, nous élaborons une méthode exacte de recherche arborescente par séparation et évaluation pour le résoudre. Cette dernière repose sur le calcul d’un majorant fin de la valeur optimale de (QMKP). Ce majorant provient d’une méthode basée sur une linéarisation et une relaxation agrégée du problème initial. Notre branch-and-bound incorpore également des procédures de pré-traitement en amont. Nous comparons les performances, en terme de temps de calcul et de qualité, de notre approche avec trois autres méthodes existantes : un algorithme de branch-and-bound développé par Djerdjour et al. (1988), une formulation linéarisée en variables 0-1 (initialement utilisée pour résoudre le sac-à-dos quadratique mono-contraint en variables entières que nous avons étendu au cas multi-contraint), un branch-and-bound classique (optimisation quadratique Cplex9. 0). Notre branch-and-bound est clairement le plus performant nous permettant de résoudre des problèmes de grandes tailles (jusqu’à 2000 variables et contraintes) en moins de 5 minutes en moyenne. Dans un deuxième temps, nous étendons nos recherches au cas où la fonction économique du problème (QMKP) est concave et non séparable. Nous proposons alors une voie théorique de résolution de ce problème basée sur une transformation du problème non séparable en un problème séparable. Nous sommes alors en mesure de lui appliquer notre algorithme développé pour résoudre (QMKP) séparable et ainsi de fournir l’optimum entier de ce problème
This thesis deals with the integer quadratic multi-knapsack problem (QMKP). This problem is NP-hard. We first study a special case of (QMKP): the integer quadratic multi-knapsack problem where the objective function is concave and separable. In this context, we develop a branch-and-bound algorithm to solve (QMKP) to optimality. This method is based on the computation of a tight upper bound for (QMKP) which is derived from a linearization and a surrogate relaxation. Our branch-and-bound also incorporates pre-processing procedures. The computational performance of our branch-and-bound is compared to that of three exact methods: a branch-and-bound algorithm developed by Djerdjour et al. (1988), a 0-1 linearization method originally applied to the separable quadratic knapsack problem with a single constraint that we extend to the case of m constraints, a standard branch-and-bound algorithm (Cplex9. 0 quadratic optimization). Our branch-and-bound clearly outperforms other methods for large instances (up to 2000 variables and constraints in 5 minutes). Finally, we suggest a theoretical approach to solve the problem (QMKP) where the objective function is concave and non separable. We transform the non separable problem into a separable in order to be able to apply our branch-and-bound for the separable case in this context

APA, Harvard, Vancouver, ISO, and other styles

38

Boulanger, Célia. "Heuristiques basées sur la programmation mathématique pour des problèmes de localisation et de routage." Valenciennes, 2010. http://ged.univ-valenciennes.fr/nuxeo/site/esupversions/097f03a9-5364-4c57-afd3-697ff1edf975.

Full text

Abstract:

Les travaux de cette thèse portent sur la définition et la résolution de deux problèmes de transport dans le domaine de la recherche opérationnelle. Ces deux problèmes entrent dans le cadre des problèmes de tournées de véhicules et des problèmes de localisation. Le premier problème abordé est le problème de localisation et routage avec contraintes de capacités aux dépôts. Trois méthodes de résolution sont proposées pour résoudre ce problème. Les deux premières sont des heuristiques hybrides, combinant programmes linéaires et une recherche tabou. La troisième méthode est également une méthode approchée, elle est basée sur une approche par génération de colonnes. Ces trois contributions ont ensuite été implémentées afin de tester leur efficacité. Les résultats obtenus sont de bonne qualité, la meilleure méthode implémentée améliorant la majorité des trente instances testées. Le second problème abordé est un problème de voyageur de commerce bi-objectif adapté à un graphe particulier où seuls certains des sommets sont à visiter obligatoirement. Une méthode approchée a été développée pour résoudre ce problème bi-objectif. Afin d’évaluer les qualités des solutions obtenues par cette méthode, une méthode exacte a également été développée
The aim of this PHD is the modelisation of two transportation problems of operationnal research. . These problems are routing problem and location problem. The first one studied is the location-routing problem with capacity constraints on facilities. Three methods are proposed to solve this problem. The two first are hybrid heuristics, mixing linear programs and a tabou search. The third method is based on a column generation method. These three contributions have been developped and tested to see their efficienty. We obtain good results, the best method giving most of the best results of the thirty instances. The second problem studied is a biobjectif travelling salesman problem on a particular graphe where some vertices have to be visited. A heuristic has been developed to solve this biobjective problem. To evaluate results obtained, an exacte method has been developed too

APA, Harvard, Vancouver, ISO, and other styles

39

Marest, Philippe. "Eléments pour l'information de la composante management du système d'information." Paris 9, 1993. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=1993PA090050.

Full text

Abstract:

Avec l'évolution de la conjoncture économique les entreprises doivent dorénavant contrôler efficacement leur fonctionnement et bien connaitre leur environnement. L'information d'une des deux composantes du système d'information d'une organisation la composante management permet ce contrôle et cette connaissance. Mais elle pose encore de nombreux problèmes contrairement à l'information de la composante production, aujourd'hui bien maitrisée grâce à l'emploi de méthodes éprouvées. L'objectif de cette thèse est de proposer des éléments de méthode pour mieux comprendre ces problèmes et tenter de les résoudre. En premier lieu, les caractéristiques de la composante management sont précisées et elle est comparée à d'autres concepts. La capacité de quelques méthodes courantes à informatiser la composante management est ensuite mesurée: l'étude montre qu'elles ne sont pas adaptées. Des éléments de méthodes sont alors recherchés, une démarche spécifique et des outils conceptuels sont proposés pour informatiser la composante management et leur pertinence est vérifiée. Pour conclure, des perspectives sur l'évolution des techniques informatiques sont esquissées et l'impact sur les deux composantes du système d'information est analysé

APA, Harvard, Vancouver, ISO, and other styles

40

Doulcier, Laurent Jean. "Elaboration de classes qualitatives pour l'aide à la décision en conception architecturale de l'éclairage mixte d'un local." Marne-la-vallée, ENPC, 1998. http://www.theses.fr/1998ENPC9808.

Full text

Abstract:

Ce travail est une contribution, avec un certain souci d'application pratique, sur la façon d'intégrer certains aspects techniques dans l'architecture, dans les phases où l'on ne cherche pas la précision, avec adjonction au côté d'éléments techniques, d'éléments d'estime et de critères économiques. Le travail se situe dans la continuité des nouvelles perspectives ouvertes par les récents travaux théoriques de « l'Ecole » de l'Architecturologie Il s'appuie sur l'introduction de la notion de classes dans certaines échelles architecturologiques. L'introduction paradoxale de cette notion de classes dans le continuum du processus de conception permet de mieux l'appréhender en lui associant des instruments qualitatifs et quantitatifs qui jouent le rôle de mesures. Des opérations simples sur les classes permettent ensuite de qualifier des situations ou plusieurs critères interviennent simultanément sans recourir à une mathématique compliquée. On a retenu le sous-problème de l'éclairage comme champ d'approfondissement et réduit le domaine d'application au secteur peu étudié de l'éclairage des locaux du petit commerce. Une approche semi-quantitative et qualitative de la clarté d'un local type en l'éclairage mixte naturel-électrique est conduite à partir d'outils techniques classiques. L’approche s’appuie sur une analyse de sensibilité systématique aux différents paramètres fondée sur le respect d’une norme de niveau d’éclairement sur un plan utile et sur la consommation énergétique annuelle minimale d’éclairage électrique pour respecter la norme d’éclairement pendant les horaires d’exploitation du local. Cette analyse systématique de sensibilité à l’ensemble des paramètres (surface au sol du local, forme du local, position et surface des percements, qualité de transparences des vitrages, orientation par rapport aux points cardinaux, hauteur et clarté des prospects, clarté de matériaux intérieurs, coûts d’investissement et de fonctionnement) permet de définir les premiers éléments techniques d’éclairage mixte naturel-électrique pour une esquisse, avec notamment la validation d’un nouveau concept opérationnel : le Facteur de Réflexion Uniforme Equivalent au Trio plafond-murs-sol (FRUET). Le FRUET réduit la combinatoire de trois paramètres continus, les facteurs de réflexions diffuses des parois, à un seul qui peut être calculé de manière simple en rationalisant la définition des classes de clarté intérieure. Les classes et les éléments qualitatifs et semi-quantitatifs que cette approche permet de manipuler sont utilisables par un concepteur non spécialiste de l'éclairagisme et compréhensibles par un client maitre d'ouvrage. Des représentations graphiques synthétiques permettent de qualifier rapidement des variantes de conception d'une situation concrète et de guider les choix dans un dialogue simple entre le concepteur et son client
This study is a contribution to the way of integrating some technical sight into architecture. The practical experience is taken into account. This concerns the steps where precision is not a big issue. It joins by the side of technical items, regard-value items and economical criterion. This work takes place in the continuity of new outlooks opened by the very new theorical studies of the Architecturology « school ». It is based on rank idea in some typical architecturology scales. This rank idea paradox in the design process continuum, leads to understand it better, by the mean of links between it and qualitatives and numeric tools which operates as a measuring tools. Some simple operations upon ranks allows afterwards to qualify situations where several criterions take place simultaneously without requiring a sophisticated mathematic. The sub-problem of the lighting was hold to be studied thoroughly. It reduces this field to the slightly studied area of the lighting of small trading shops. A semi quantitative and qualitative analysis of a standard shop brightness in natural and electric compound lighting is led from the conventional technical tools. We analyse systematically the sensitiveness to all its different parameters. We use a rule of brightness levels on the key planes and on the minimal annual energy consummation of electric lighting, with all due respect to the normalised lighting during the business hours. The following sensitiveness parameters set is systematically analised : shop area, shop shape, openings surface and location, transparency quality of the glasses, orientation according to cardinal points, hight and brightness of facing buildings, brightness of interior materials, investments and using costs. These parameters lead to define the first tehnical items of natural and electric compound lighting for an outline of the project, which tipicaly validate a new oprational concept : the Uniform Reflection Factor Equivalent to the Trio ceiling-wall-floor (URFET, FRUET in french language). This factor reduces the combination set of three continuous parameters, the factors of diffuse reflection of the faces, to a single one which can be easily computed because the definition of the ranks of interior brightness is relevant. The ranks and qualitative and semi numeric iems handled by our approach, can be used by a designer who is non expert in lighting field, and is understandable by a governor-customer. Syntetic graphics allow to quickly qualify variants of design of a concrete case, and to lead the choices in simple dialogue between the designer and his customer

APA, Harvard, Vancouver, ISO, and other styles

41

Ribault, Alnour. "Optimisation de la consommation d’énergie d’un entrepôt frigorifique : double approche par la recherche opérationnelle et l’apprentissage automatique." Thesis, Lyon, 2020. http://www.theses.fr/2020LYSE2008.

Full text

Abstract:

Les entrepôts frigorifiques en Europe consomment une quantité importante d’énergie afin de maintenir leurs chambres froides à basse température. La méthode de gestion de la production de froid utilisée dans la plupart des entrepôts frigorifiques ne prend pas en compte les variations de prix de l’électricité causées par les besoins fluctuants du réseau électrique, malgré la possibilitéd’utiliser l’inertie thermique des chambres froides ainsi que la cuve de réfrigérant comme des stocks d’énergie. De plus, les compresseurs frigorifiques sont utilisés à des niveaux de production au rendement sous-optimal. Ces pratiques entraînent des surplus de coût et de quantité d’énergie consommée.Dans ces travaux de recherche, deux approches sont proposées pour améliorer le pilotage des entrepôts frigorifiques. La première est basée sur une modélisation mathématique des entrepôts, puis par l’application d’algorithmes d’optimisation afin de générer des planifications de production dont le coût est minimisé. La seconde, basée sur des techniques d’apprentissage automatique,vise à déterminer les meilleures décisions de production en fonction du contexte de production via la prédiction du cout futur engendré par chaque décision de production possible. Ces deux approches sont comparées à la méthode usuelle de pilotage des entrepôts frigorifiques
Cold storage in Europe consume important amounts of energy to maintain cold rooms at low temperatures. The cold production control method most commonly used in cold stores does not account for variations in the price of electricity caused by the fluctuating needs of the electrical network. The thermal inertia of the cold rooms as well as the coolant tank could be used as energy storage. Moreover, the compressors are often used at suboptimal production levels. Those practices lead to extra energy consumption costs.In the present research work, two approaches are proposed to improve the control of cold stores. The first approach is based on the mathematical modelling of the cold stores, and by the application of optimisation algorithms to those models in order to generate energy consumption schedules with minimal cost. The second approach, based on machine learning techniques, aims at establishing the best production decision in a given context by predicting the future cost generated by each possible production decision. These two approaches are compared to the most common control method for cold stores

APA, Harvard, Vancouver, ISO, and other styles

42

Abdou, Joseph. "Fonctions d'effectivité et jeux coopératifs." Paris 1, 1988. http://www.theses.fr/1988PA010017.

Full text

Abstract:

La fonction d'effectivité est une notion introduite par les travaux de Moulin-Peleg (1982) et consiste dans la représentation du pouvoir des coalitions en termes d'efficacité sur un ensemble d'alternatives. La thèse propose des extensions de résultats obtenus dans le cadre de la théorie des fonctions d'effectivité, ainsi que diverses études sur la structure de ces fonctions. Dans la première partie, on généralise le modèle au cas où les alternatives forment un continuum muni d'une mesure. On établit des conditions nécessaires et suffisantes de stabilité, en particulier on prouve qu'une fonction veto maximale est stable si et seulement si elle est additive. Dans un deuxième temps, l'ensemble d'alternatives est conçu plus généralement comme un espace topologique compact, ce qui permettra le cas échéant de représenter des situations économiques de production ou d'échange. On démontre qu'une fonction d'effectivité est stable si et seulement si elle est acyclique. Une notion de maximalité y est introduite et les fonctions d'effectivité maximales et stables sont caractéristiques. Dans une troisième partie, l'ensemble des joueurs lui-même est infini. La dernière partie réunit deux articles: le premier comporte une caractérisation des fonctions veto (quasi) convexes au moyen des algorithmes d'élimination successive. Le second article introduit à la théorie d'effectivité issue de mécanismes où les stratégies corrélées peuvent être utilisées par les coalitions. Cette étude utilise les techniques des jeux répétés

APA, Harvard, Vancouver, ISO, and other styles

43

Ramu, Jean-Philippe. "Efficience d'une documentation opérationnelle contextuelle sur la performance des pilotes de transport aérien." Toulouse, ISAE, 2008. http://www.theses.fr/2008ESAE0020.

Full text

Abstract:

La documentation a rencontré des changements radicaux au cours de cette dernière décennie. Un pas important a été franchi avec l'avènement de la documentation en format électronique. La documentation opérationnelle aéronautique est elle aussi de plus en plus disponible en format électronique, et offre de nouvelles opportunités d'utilité et des défis d'utilisabilité. Nous nous attachons à étudier comment cette documentation peut être développée pour répondre à cette évolution. Grâce à une modélisation cognitive de la tâche de recherche d'information, nous catégorisons puis discutons les activités documentaires des pilotes telles que : support de performance, aide à la préparation ou entraînement. Dans ces différentes activités, l’interactivité entre le pilote et la documentation présuppose une notion de pertinence de l'information choisie. Nous utilisons la notion de contexte comme référentiel de pertinence. Notre modélisation du contexte est composée de trois catégories de descripteurs sémantiques, qui sont : les tâches, les conditions et les ressources. L'articulation de ces trois catégories de contexte définit l'ensemble des situations décrites dans la documentation aéronautique. La thèse met en application les propositions de notre modélisation en utilisant une approche centrée utilisateur. D'abord, un questionnaire sur l'utilisation de la documentation illustre les besoins des pilotes. Ensuite, deux cycles de conceptions/évaluations d'un prototype de documentation contextuelle permettent de spécifier une méthode de contextualisation de la documentation, ainsi que de proposer des interactions susceptibles de supporter les catégories d'activités documentaires des pilotes.

APA, Harvard, Vancouver, ISO, and other styles

44

Zaytoon, Janan. "Extension de l'analyse fonctionnelle à l’étude de la sécurité opérationnelle des systèmes automatises de production." Lyon, INSA, 1993. http://www.theses.fr/1993ISAL0016.

Full text

Abstract:

L'un des objectifs de l'évaluation du niveau de Sécurité Opérationnelle d'une installation consiste à déterminer les situations critiques de production. Dans ce cadre, la démarche proposée consiste à intégrer les contraintes de Sécurité, dès la phase de spécification, en terme de service sur un modèle issu de l'analyse fonctionnelle. Le premier chapitre introduit les différentes méthodes d'analyse et de conception des systèmes automatisés de production ainsi que les techniques de Sûreté de Fonctionnement. Une étude préalable nous a amené à retenir les méthodes couramment utilisées dans le domaine de la productique, à savoir SADT et les AMDE. Le concept de la Sécurité Opérationnelle et les problèmes d'intégration de la Sûreté de Fonctionnement dans l'analyse-conception des systèmes de production font l'objet du deuxième chapitre. C'est ainsi que nous présentons la démarche d'intégration de la Sécurité Opérationnelle retenue dans le cadre du projet CASCIS. L'approche d'assistance à la spécification, présentée au troisième chapitre, s'appuie d'une part sur la définition des activités génériques et d'autre part sur la proposition d'une démarche de validation de la cohérence des spécifications vis-à-vis du cahier des charges. Des classes-type d'activités et de flux de production permettent de générer des AMDE fonctionnelles. Le quatrième chapitre fait état des travaux menés pour compléter l' approche strictement fonctionnelle de SADT par la spécification et la génération d'un SADT temporel qui garde les acquis du modèle de base. Un simulateur d'événements discrets, écrit en langage orienté objet, permet de simuler le comportement du SADT temporel
One of the objectives of the evaluation of the Operational Safety level for an Automated Manufacturing System consists of the determination of critical production situations. Therefore our research work aims at integrating the safety constraints into the service provided by a functional model. The first chapter introduces the different methods of specification and design of Automated Manufacturing Systems as well as the dependability techniques. This survey justified the use of the methods : SADT and FMEA. The second chapter presents the operational Safety concept and the problems of dependability integration in system specification and design. The structured approach of Operational Safety integration that was used in the project CASCIS is then presented. The specification assistance approach presented in chapter 3 is based upon the use of generic activities on the one hand and upon the validation of the specification consistency with respect to requirement definition on the other hand. Typical classes of production activities and flows are established in order to generate the associated functional FMEA. The fourth chapter presents the work carried out to complete the functional approach of SADT by the specification and the generation of a temporal SADT model which maintains the advantages of the original model. A discrete event simulator, based on an object oriented language, was designed in order to directly simulate the behaviour of the SADT model

APA, Harvard, Vancouver, ISO, and other styles

45

Tangpattanakul, Panwadee. "Optimisation multi-objectif de missions de satellites d'observation de la Terre." Phd thesis, INSA de Toulouse, 2013. http://tel.archives-ouvertes.fr/tel-00903756.

Full text

Abstract:

Cette thèse considère le problème de sélection et d'ordonnancement des prises de vue d'un satellite agile d'observation de la Terre. La mission d'un satellite d'observation est d'obtenir des photographies de la surface de la Terre afin de satisfaire des requêtes d'utilisateurs. Les demandes, émanant de différents utilisateurs, doivent faire l'objet d'un traitement avant transmission d'un ordre vers le satellite, correspondant à une séquence d'acquisitions sélectionnées. Cette séquence doit optimiser deux objectifs sous contraintes d'exploitation. Le premier objectif est de maximiser le profit global des acquisitions sélectionnées. Le second est d'assurer l'équité du partage des ressources en minimisant la différence maximale de profit entre les utilisateurs. Deux métaheuristiques, composées d'un algorithme génétique à clé aléatoire biaisées (biased random key genetic algorithm - BRKGA) et d'une recherche locale multi-objectif basée sur des indicateurs (indicator based multi-objective local search - IBMOLS), sont proposées pour résoudre le problème. Pour BRKGA, trois méthodes de sélection, empruntées à NSGA-II, SMS-EMOA, et IBEA, sont proposées pour choisir un ensemble de chromosomes préférés comme ensemble élite. Trois stratégies de décodage, parmi lesquelles deux sont des décodages uniques et la dernière un décodage hybride, sont appliquées pour décoder les chromosomes afin d'obtenir des solutions. Pour IBMOLS, plusieurs méthodes pour générer la population initiale sont testées et une structure de voisinage est également proposée. Des expériences sont menées sur des cas réalistes, issus d'instances modifiées du challenge ROADEF 2003. On obtient ainsi les fronts de Pareto approximés de BRKGA et IBMOLS dont on calcule les hypervolumes. Les résultats de ces deux algorithmes sont comparés.

APA, Harvard, Vancouver, ISO, and other styles

46

Casorran, Amilburu Carlos. "Formulations and Algorithms for General and Security Stackelberg Games." Doctoral thesis, Universite Libre de Bruxelles, 2017. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/259557.

Full text

Abstract:

General Stackelberg games (GSG) confront two contenders, each wanting to optimize their rewards. One of the players, referred to as the leader, can commit to a given action or strategy first, and the other player, referred to as the follower, then responds by selecting an action or strategy of his own. The objective of the game is for the leader to commit to a reward-maximizing strategy, anticipating that the follower will best respond.Finding an optimal mixed strategy for the leader in a GSG is NP-hard when the leader faces one out of a group of several followers and polynomial when there exists a single follower. Additionally, GSGs in which the strategies of the leader consist in covering a subset of at most $m$ targets and the strategies of the followers consist in attacking some target, are called Stackelberg security games (SSG) and involve an exponential number of pure strategies for the leader.The goal of this thesis is to provide efficient algorithms to solve GSGs and SSGs. These algorithms must not only be able to produce optimal solutions quickly, but also be able to solve real life, and thus large scale, problems efficiently. To that end, the main contributions of this thesis are divided into three parts:First, a comparative study of existing mixed integer linear programming (MILP) formulations is carried out for GSGs, where the formulations are ranked according to the tightness of their linear programming (LP) relaxations. A formal theoretical link is established between GSG and SSG formulations through projections of variables and this link is exploited to extend the comparative study to SSG formulations. A new strong SSG MILP formulation is developed whose LP relaxation is shown to be the tightest among SSG formulations. When restricted to a single attacker type, the new SSG formulation is ideal, i.e. the constraints of its LP relaxation coincide with its convex hull of feasible solutions. Computational experiments show that the tightest formulations in each setting are the fastest. Notably, the new SSG formulation proposed is competitive with respect to solution time, and due to the tightness of its LP relaxation, it is better suited to tackle large instances than competing formulations.Second, the bottleneck encountered when solving the formulations studied in the first part of the thesis is addressed: The tightest formulations in each setting have heavy LP relaxations which can be time-consuming to solve and thus limit the effectiveness of the formulations to tackle instances. To address this issue, in both the general and the security case, Benders cuts from the LP relaxation of the tightest MILP formulations are embedded into a Cut and Branch scheme on a sparse equivalent formulation in each setting. By combining the tightness of the bound provided by the strong formulations with the resolution speed of the formulations, the proposed algorithm efficiently solves large GSG and SSG instances which were out of the scope of previous methods.Third, a special type of SSG, defined on a network, is studied, where the leader has to commit to two coverage distributions, one over the edges of the network and one over the targets, which are contained inside the nodes. A particular case of this SSG is used to tackle a real life border patrol problem proposed by the Carabineros de Chile in which the use of their limited security resources is optimized while taking into account both global and local planning considerations. A methodology is provided to adequately generate the game's parameters. Computational experiments show the good performance of the approach and a software application developed for Carabineros to schedule their border resources is described.
Doctorat en Sciences
info:eu-repo/semantics/nonPublished

APA, Harvard, Vancouver, ISO, and other styles

47

Benoist, Thierry. "Relaxations et décompositions combinatoires." Avignon, 2004. http://www.theses.fr/2004AVIG0135.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Malod-Dognin, Noël. "Protein structure comparison : from contact map overlap maximisation to distance-based alignment search tool." Rennes 1, 2010. http://www.theses.fr/2010REN1S015.

Full text

Abstract:

In molecular biology, a fruitful assumption is that proteins sharing close three dimensional structures may share a common function and in most cases derive from a same ancestor. Computing the similarity between two protein structures is therefore a crucial task and has been extensively investigated. Among all the proposed methods, we focus on the similarity measure called Contact Map Overlap maximisation (CMO), mainly because it provides scores which can be used for obtaining good automatic classifications of the protein structures. In this thesis, comparing two protein structures is modelled as finding specific sub-graphs in specific k-partite graphs called alignment graphs. Then, we model CMO as a kind of maximum edge induced sub-graph problem in alignment graphs, for which we conceive an exact solver which outperforms the other CMO algorithms from the literature. Even though we succeeded to accelerate CMO, the procedure still stays too much time consuming for large database comparisons. To further accelerate CMO, we propose a hierarchical approach for CMO which is based on the secondary structure of the proteins. Finally, although CMO is a very good scoring scheme, the alignments it provides frequently posses big root mean square deviation values. To overcome this weakness, we propose a new comparison method based on internal distances which we call DAST (for Distance-based Alignment Search Tool). It is modelled as a maximum clique problem in alignment graphs, for which we design a dedicated solver with very good performances
Une hypothèse féconde de la biologie structurale est que les protéines partageant des structures tri-dimensionnelles similaires sont susceptibles de partager des fonctions similaires et de provenir d'un ancêtre commun. Déterminer la similarité entre deux structures protéiques est une tâche importante qui à été largement étudiée. Parmi toutes les méthodes proposées, nous nous intéressons à la mesure de similarité appelée Maximisation du Recouvrement de Cartes de Contacts (CMO). Dans cette thèse, nous proposons un cadre général pour modéliser la comparaison de deux structures protéiques dans des graphes k-partis spécifiques appelés graphes d'alignements. Puis, nous modélisons CMO comme une recherche de sous-graphe maximum induit par les arêtes dans des graphes d'alignements, problème pour lequel nous proposons un solveur exact qui surpasse les autres algorithmes de la littérature. Cependant, la procédure d'alignement requière encore trop de temps de calculs pour envisager des comparaisons à grande échelle. Afin d'accélérer davantage CMO, nous proposons une approche hiérarchique basée sur les structures secondaires. Enfin, bien que CMO soit une très bonne mesure de similarité, les alignements qu'elle fournit possèdent souvent de fortes valeurs de déviation (RMSD). Pour palier à cette faiblesse, nous proposons une nouvelle méthode de comparaison basée sur les distances internes que nous appelons DAST. Elle est modélisée comme une recherche de clique maximum dans des graphes d'alignements, pour laquelle nous présentons un solveur dédié montrant de très bonnes performances

APA, Harvard, Vancouver, ISO, and other styles

49

Zolghadri, Mahmoud. "Contribution à la modélisation agrégée des systèmes de production discrète." Bordeaux 1, 1998. http://www.theses.fr/1998BOR10532.

Full text

Abstract:

La these propose un cadre methodologique et des outils de modelisation agregee des systemes complexes de production, en vue de leur pilotage a differents niveaux de gestion. On s'interesse d'une part aux mecanismes generiques et aux proprietes recursives des agregateurs, d'autre part et plus specifiquement a l'elaboration de tableaux de bord agreges d'exploitation a partir des caracteristiques du systeme operationnel. Une formalisation complete de l'agregation iterative d'activites de s. E. D. Est menee dans (max, +). Enfin, on met en evidence les modalites d'utilisation, par les differents decideurs, des outils presentes dans une perspective d'ordonnancement multiniveaux.

APA, Harvard, Vancouver, ISO, and other styles

50

Soukhal, Ameur. "Ordonnancement simultané des moyens de transformation et de transport." Tours, 2001. http://www.theses.fr/2001TOUR4010.

Full text

Abstract:

On s'intéresse à la résolution des problèmes d'ordonnancement dans les Systèmes Flexibles de Production (SFP). L'établissement d'une typologie, de notations claires et non ambigue͏̈s des problèmes réellement présents dans les ateliers de production est nécessaire pour résoudre efficacement les problèmes. Dans la première partie de cette thèse, nous utilisons une technique pour identifier automatiquement et précisément les problèmes d'ordonnancement, avec un minimum d'hypothèses simplificatrices. Dans la deuxième partie, nous nous préoccupons de la résolution des problèmes identifiés. Certains sont connus pour être NP-difficiles, et pour les autres de nouveaux résultats de complexité sont proposés. Compte tenu de la taille des problèmes à résoudre, nous nous sommes intéressés aux méthodes de résolution approchées de type métaheuristiques. Les méthodes ont été implémentées et testées pour quelques ateliers. Finalement, l'ordonnancement obtenu est traduit directement en consignes de pilotage du système de production. Plusieurs exemples servent d'illustration tout au long de la thèse, en particulier : le flowshop robotisé, le flowshop hybride classique et le flowshop hybride avec recirculation et temps de préparation. L'ensemble de ce travail contribue au développement du logiciel OCEA (Outil de Comparaison et d'Elaboration d'Algorithmes) à différents niveaux : - dans le DeSAP (Description de la Structure d'un Atelier de Production), le problème d'ordonnancement présent dans l'atelier est identifié précisément de façon automatique, à partir de sa description iconique ; - la bibliothèque électronique des références bibliographiques LEBO est enrichie ; - nous apportons à la bibliothèque d'algorithmes de résolution LCA (Logiciel de Comparaison d'Algorithmes) nos propres algorithmes basés principalement sur des méthodes comme le Recuit Simulé, la Recherche Tabou, les Algorithmes Evolutionnaires ou encore les Algorithmes de Fourmis Artificielles.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Recherche opérationnelle'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles