O problema de agrupamento de dados em grafos consiste em encontrar clusters de nós em um dado grafo, ou seja, encontrar subgrafos com alta conectividade. Esse problema pode receber outras nomenclaturas, algumas delas são: problema de particionamento de grafos e problema de detecção de comunidades. Para modelar esse problema, existem diversas formulações matemáticas, cada qual com suas vantagens e desvantagens. A maioria dessas formulações tem como desvantagem a necessidade da definição prévia do número de grupos que se deseja obter. Entretanto, esse tipo de informação não está contida em dados para agrupamento, ou seja, em dados não rotulados. Esse foi um dos motivos da popularização nas últimas décadas da medida conhecida como modularidade, que tem sido maximizada para encontrar partições em grafos. Essa formulação, além de não exigir a definição prévia do número de clusters, se destaca pela qualidade das partições que ela fornece. Nesta Tese, metaheurísticas Greedy Randomized Search Procedures para dois modelos existentes para agrupamento em grafos foram propostas: uma para o problema de maximização da modularidade e a outra para o problema de maximização da similaridade intra-cluster. Os resultados obtidos por essas metaheurísticas foram melhores quando comparadas àqueles de outras heurísticas encontradas na literatura. Entretanto, o custo computacional foi alto, principalmente o da metaheurística para o modelo de maximização da modularidade. Com o passar dos anos, estudos revelaram que a formulação que maximiza a modularidade das partições possui algumas limitações. A fim de promover uma alternativa à altura do modelo de maximização da modularidade, esta Tese propõe novas formulações matemáticas de agrupamento em grafos com e sem pesos que visam encontrar partições cujos clusters apresentem alta conectividade. Além disso, as formulações propostas são capazes de prover partições sem a necessidade de definição prévia do número de clusters. Testes com centenas de grafos com pesos comprovaram a eficiência dos modelos propostos. Comparando as partições provenientes de todos os modelos estudados nesta Tese, foram observados melhores resultados em uma das novas formulações propostas, que encontrou partições bastante satisfatórias, superiores às outras existentes, até mesmo para a de maximização de modularidade. Os resultados apresentaram alta correlação com a classificação real dos dados simulados e reais, sendo esses últimos, em sua maioria, de origem biológica / Graph clustering aims at identifying highly connected groups or clusters of nodes of a graph. This problem can assume others nomenclatures, such as: graph partitioning problem and community detection problem. There are many mathematical formulations to model this problem, each one with advantages and disadvantages. Most of these formulations have the disadvantage of requiring the definition of the number of clusters in the final partition. Nevertheless, this type of information is not found in graphs for clustering, i.e., whose data are unlabeled. This is one of the reasons for the popularization in the last decades of the measure known as modularity, which is being maximized to find graph partitions. This formulation does not require the definition of the number of clusters of the partitions to be produced, and produces high quality partitions. In this Thesis, Greedy Randomized Search Procedures metaheuristics for two existing graph clustering mathematical formulations are proposed: one for the maximization of the partition modularity and the other for the maximization of the intra-cluster similarity. The results obtained by these proposed metaheuristics outperformed the results from other heuristics found in the literature. However, their computational cost was high, mainly for the metaheuristic for the maximization of modularity model. Along the years, researches revealed that the formulation that maximizes the modularity of the partitions has some limitations. In order to promote a good alternative for the maximization of the partition modularity model, this Thesis proposed new mathematical formulations for graph clustering for weighted and unweighted graphs, aiming at finding partitions with high connectivity clusters. Furthermore, the proposed formulations are able to provide partitions without a previous definition of the true number of clusters. Computational tests with hundreds of weighted graphs confirmed the efficiency of the proposed models. Comparing the partitions from all studied formulations in this Thesis, it was possible to observe that the proposed formulations presented better results, even better than the maximization of partition modularity. These results are characterized by satisfactory partitions with high correlation with the true classification for the simulated and real data (mostly biological)

