Les travaux exposés dans cette thèse sont de natures multiples mais visent tous à une meilleure compréhension du geste de saisie chez l'homme, que ce soit d'un point de vue comportemental, cinématique ou de contrôle. Lorsqu'il doit saisir un objet, l'homme s'appuie sur une structure de contrôle multi-niveaux ainsi que son expérience, ce qui lui permet d'estimer les mouvements à effectuer de manière très efficace avant même d'avoir commencé à bouger. Nous pensons que ce mode de commande peut apporter une solution innovante au double problème de l'atteinte et de la saisie par une main artificielle. Nous avons donc développé une architecture de commande distribuée reproduisant en partie ces mécanismes et capable de contrôler ce genre d'artefacts de manière efficace, déclinée en plusieurs versions en fonction du niveau de contrôle souhaité. Elle est constituée d'un ensemble d'unités d'appariement s'inspirant des structures présentes dans le Système Nerveux Central : chacune a en charge une partie du problème global à résoudre, elles intègrent des informations en provenance de la consigne et/ou d'autres unités à travers des échanges parfois redondants, et elles s'appuient sur un algorithme d'apprentissage supervisé. Afin de mieux comprendre les principes qui sous-tendent le mouvement humain nous nous sommes aussi intéressés à la modélisation de la main et du geste de saisie, que ce soit à travers un protocole d'expérimentation chez l'homme ou l'analyse de données médicales et vidéos chez le singe / Works presented in this thesis are of multiple kinds but all aim at a better understanding of the human grasping movements, may it be from a behavioural, kinematics or control point of view. When one wants to grasp an object he relies on a multilayer control structure and its personal experience, the two of which allow him to estimate the appropriate move in a very efficient way, even before he actually started to move. We think that this type of command can bring forth an innovative solution to the double reach and grasp problem that face an artificial hand. We developed a distributed command architecture that reproduce in part these mechanisms and is able to control this type of artefacts in an efficient way, several versions of which were implemented regarding the desired control level. It consists of a group of matching units that takes inspiration in the Central Nervous System: each of them is in charge of a part of the global problem to be solved; they integrate data from the system inputs and/or from other units in partly redundant ways; and they rely on a supervised learning algorithm. In order to better understand the underlying principles of human movement we also took interest in hand and grasping movement models, may it be through an experimental protocol on human or monkey medical and video data analysis

The aim of this thesis was to assess the influence of canistherapeutic intervention on the level of fine motor skills in patients with rare diseases, namely mitochondrial encephalocardiomyopathy caused by TMEM70 gene mutation and Leigh syndrome. Canistherapeutic intervention in these patients is based on activation of motoric functions during programme reasonably designed according to the needs of specific patients. The assistance of the dog is used to achieve this activation. The dog acts as an important motivational factor and the direct contact with it contributes to development of sensomotoric skills of these patients. The thesis summarizes general information about rare diseases and focuses on one of the subgroups of mitochondrial disorders. It presents knowledge about the Leigh syndrome and mitochondrial encephalocardiomyopathy caused by TMEM70 gene mutation. Subsequently the thesis presents information about canistherapy and fine motor skills. The thesis further contains case reports of patients, data from research units and their evaluation. The aim of the thesis was to find out whether patients with mitochondrial disease show improvement of quality and effectivity of selected grasp forms and thus faster and more precise execution assigned tasks focusing on object manipulations. Partial...