Les molécules d’adhésion jonctionnelles JAM-B et JAM-C forment une paire récepteur/ligand impliquée dans la régulation de nombreux mécanismes biologiques dont l’inflammation, l’hématopoïèse et la spermatogénèse. Dans la moelle osseuse, l’interaction entre JAM-C et JAM-B, respectivement exprimée par les cellules souches hématopoïétiques (CSH) et les cellules stromales, joue un rôle dans la rétention et la quiescence des CSH. Dans le testicule, JAM-C participe à la polarisation des spermatides en différenciation en interagissant avec JAM-B exprimée par les cellules de Sertoli. GRASP55 (Golgi ReAssembly and Stacking Protein of 55 kDa), identifiée au laboratoire comme un interacteur intracellulaire des protéines JAMs, est une protéine de l’appareil de Golgi participant à l’architecture et la dynamique de celui-ci ainsi qu’au transport protéique non-conventionnel.Le but de mon travail de thèse a été d’étudier le rôle de GRASP55 in vivo par des approches génétiques et pharmacologiques. Nous avons ainsi pu mettre en évidence que l’expression de GRASP55 par la spermatide ronde permet la localisation polarisée de JAM-C et le déroulement correct de la spermatogénèse. A contrario, GRASP55 n’est pas essentiel à l’hématopoïèse en conditions basales ou de stress. Toutefois, la délétion de GRASP-55 dans les cellules leucémiques diminue le progression de la pathologie in vivo. Ces résultats montrent un rôle non redondant de GRASP55 dans la spermatogenèse et la prolifération de cellules leucémiques et ouvrent des pistes possibles pour un ciblage thérapeutique de GRASP55 en hématologie. / The junctional adhesion molecules JAM-B and JAM-C form a receptor / ligand pair involved in regulation of many biological mechanisms including inflammation, hematopoiesis and spermatogenesis. In the bone marrow, the interaction between JAM-C and JAM-B, expressed by hematopoietic stem cells (HSC) and stromal cells respectively, is involved in HSC retention and quiescence. Similarly, in the testis, JAM-C participates in the polarization of differentiated spermatids by interacting with JAM-B expressed by Sertoli cells. GRASP55 (Golgi ReAssembly and Stacking Protein of 55 kDa), identified in our laboratory as a new intracellular interactor of JAM, is a Golgi apparatus protein involved in Golgi architecture and dynamics as well as unconventional secretion.The aim of my thesis was to study the role of GRASP55 in vivo by genetic and pharmacological approaches. We demonstrate that GRASP55 expression by round spermatid allows polarized localization of JAM-C and the correct course of the spermatogenesis. In contrast, GRASP55 is not essential for hematopoiesis in basal or stress conditions. However, deletion of GRASP-55 in leukemic cells decreases the progression of the pathology in vivo. These results show a non-redundant role of GRASP55 in the spermatogenesis and proliferation of leukemic cells and allow us to consider GRASP55 as a potential target in hematology.

Mit der Interaktionstechnik der "direkten Objektmanipulation" für virtuelle Umgebungen wird angestrebt, virtuelle Objekte genauso realistisch und flexibel handhaben zu können, wie das bei realen Objekten der Fall ist. Das bedeutet, virtuelle Objekte können mittels eines Handmodells direkt berührt, ergriffen, getragen, gedrückt und gezogen werden. Diese Interaktionstechnik findet vor allem dort Anwendung, wo Objektmanipulationen möglichst realistisch simuliert und erfasst werden sollen, z.B. bei Ergonomieuntersuchungen, virtuellem Prototyping, Trainingssimulationen usw. Neben einigen Ansätzen zur technischen Umsetzung von direkten Objektmanipulationen werden in dieser Arbeit vor allem Konzepte und Verfahren entwickelt und vorgestellt, die eine Erfassung und Analyse von Benutzerinteraktionen unter Verwendung dieser Interaktionstechnik ermöglichen. Eine wichtige Rolle spielt dabei die Untersuchung von Greifvorgängen, insbesondere die automatische Erkennung von Greifarten. Dazu wurden mehrere ausführliche empirische Studien mit einer neuartigen systematischen Methodik durchgeführt, woraus sich Empfehlungen für die Wahl von Klassifikationsverfahren und die Zusammensetzung der Merkmale ergeben. Ein weiteres Ergebnis ist eine neue Taxonomie von Greifarten, die speziell auf den Einsatz in virtueller Realität zugeschnitten ist und sich durch die Integration nicht-prehensiler Greifarten auszeichnet. Als weiterer wesentlicher Beitrag wird ein Analyseverfahren vorgestellt, mit dem der kontinuierliche Strom von Bewegungs- und Interaktionsdaten in Sequenzen von diskreten sinntragenden Basisinteraktionen zerlegt werden kann. Diese Sequenzen können anschließend manuell ausgewertet oder im Rahmen des "Action Capture"-Verfahrens in eine abstrakte Aktionsrepräsentation überführt und durch unterschiedliche virtuelle Figuren wiedergegeben werden.