La manipulation dextre est un sujet important dans la recherche en robotique et dans lequel peu de travaux ont abordé la manipulation d'objets déformables. De nouvelles applications en chirurgie, en industrie agroalimentaire ou encore dans les services à la personne nécessitent la maîtrise de la saisie et la manipulation d'objets déformables. Cette thèse s’intéresse à la manipulation d’objets déformables par des préhenseurs mécaniques anthropomorphiques tels que des mains articulées à plusieurs doigts. Cette tâche requière une grande expertise en modélisation mécanique et en commande : modélisation des interactions, perception tactile et par vision, contrôle des mouvements des doigts en position et en force pour assurer la stabilité de la saisie. Les travaux présentés dans cette thèse se focalisent sur la modélisation de la saisie d'objets déformables. Pour cela, nous avons utilisé une discrétisation par des systèmes masses-ressorts non-linéaires pour modéliser des corps déformables en grands déplacements et déformations tout en ayant un coût calculatoire faible. Afin de prédire les forces d’interactions entre main robotique et objet déformable, nous avons proposé une approche originale basée sur un modèle rhéologique visco-élasto-plastique pour évaluer les forces tangentielles de contact et décrire la transition entre les modes d’adhérence et de glissement. Les forces de contact sont évaluées aux points nodaux en fonction des mouvements relatifs entre les bouts des doigts et les facettes du maillage de la surface de l’objet manipulé. Une autre contribution de cette thèse consiste à utiliser de cette modélisation dans la planification des tâches de manipulation d’objets déformables 3D. Cette planification consiste à déterminer la configuration optimale de la main pour la saisie de l’objet ainsi que les trajectoires à suivre et les efforts à appliquer par les doigts pour contrôler la déformation de l’objet tout en assurant la stabilité de l’opération. La validation expérimentale de ces travaux a été réalisée sur deux plateformes robotiques : une main Barrett embarquée sur un bras manipulateur Adept S1700D et une main Shadow embarquée sur un bras manipulateur Kuka LWR4+. / Dexterous manipulation is an important issue in robotics research in which few works have tackled deformable object manipulation. New applications in surgery, food industry or in service robotics require mastering the grasping and manipulation of deformable objects. This thesis focuses on deformable object manipulation by anthropomorphic mechanical graspers such as multi-fingered articulated hands. This task requires a great expertise in mechanical modeling and control: interaction modeling, tactile and vision perception, force / position control of finger movements to ensure stable grasping. The work presented in this thesis focuses on modeling the grasping of deformable objects. To this end, we used a discretization by non-linear mass-spring systems to model deformable bodies in large displacements and deformations while having a low computational cost. To predict the interaction forces between robot hand and deformable object, we proposed an original approach based on a visco-elasto-plastic rheological model to evaluate tangential contact forces and describe the transition between the sticking and slipping modes. The contact forces are evaluated at nodes as function of the relative movements between the fingertips and the surface mesh facets of the manipulated object. Another contribution of this thesis is the use of this model in the planning of 3D deformable object manipulation tasks. This planning consists in determining the optimal configuration of the hand for grasping the objects as well as the paths to track and the efforts to be applied by the fingers to control the deformation of the object while ensuring the stability of the operation. The experimental validation of this work has been carried out on two robotic platforms: a Barrett hand embedded on a Adept S1700D ® manipulator and a Shadow hand embedded on a Kuka LWR4+® manipulator.

Ce travail de thèse de doctorat est dédié à l'étude de problèmes d'optimisation combinatoire du domaine des architectures massivement parallèles avec la prise en compte des données incertaines tels que les temps d'exécution. On s'intéresse aux programmes sous contraintes probabilistes dont l'objectif est de trouver la meilleure solution qui soit réalisable avec un niveau de probabilité minimal garanti. Une analyse quantitative des données incertaines à traiter (variables aléatoires dépendantes, multimodales, multidimensionnelles, difficiles à caractériser avec des lois de distribution usuelles), nous a conduit à concevoir une méthode qui est non paramétrique, intitulée "approche binomiale robuste". Elle est valable quelle que soit la loi jointe et s'appuie sur l'optimisation robuste et sur des tests d'hypothèse statistique. On propose ensuite une méthodologie pour adapter des algorithmes de résolution de type approchée pour résoudre des problèmes stochastiques en intégrant l'approche binomiale robuste afin de vérifier la réalisabilité d'une solution. La pertinence pratique de notre démarche est enfin validée à travers deux problèmes issus de la compilation des applications de type flot de données pour les architectures manycore. Le premier problème traite du partitionnement stochastique de réseaux de processus sur un ensemble fixé de nœuds, en prenant en compte la charge de chaque nœud et les incertitudes affectant les poids des processus. Afin de trouver des solutions robustes, un algorithme par construction progressive à démarrages multiples a été proposé ce qui a permis d'évaluer le coût des solution et le gain en robustesse par rapport aux solutions déterministes du même problème. Le deuxième problème consiste à traiter de manière globale le placement et le routage des applications de type flot de données sur une architecture clustérisée. L'objectif est de placer les processus sur les clusters en s'assurant de la réalisabilité du routage des communications entre les tâches. Une heuristique de type GRASP a été conçue pour le cas déterministe, puis adaptée au cas stochastique clustérisé. / This PhD thesis is devoted to the study of combinatorial optimization problems related to massively parallel embedded architectures when taking into account uncertain data (e.g. execution time). Our focus is on chance constrained programs with the objective of finding the best solution which is feasible with a preset probability guarantee. A qualitative analysis of the uncertain data we have to treat (dependent random variables, multimodal, multidimensional, difficult to characterize through classical distributions) has lead us to design a non parametric method, the so-called "robust binomial approach", valid whatever the joint distribution and which is based on robust optimization and statistical hypothesis testing. We also propose a methodology for adapting approximate algorithms for solving stochastic problems by integrating the robust binomial approach when verifying for solution feasibility. The paractical relevance of our approach is validated through two problems arising in the compilation of dataflow application for manycore platforms. The first problem treats the stochastic partitioning of networks of processes on a fixed set of nodes, by taking into account the load of each node and the uncertainty affecting the weight of the processes. For finding stochastic solutions, a semi-greedy iterative algorithm has been proposed which allowed measuring the robustness and cost of the solutions with regard to those for the deterministic version of the problem. The second problem consists in studying the global placement and routing of dataflow applications on a clusterized architecture. The purpose being to place the processes on clusters such that it exists a feasible routing, a GRASP heuristic has been conceived first for the deterministic case and afterwards extended for the chance constrained variant of the problem.

Orientador: Rubén Augusto Romero Lazaro / Resumo: O problema de reconfiguração de sistemas de distribuição de energia elétrica consiste em encontrar uma configuração radial por meio da permutação do estado das chaves (abertura ou fechamento) dos ramos de um sistema elétrico. O objetivo é de se alcançar a minimização das perdas elétricas. Cada configuração radial só é considerada factível se respeitar certas restrições operacionais como o limite de tensão nas barras e os limites de correntes nos circuitos. O modelo tratado neste trabalho apresenta explosão combinatória e difícil tratabilidade por meio de métodos convencionais de otimização. O problema, computacionalmente falando, é considerado Não-Polinomial Completo (NPC), pois não possui uma resposta em tempo polinomial a partir de uma entrada definida. Neste trabalho são apresentadas três técnicas meta-heurísticas para se tratar o problema de reconfiguração de sistemas de distribuição de energia elétrica, totalmente diferentes entre uma e outra, atuando em conjunto, para somente um nível de demanda, no intuito de se encontrar a topologia ótima, com o objetivo de se minimizar as perdas elétricas ativas. Além disso, propôs-se modificar o paradigma clássico de implementação estático deste tipo de problema para o paradigma de programação dinâmica por meio de árvores com filhos variados a fim de que a estrutura de dados utilizada representasse fielmente um sistema de distribuição de energia elétrica na memória do computador. As meta-heurísticas implementadas foram a Greedy Rand... (Resumo completo, clicar acesso eletrônico abaixo) / Doutor