The Golgi complex is an organelle responsible for receiving synthesized cargo from the endoplasmic reticulum for subsequent post-translations modifications, sorting and secretion. A family of proteins named Golgi Reassembly and Stacking Proteins (GRASP) is essential for the correct assembly and laterally tethering of the Golgi cisternae, a necessary structuration to keep this organelle working correctly. The GRASP structure is mainly composed of two regions: an N-terminal formed by two PDZ domains connected by a short loop (GRASP domain) and a non-conserved C-terminal region, rich in serine and proline residues. Although there are now a few crystal structures solved for the N-terminal domain, it is surprising to notice that no information is currently available regarding a full-length protein or even about dynamic and structural differences between the two PDZs in solution, which is the main functional region of this protein. Using a full-length GRASP model, we were capable of detecting the coexistence of regular secondary structures and large amounts of disordered regions. The overall structure is less compact than a regular globular protein and the high structural flexibility makes its hydrophobic core more accessible to solvent. GRASP coexist in a dynamic conformational ensemble of a µs-ms timescale. Our results indicate an unusual behavior of GRASP in solution, closely resembling a class of collapsed intrinsically disordered proteins called molten globule. We report here also the disorder-to-order transition propensities for a native molten globule-like protein in the presence of different mimetics of cell conditions. Changes in the dielectric constant (such as those experienced close to the membrane surface) seem to be the major factor capable of inducing several disorder-to-order transitions in GRASP, which seems to show very distinct behavior when in conditions that mimic the vicinity of the membrane surface as compared to those found when free in solution. Other folding factors such as molecular crowding, counter ions, pH and phosphorylation exhibit lower or no effect on GRASP secondary structure and/or stability. This is the first study focusing on understanding the disorder-to-order transitions of a molten globule structure without the need for any mild denaturing condition. Regarding the PDZs that form the GRASP domain, we observed that GRASPs are formed by a more unstable and flexible PDZ1 and much more stable and structurally well-behaved PDZ2. More than that, many of the unstable regions found in PDZ1 are in the predicted binding pocket, suggesting a structural promiscuity inside this domain that correlates with the functional promiscuity of interacting with multiple protein partners. This thesis presents the first structural characterization of a full-length GRASP, the first model of how GRASPs (or any molten globule-like protein) can be modulated by the cell during different cell functionalities and the first work in the community proving that the established idea that both PDZs are structurally equivalent is not completely right / O complexo de Golgi é um organela responsável pela recepção de carga sintetizada no retículo endoplasmático e por subsequente modificações pós-traducionais, classificação e secreção. Uma família de proteínas chamada Golgi Reassembly and Stacking Proteins (GRASP) é essencial para o correto empilhamento das cisternas e conexões laterais das pilhas do complexo de Golgi, uma estruturação necessária para manter essa organela funcionando corretamente. A estrutura das GRASPs é composta de duas regiões principais: uma extensão N-terminal formado por dois domínios PDZ conectados por um loop (domínio GRASP) e uma região C-terminal não conservada, rica em resíduos de serina e prolina. Embora existam algumas estruturas cristalográficas resolvidas para o domínio N-terminal, é surpreendente notar que não havia nenhuma informação na literatura sobre a construção inteira de um GRASP, ou mesmo um estudo detalhado sobre os PDZs no N-terminal em solução, que é a principal região funcional dessa proteína. Usando um modelo de GRASP em sua construção completa, fomos capazes de detectar a coexistência de estruturas secundárias regulares e grandes quantidades de regiões desordenadas. A estrutura é menos compacta do que uma proteína globular e a alta flexibilidade estrutural torna o seu núcleo hidrofóbico mais acessível ao solvente. GRASPs coexistem em um conjunto conformacional dinâmico numa escala de tempo característico de s-ms. Nossos resultados indicam um comportamento incomum da GRASP em solução, similar à de uma classe de proteínas intrinsicamente desordenadas colapsadas conhecidas como glóbulos fundidos. Nós relatamos também as propensões de transição estrutural do tipo desordem-ordem para uma proteína glóbulo fundido nativa, induzidas pela presença de diferentes miméticos de condições celulares especificas. A mudança na constante dielétrica do meio (como as experimentadas próximas à superfície da membrana biológica) é o principal modulador estrutural, capaz de induzir múltiplas transições desordem-ordem na GRASP, sugerindo um comportamento muito distinto quando em condições que imitam a vizinhança da superfície da membrana em comparação com os encontrados quando livre em solução. Outros fatores de enovelamento, tais como o molecular crowding, contra-ions, pH e a fosforilação exibem efeitos menores (ou nenhum) na estrutura secundária e/ou estabilidade da GRASP. Este é o primeiro estudo focado na compreensão das transições desordem-ordem em uma estrutura do tipo glóbulo fundido sem que houvesse a necessidade de qualquer condição desnaturante. Em relação aos PDZs que formam o domínio GRASP, observamos que as GRASPs são formadas por um PDZ1 mais instável e flexível e um PDZ2 muito mais estável e estruturalmente bem comportado. Mais do que isso, muitas das regiões instáveis encontradas no PDZ1 estão no predito bolsão de ligação, sugerindo uma promiscuidade estrutural dentro desse domínio que se correlaciona com a promiscuidade funcional de interação com múltiplos parceiros proteicos. É apresentado nesta tese a primeira caracterização estrutural de uma GRASP em sua forma completa, o primeiro modelo de como as GRASPs (ou qualquer proteína em forma de glóbulo fundido) pode ser modulada estruturalmente pela célula durante diferentes funcionalidades e o primeiro trabalho na comunidade provando que a estabelecido ideia de que ambos os PDZs são estruturalmente equivalentes não é completamente correta

[pt] Seja G= (V, E) um grafo não-orientado com custos não- negativos em suas arestas e D um conjunto de pares origem - destino. Um 2-caminho entre nós (s,t)é um caminho de s a t formado por , no máximo, 2 arestas. O problema de síntese de redes com 2-caminhos (2PNDP) consiste em encontrar um subconjunto de arestas com custo mínimo que contenha um 2- caminho entre as extremidades dea cada para origem- destino pertencente a D. Apicações deste problema encontram-se no projeto de redes de comunicação, onde caminhos com poucas arestas são desejáveis para garantir alta confiabilidade e pequenos atrasos. A metaheurística GRASP é um processo multipartida para resolver problemas combinatórios, cujas iterações consistem de duas fases, uma fase de construção e outra de busca local. O algoritmo retorna a melhor solução encontrada depois de um número determinado de iterações.Aplica-se a técnica de reconexão por caminhos ao final de cada iteração GRASP para melhorar a qualidade das soluções. Implementações paralelas de metaheurística são muito robustas. A maior parte das implementações paralelas da metaheurística GRASP segue uma estratégia do tipo independente , baseada na distribuição balanceada das iterações pelos processadores. No caso de estratégias colaboradtivas, os processadores trocam e compartilham informações coletadas ao longo da trajetória que cada um deles investiga. Neta tese são desenvolvidas heurísticas seqüenciais e paralelas para 2PNDP. São analisadas variantes e combinações de GRASP e reconexão por caminhos , comparando-se os resultados obtidos pelos algoritmos descritos na literatura. Heurísticas GRASP paralelas com reconexão por caminhos são avaliadas e comparadas para verificar qual o papel que a colaboração entre os processadores desempenha na qualidade das soluções e nos tempos de processamento. Procura-se também estudar a melhor maneira de desenvolver implementações paralelas , para se utilizar da melhor forma possível os recursos computacionais e reduzir conflitos de memória e comunicação. / [en] Let G = ( V, E) be a connected undirected graph , where V is the set of nodes and E denotes the set of edges. A 2- path between nodes (s,t)is a sequence of a most two edges connecting them. Given a non-negative weight function associated with edges of G and a set D of origin- destination pairs of nodes, the 2-path network design problem (2PNDP) consists in finding a minimum weighted subset of edges containing a 2-path between the extremities of every origin-destination pair in D. Applications can be found in the design of communication networks , in which paths with few edges are sought to enforce high reliability and small delays. The GRASP metaheuristic is a multistart process , in which each iteration consists of two phases : construction and local search. The best solution found after a fixed number of iterations is returned. Path- relinking is applied as an attempt to improve the solutions found at the of each GRASP iteration. Parallel implementations of metaheuistics ara very robust. Typical parallelizations of GRASP correspond to multiple-walk independent-thread strategies, based on the balanced distribuiton of the iterations over the processors. In the case of multiple-walk cooperative-thread strategies, the processors exchange and share information collected along the trajectories that they investigate. In this thesis, sequential and parallel heuristics are developed for 2PNDP. Variants and combinations of GRASP with path-relinking are analysed by comparing the results of the proposed algorithms with those obtained by others algoritms described in the literature. Parallel GRASP with pathrelinking heuristcs are compared to investigate the influence of the cooperation among processors in terms of solution quality and processing time. We also explore different strategies to optimize the parallel implementations, to make better use of the computational resources and to reduce communication and memory conflicts.