[EN] The primary handling of food with robots calls for the development of new manipulation devices, especially when products are easily damaged and have a wide range of shapes and textures. These difficulties are even greater in the agricultural industry because the quality of the products is also checked during the manual handling process. This PhD dissertation provides solutions to these issues and helps to further introduce robotics into the handling of food. Several methods for handling food are included and analyzed, and specific solutions are proposed and then validated with prototypes. The research focuses on devices capable of adapting themselves to the shapes of the products without increasing the complexity of the mechanism. After analyzing several different solutions, the method chosen involves the use of under-actuated mechanisms, compliant mechanisms and fingers with pads filled with granular fluids. These fluids can behave as quasi-liquids or quasi-solids due to the jamming transition, which provides a soft initial grasp and can support high stresses during fast movements performed by the robot. The additive manufacturing process provides an opportunity to develop robot grippers that are lighter, simpler, more flexible and cheaper. By using this process elastic mechanisms are manufactured in a single part, which are equivalent to mechanisms with several rigid parts connected by joints. Laser sintering is employed to produce pneumatic actuators, with different types of motions, based on the elastic properties of the materials used in this manufacturing process. As a result, the systems can be simplified to achieve grippers, with several fingers, that are produced as a single part. In order to estimate the freshness and quality of agricultural products while they are being grasped, accelerometers are added to the fingers of several grippers. Accelerometers are economical and act as intrinsic tactile sensors. They can be easily embedded, thereby reducing the risk of getting damaged due to contact with the product, and allow each of the grasping phases to be identified. To achieve good performance of the accelerometers, a specific process is defined for the robot gripper, which touches the products a few times. In addition, several gripper prototypes are manufactured with diverse under-actuated mechanisms, jamming systems, and a new program that processes the signals from the accelerometers using different procedures in order to obtain parameters that can be used to estimate the quality of products. These parameters are correlated with data from destructive tests that are commonly used as a reference. The best performance of the accelerometers is achieved when the finger employs a granular fluid, a correlation coefficient of 0.937 being accomplished for the ripeness of mangoes and 0.872 for the firmness of eggplants. / [ES] La manipulación primaria de alimentos con robots precisa del desarrollo de nuevos sistemas de manipulación especialmente cuando los productos son sensibles al daño y presentan una amplia variabilidad de formas y texturas. En el sector agroalimentario las dificultades son aún mayores ya que la manipulación manual sirve además para inspeccionar los productos durante el proceso. Está tesis aporta soluciones a estos problemas facilitando la incorporación de la robótica. En la tesis se recopilan y analizan diversas soluciones para poder manipular alimentos proponiendo soluciones concretas que luego son validadas con prototipos. La investigación se centra en aquellos sistemas que son capaces de auto adaptarse a las formas de los productos sin incrementar la complejidad del mecanismo. Tras analizar diversas técnicas se propone el uso de mecanismos infra-actuados, mecanismos flexibles y dedos con fluidos granulares que, al estar encerrados dentro de una membrana, se comportan como cuasi-líquidos o cuasi-sólidos gracias a la transición jamming, permitiendo un agarre inicial suave y la posibilidad de transmitir esfuerzos elevados durante los movimientos del robot. En la búsqueda de garras más ligeras, sencillas, flexibles y económicas se aprovecha la oportunidad que brinda la tecnología de fabricación aditiva de material. Gracias a este proceso se fabrican mecanismos flexibles realizados en una única pieza y que equivalen a mecanismos de garras realizados con varias piezas rígidas unidos por articulaciones. Mediante el sinterizado por láser, se fabrican actuadores neumáticos, con diversos tipos de movimiento, basados en la flexibilidad del material empleado en su fabricación. En conjunto se simplifican los sistemas llegando a realizar garras flexibles de varios dedos fabricadas en una única pieza. Para evaluar la calidad y frescura de los productos agroalimentarios durante el agarre se emplean acelerómetros localizados en los dedos de varias garras. Los acelerómetros son económicos y se comportan como sensores táctiles intrínsecos, están fuera del contacto directo con el producto evitando desgastes por contacto y permiten identificar las distintas fases de agarre. Para lograr esto se desarrolla un proceso específico del robot con la garra, que palpa varias veces el producto. Se fabrican diversos tipos de garra con distintas tecnologías de mecanismos infra-actuados y sistemas jamming y se programa un algoritmo original de procesado de señal que con diversas técnicas es capaz de extraer parámetros de los acelerómetros que sirven para evaluar la calidad de los productos. Estos parámetros son correlacionados con los datos de ensayos destructivos que son habitualmente empleados como referencia. Las mejores capacidades se consiguen empleando garras con jamming lográndose coeficientes de correlación de 0.937 en índices de madurez con mangos y 0.872 en firmeza de berenjenas. / [CAT] La manipulació primària d'aliments amb robots precisa del desenvolupament de nous sistemes de manipulació especialment quan els productes són sensibles al dany i presenten una àmplia variabilitat de formes i textures. En el sector agroalimentari les dificultats són encara més grans ja que la manipulació manual serveix a més per a inspeccionar els productes durant el procés. Aquesta tesi aporta solucions a aquests problemes facilitant la incorporació de la robòtica. En la tesi es recopilen i analitzen diverses solucions per a poder manipular aliments proposant solucions concretes que després són validades amb prototips. La investigació es centra en aquells sistemes que són capaços d'auto adaptar-se a la forma dels productes sense incrementar la complexitat del mecanisme. Després d'analitzar diverses tècniques es proposa l'ús de mecanismes infra-actuats, mecanismes flexibles i dits amb fluids granulars que, tancats dins d'una membrana, es comporten com quasi-líquids o quasi-sòlids gràcies a la transició jamming, permetent una prensió inicial suau i la possibilitat de transmetre esforços elevats durant els moviments del robot. En la recerca d'urpes més lleugeres, senzilles, flexibles i econòmiques s'aprofita l'oportunitat que brinda la tecnologia de fabricació additiva de material. Gràcies a aquest procés es fabriquen mecanismes flexibles realitzats en una única peça i que equivalen a mecanismes d'urpes realitzats amb diverses peces rígides unides per articulacions. Mitjançant el sinteritzat per làser, es fabriquen actuadors pneumàtics, amb diversos tipus de moviment, basats en la flexibilitat del material emprat en la seva fabricació. En conjunt es simplifiquen els sistemes arribant a realitzar urpes flexibles de diversos dits fabricades en una única peça. Per a avaluar la qualitat i frescor dels productes agroalimentaris durant la manipulació s'empren acceleròmetres localitzats en els dits de diverses urpes. Els acceleròmetres són econòmics i es comporten com a sensors tàctils intrínsecs, sense estar en contacte directe amb el producte evitant desgastos per aquest motiu, i permeten identificar les diferents fases d'prensió. Per aconseguir això es desenvolupa un procés específic del robot amb l'urpa, que palpa diverses vegades el producte. Es fabriquen diversos tipus d'urpa amb diferents tecnologies de mecanismes infra-actuats i sistemes jamming i es programa un algoritme original de processat de senyal que, amb diverses tècniques, és capaç d'extreure paràmetres dels acceleròmetres que serveixen per a avaluar la qualitat dels productes. Aquests paràmetres són correlacionats amb les dades d'assajos destructius que són habitualment emprats com a referència. Les millors capacitats s'aconsegueixen emprant urpes amb jamming assolint-se coeficients de correlació de 0,937 en índexs de maduresa amb mangos i 0,872 en fermesa d'albergínies. / Blanes Campos, C. (2016). Garras con sensores táctiles intrínsecos para manipular alimentos con robots [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/68481 / TESIS

Les travaux de cette thèse portent sur la saisie et la manipulation dextre et ont pour dénominateur commun la robustesse vis-à-vis d'un environnement incertain (méconnaissance de la géométrie de l'objet ou du préhenseur, initialisation imparfaite du système, etc). La mesure de qualité de prise permet d'évaluer la stabilité d'une saisie. Nos travaux proposent une nouvelle mesure de qualité de prise, dont le principe reste dans la continuité des méthodes les plus connues qui consistent à déterminer l'espace des torseurs dynamiques applicables sur l'objet par le préhenseur. Notre mesure cherche à déterminer cet espace quelle que soit l'incertitude qui affecte le système préhenseur/objet. On appelle cet ensemble le Reachable Wrench Space under Uncertainties (RWSU). Deux algorithmes sont proposés afin de déterminer un majorant et un minorant du RWSU. La deuxième contribution concerne l'application d'algorithmes de commande robuste aux incertitudes de modèle pour la manipulation dextre. La première méthode de commande que nous proposons est un retour d'état, permettant de répondre à la consigne de manipulation, auquel on ajoute une action dynamique, permettant de répondre aux contraintes de saisie. Le retour d'état est synthétisé suivant un problème d'optimisation avec contraintes LMI. Les contraintes LMI permettent de définir la réponse dynamique du système bouclé, et d'assurer la robustesse aux incertitudes de modèle. Une seconde méthode de commande est proposée afin d'améliorer les performances de suivi de trajectoire pour ce système MIMO en découplant le mouvement à suivre des mouvements perturbateurs résultant des couplages dynamiques entre les axes. / This thesis deals with grasping and dexterous manipulation with multifingered hands, with the robustness to uncertain environments as a common denominator.The first contribution of the present work is a new measure of the grasp quality, which is used to evaluate the stability of a grasp. In the footsteps of the most known methods which consist in determining the reachable wrench space, our measure aims to evaluate this space whatever the uncertainty which affects the gripper/object system. This new space is called Reachable Wrench Space under Uncertainty (RWSU). Two algorithms are proposed to find respectively an upper and a lower bound of the RWSU.The second contribution concerns the application of robust control algorithms for dexterous manipulation. The first control method is composed of as a state-space feedback, which enables a manipulation task, and of an additional dynamic action, allowing to respect the grasp constraints. The state-space feedback is designed for a robust regional pole placement by the resolution of an optimization problem under LMI constraints. The LMI constraints define the dynamic response of the system in closed loop, and ensure the robustness with respect to model uncertainties. A second control method, based on eigenstructure assignment, is proposed to improve the trajectory tracking for the MIMO system. The eigenstructure assignment decouples the movement of the task from the disturbing movements resulting from the dynamic coupling between the axes.