Au cours des dernières années, les fournisseurs de contenu ont connu une forte augmentation des demandes de contenus vidéo et de services riches en média. Compte tenu des limites de la mise à l'échelle du réseau et au-delà des réseaux de diffusion de contenu, les fournisseurs de services Internet développent leurs propres systèmes de mise en cache afin d'améliorer la performance du réseau. Ces facteurs expliquent l'enthousiasme à l'égard du concept de réseau centré sur le contenu et de sa fonction de mise en cache en réseau. La quantification analytique de la performance de la mise en cache n'est toutefois pas suffisamment explorée dans la littérature. De plus, la mise en place d'un système de caching efficace au sein d'une infrastructure réseau est très complexe et demeure une problématique ouverte. Pour traiter ces questions, nous présentons d'abord dans cette thèse un modèle générique et précis de cache nommé MACS (Markov chain-based Approximation of Caching Systems) qui peut être adapté très facilement pour représenter différents schémas de mise en cache et qui peut être utilisé pour calculer différentes mesures de performance des réseaux multi-cache. Nous avons ensuite abordé le problème de l'allocation des ressources de cache dans les réseaux avec capacité de caching. Moyennant notre outil analytique MACS, nous présentons une approche permettant de résoudre le compromis entre différentes mesures de performance en utilisant l'optimisation multi-objectif et nous proposons une adaptation de la métaheuristique GRASP pour résoudre le problème d'optimisation. / In the last few years, Content Providers (CPs) have experienced a high increase in requests for video contents and rich media services. In view of the network scaling limitations and beyond Content Delivery Networks (CDNs), Internet Service Providers (ISPs) are developing their own caching systems in order to improve the network performance. These factors explain the enthusiasm around the Content-Centric Networking (CCN) concept and its in-network caching feature. The analytical quantification of caching performance is, however, not sufficiently explored in the literature. Moreover, setting up an efficient caching system within a network infrastructure is very complex and remains an open problem. To address these issues, we provide first in this thesis a fairly generic and accurate model of caching nodes named MACS (Markov chain-based Approximation of Caching Systems) that can be adapted very easily to represent different caching schemes and which can be used to compute different performance metrics of multi-cache networks. We tackled after that the problem of cache resources allocation in cache-enabled networks. By means of our analytical tool MACS, we present an approach that solves the trade-off between different performance metrics using multi-objective optimization and we propose an adaptation of the metaheuristic GRASP to solve the optimization problem.