One way of reducing the examination time in magnetic resonance imaging (MRI) is to reduce the amount of raw data acquired, by performing so-called undersampling. Conventionally, MRI data is acquired line-by-line on a Cartesian grid. In the field of Cardiovascular Magnetic Resonance (CMR), however, radial k-space sampling is seen as a promising emerging technique for rapid image acquisitions, mainly due to its robustness against motion disturbances occurring from the beating heart. Whereas Cartesian undersampling will result in image aliasing, radial undersampling will introduce streak artifacts. The objective of this work was to train the deep learning architecture, CycleGAN, to reduce streak artifacts in radially undersampled CMR images, and to evaluate the model performance. A benefit of using CycleGAN over other deep learning techniques for this application is that it can be trained on unpaired data. In this work, CycleGAN network was trained on 3060 radial and 2775 Cartesian unpaired CMR images acquired in human subjects to learn a mapping between the two image domains. The model was evaluated in comparison to images reconstructed using another emerging technique called GRASP. Whereas more investigation is warranted, the results are promising, suggesting that CycleGAN could be a viable method for effective streak-reduction in clinical applications.

O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta-heurísticas de diferentes categorias. Essas meta-heurísticas são: Iterated Local Search (ILS), classificada como meta-heurística de trajetória; Greedy Randomized Adaptive Search (GRASP), meta-heurística construtiva; e Artificial Bee Colony (ABC), meta-heurística populacional recentemente proposta. Esses métodos foram selecionados por alcançarem bons resultados para diversos problemas de otimização da literatura. São realizados experimentos computacionais com 600 instâncias do JSF, permitindo comparações entre os métodos de resolução. Os resultados mostram que explorar as características do problema permite que uma das regras de prioridade propostas supere a melhor regra da literatura em 81% das instâncias. As meta-heurísticas ILS, GRASP e ABC chegam a conseguir mais de 31% de melhoria sobre as soluções iniciais e a obter atrasos, em média, somente 2,24% superiores aos das soluções ótimas. Também são propostas modificações nas meta-heurísticas que permitem obter melhorias ainda mais expressivas sem aumento do tempo de execução. Adicionalmente é estudada uma versão do JSF com operações de Montagem e Desmontagem (JSFMD) e os experimentos realizados com um conjunto de 150 instâncias também indicam o bom desempenho dos métodos desenvolvidos. / The production environment addressed herein is the Flexible Job Shop (FJS), a generalization of the Job Shop (JS). In the JS environment, the jobs scheduling problem is classified by Garey; Johnson and Sethi (1976) as NP-Hard and the FJS is at least as difficult as the JS. FJS is composed of a set of jobs, each consisting of operations. Each operation must be processed individually, without interruption, in a single machine of a subset of enabled machines. The main performance criterion is minimizing the jobs tardiness. Mixed Integer Linear Programming (MILP) models are presented. These models minimize the total tardiness and the completion time of the last operation, makespan. New priority rules of jobs are proposed, as well as adaptations of rules from the literature. These rules are used by constructive heuristics and are combined with strategies aimed at exploiting specific characteristics of FSJ. In order to improve the solutions initially obtained, local searches and other improvement mechanisms are proposed and used in the development of metaheuristics of three different categories. These metaheuristics are: Iterated Local Search (ILS), classified as trajectory metaheuristic; Greedy Randomized Adaptive Search (GRASP), constructive metaheuristic, and Artificial Bee Colony (ABC), recently proposed population metaheuristic. These methods were selected owing to their good results for various optimization problems in the literature. Computational experiments using 600 FJS instances are carried out to allow comparisons between the resolution methods. The results show that exploiting the characteristics of the problem allows one of the proposed priority rules to exceed the best literature rule in about 81% of instances. Metaheuristics ILS, GRASP and ABC achieve more than 31% improvement over the initial solutions and obtain an average tardiness only 2.24% higher than the optimal solutions. Modifications in metaheuristics are proposed to obtain even more significant improvements without increased execution time. Additionally, a version called Disassembly and Assembly FSJ (DAFJS) is studied and the experiments performed with a set of 150 instances also indicate good performance of the methods developed.