O problema de dimensionamento de lotes, objeto desse estudo, considera um ambiente composto por múltiplas plantas independentes, múltiplos itens e múltiplos períodos. O ambiente de produção tem capacidade limitada e as plantas podem produzir os mesmos itens. Cada planta tem uma demanda própria e é permitida a transferência de lotes entre as plantas, o que envolve um certo custo. Este problema tem como caso particular o de dimensionamento de lotes com máquinas paralelas. O objetivo desta dissertação é propor uma heurística baseada na meta-heurística GRASP (Greedy Randomized Adaptive Search Procedures). Além disso, uma estratégia path relinking foi incorporada ao GRASP como uma fase de melhoria do algoritmo. Para verificar a eficiência da heurística proposta, os seus resultados são comparados aos da literatura tanto no caso de máquinas paralelas quanto no de múltiplas plantas. Como resultado, o problema de múltiplas plantas obteve melhores resultados quando comparado aos da heurística da literatura. Com relação ao problema de máquinas paralelas, a heurística proposta se mostrou competitiva / The lot sizing problem, which is the aim of this study, considers an environment consisting of multiple independent plants, multiple items and multiple periods. The production environment has limited capacity and the plants can produce the same items. Each plant has its own demand and the lot transfers between the plants are permitted, which involves a certain cost. This problem has as a particular case the parallel machines lot sizing problem. The objective of this dissertation is to propose a heuristic based on the GRASP (Greedy Randomized Adaptive Search Procedures). Furthermore, a path relinking phase is embedded in the GRASP to obtain better performance. To verify the efficiency of the proposed heuristic, its results were compared with the literature as for the multi-plant as for parallel machines problem. Computational tests showed that the proposed heuristic performed better than other literature heuristic concerning the multiplant problem. Concerning the parallel machines, the heuristic is competitive

Today, most robots used in the industry are preprogrammed and require a welldefined and controlled environment. Reprogramming such robots is often a costly process requiring an expert. By enabling robots to learn tasks from human demonstration, robot installation and task reprogramming are simplified. In a longer time perspective, the vision is that robots will move out of factories into our homes and offices. Robots should be able to learn how to set a table or how to fill the dishwasher. Clearly, robot learning mechanisms are required to enable robots to adapt and operate in a dynamic environment, in contrast to the well defined factory assembly line. This thesis presents contributions in the field of robot task learning. A distinction is made between direct and indirect learning. Using direct learning, the robot learns tasks while being directly controlled by a human, for example in a teleoperative setting. Indirect learning, however, allows the robot to learn tasks by observing a human performing them. A challenging and realistic assumption that is decisive for the indirect learning approach is that the task relevant objects are not necessarily at the same location at execution time as when the learning took place. Thus, it is not sufficient to learn movement trajectories and absolute coordinates. Different methods are required for a robot that is to learn tasks in a dynamic home or office environment. This thesis presents contributions to several of these enabling technologies. Object detection and recognition are used together with pose estimation in a Programming by Demonstration scenario. The vision system is integrated with a localization module which enables the robot to learn mobile tasks. The robot is able to recognize human grasp types, map human grasps to its own hand and also evaluate suitable grasps before grasping an object. The robot can learn tasks from a single demonstration, but it also has the ability to adapt and refine its knowledge as more demonstrations are given. Here, the ability to generalize over multiple demonstrations is important and we investigate a method for automatically identifying the underlying constraints of the tasks. The majority of the methods have been implemented on a real, mobile robot, featuring a camera, an arm for manipulation and a parallel-jaw gripper. The experiments were conducted in an everyday environment with real, textured objects of various shape, size and color. / QC 20100706