Made available in DSpace on 2014-12-17T15:46:59Z (GMT). No. of bitstreams: 1 PauloHAS_TESE.pdf: 9268945 bytes, checksum: 08c0c5f93ed7b964b99c6df2ee26ab1b (MD5) Previous issue date: 2011-12-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Car Rental Salesman Problem (CaRS) is a variant of the classical Traveling Salesman Problem which was not described in the literature where a tour of visits can be decomposed into contiguous paths that may be performed in different rental cars. The aim is to determine the Hamiltonian cycle that results in a final minimum cost, considering the cost of the route added to the cost of an expected penalty paid for each exchange of vehicles on the route. This penalty is due to the return of the car dropped to the base. This paper introduces the general problem and illustrates some examples, also featuring some of its associated variants. An overview of the complexity of this combinatorial problem is also outlined, to justify their classification in the NPhard class. A database of instances for the problem is presented, describing the methodology of its constitution. The presented problem is also the subject of a study based on experimental algorithmic implementation of six metaheuristic solutions, representing adaptations of the best of state-of-the-art heuristic programming. New neighborhoods, construction procedures, search operators, evolutionary agents, cooperation by multi-pheromone are created for this problem. Furtermore, computational experiments and comparative performance tests are conducted on a sample of 60 instances of the created database, aiming to offer a algorithm with an efficient solution for this problem. These results will illustrate the best performance reached by the transgenetic algorithm in all instances of the dataset / O Problema do Caixeiro Alugador (CaRS) ? uma variante ainda n?o descrita na literatura do cl?ssico Problema do Caixeiro Viajante onde o tradicional tour de visitas do caixeiro pode ser decomposto em caminhos cont?guos e que podem ser realizados em diferentes carros alugados. O problema consiste em determinar o ciclo hamiltoniano que resulte em um custo final m?nimo, considerando o custo da rota adicionado ao custo de uma prov?vel penaliza??o paga em cada troca de ve?culos na rota, penaliza??o devida ao retorno do carro descartado at? a sua cidade base. Sem perda para a generalidade do caso, os custos do aluguel do carro podem ser considerados embutidos nos custos da rota do carro. O presente trabalho introduz o problema geral e o exemplifica, caracterizando igualmente algumas variantes associadas. Uma an?lise geral da complexidade desse problema combinat?rio ? descrita, visando justificar sua classifica??o na classe NP-dif?cil. Um banco de inst?ncias para o problema ? apresentado, descrevendo-se a metodologia de sua constitui??o. O problema proposto tamb?m ? objeto de um estudo algor?tmico experimental baseado na aplica??o de seis metaheur?sticas de solu??o, representando adapta??es do melhor do estado da arte em programa??o heur?stica. Novas vizinhan?as, procedimentos construtivos, operadores de busca, agentes evolucion?rios, coopera??o por multiferom?nios, s?o criados para o caso. Experimentos computacionais comparativos e testes de desempenho s?o realizados sobre uma amostra de 60 inst?ncias, visando oferecer um algoritmo de solu??o competitivo para o problema. Conclui-se pela vantagem do algoritmo transgen?tico em todos os conjuntos de inst?ncias