Made available in DSpace on 2014-12-17T15:48:01Z (GMT). No. of bitstreams: 1 EdmilsonFMOJ_DISSERT.pdf: 4310075 bytes, checksum: c753f90b3f1afd654108edecd6a3fc70 (MD5) Previous issue date: 2012-02-27 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / This work seeks to propose and evaluate a change to the Ant Colony Optimization based on the results of experiments performed on the problem of Selective Ride Robot (PRS, a new problem, also proposed in this paper. Four metaheuristics are implemented, GRASP, VNS and two versions of Ant Colony Optimization, and their results are analyzed by running the algorithms over 32 instances created during this work. The metaheuristics also have their results compared to an exact approach. The results show that the algorithm implemented using the GRASP metaheuristic show good results. The version of the multicolony ant colony algorithm, proposed and evaluated in this work, shows the best results / Este trabalho tem o objetivo de propor e avaliar uma variante para o algoritmo de col?nia de formigas baseando-se no resultado de experimentos executados sobre o problema do Passeio do Rob? Seletivo (PRS, um novo problema, tamb?m proposto neste trabalho. S?o implementadas quatro metaheur?sticas, GRASP, VNS, e duas vers?es do Otimiza??o por Col?nia de Formigas, e analisados seus resultados executando-os sobre 32 inst?ncias criadas no trabalho. As metaheur?sticas tamb?m tem seu resultado comparado com o de um algoritmo exato. Os resultados mostram que o algoritmo implementado utilizando a metaheur?stica GRASP apresenta bons resultados. A vers?o multi-col?nias do algoritmo de col?nia de formigas, proposta e avaliada no trabalho, apresenta os melhores resultados

Ce doctorat a porté, pour partie, sur une problématique dérivée du cas de la Supply Chain Tourisme Camionnette Europe de la société Michelin. Celle-ci a été formulée comme un problème d’Affectation Stratégique des Productions et de Dimensionnement des Ressources ainsi que de la Flexibilité (ASPDRF) du système de production d’une Supply Chain dans un contexte incertain. Ce problème ASPDRF présentant un certain nombre de spécificités rendant impossible le recours à des méthodes existantes ; un modèle linéaire dédié ainsi qu’une métaheuristique de type « Greedy Randomized Adaptative Search Procedure » (GRAPS) ont été construits. Cette dernière a permis l’obtention de résultats de bonnes qualités et industriellement exploitables et, ce, même dans le cas d’instances de très grandes tailles ; instances ne pouvant être résolues par le recours à la programmation linéaire. Ceci constitue, en plus de l’originalité de certaines contraintes considérées, l’un des apports de ces travaux de doctorat vis-à-vis de la thématique du Supply Chain Network Design à laquelle ils se rattachent. Au-delà de la résolution du problème ASPDRF, ces travaux de doctorat ont également portés sur la réalisation d’un environnement intégré de planification couvrant les horizons stratégique, tactiques et opérationnels ainsi que les différentes boucles de rétroaction associées. Celui-ci a pour vocation d’apporter une aide au manager lors des différentes étapes de prises de décisions associées à ces horizons de planification. Cet environnement, constitué du GRASP proposé ainsi que de modèles de flot et de modèles linéaires spécifiques, présente lui aussi la particularité de pouvoir adresser des problèmes de grandes tailles. / Works made during this PhD deal with a problem arising from the Europe Tourism Supply Chain of the firm Michelin. They are formulated as a Strategic Production Allocation, Resource sizing and Flexibility design problem of a Supply Chain Manufacturing System in an uncertain context. Because of it’s specificities, this problem can’t be solved using existing methods. Consequently, a dedicated linear program and a metaheuristic have been defined. This metaheuristic corresponds to a dedicated « Greedy Randomized Adaptive Search Procedure » (GRAPS). It has led to good quality solutions with real industrial meaningful even in the case of large scale problems. As originality of considered constraints, this result is a contribution regarding existing studies about Supply Chain Network Design problems. Moreover, in the context of this PhD, a global planning system dealing with strategic, tactical and operational planning has been defined. It constitutes a helping tool to manage Supply Chain regarding several options and risky situations. This system consists of the proposed GRASP but also of several dedicated flow models and linear models. It is able to tackle large scale problems in a rather short time.