O problema de empacotamento de itens irregulares com balanceamento da carga é encontrado no carregamento de aviões, caminhões e navios. O objetivo é empacotar itens irregulares utilizando o menor número de recipientes possível de forma que os recipientes estejam balanceados, que os itens não se sobreponham e estejam inteiramente contidos no recipiente. Neste trabalho, propomos três heurísticas bases com três variações cada para o problema com recipientes retangulares e irregulares. As heurísticas utilizam abordagens diferentes para representar os itens e para fazer o balanceamento. Uma das heurísticas utiliza malha para representação dos itens e faz o balanceamento dividindo o recipiente em quadrantes e revezando a alocação dos itens entre eles de forma que o balanceamento é feito de forma indireta. Tal heurística resolve o problema tanto para recipientes retangulares quanto irregulares. A segunda heurística utiliza a representação dos itens por polígonos e impossibilita a sobreposição de itens utilizando a técnica do nofit polygon. A heurística constrói a solução item por item, sem posições fixas e a cada item alocado, os itens são deslocados em direção ao centro de gravidade desejado do recipiente. Esta heurística resolve apenas problemas com recipientes retangulares. A última heurística é uma adaptação da heurística anterior para a resolução do problema com recipientes irregulares, de forma que o problema é resolvido em duas fases. Cada heurística base possui três variações cada, totalizando nove heurísticas. As heurísticas foram comparadas com outro trabalho da literatura e conseguiram melhorar os resultados para nove das dezenove instâncias testadas. / The irregular bin packing problem with load balancing is found in the loading of airplanes, trucks and ships. The aim is to use as few bins as possible to pack all the items so that all bins are balanced, items do not overlap and are fully contained in the bin. In this work, we propose three base heuristics with three variations each for the problem with rectangular and irregular bin. The three heuristics use different approaches to represent the items and to balance the bin. One of the heuristics uses a grid to represent the items and does the balancing by dividing the container into quadrants and alternating the allocation of items between them so that the balancing is done indirectly. Such heuristic solves the problem for both rectangular and irregular bins. The second heuristic uses the representation of items by polygons and uses the nofit polygon technique. The heuristic constructs the solution item by item, with no fixed positions and with each item allocated, the items are shifted towards the desired center of gravity of the bin. This heuristic only solves problems with rectangular bins. The last heuristic is an adaptation of the previous one to solve the problem with irregular bins, so that the problem is solved in two phases. Each base heuristic has three variations, totaling nine heuristics. The heuristics were compared with other work in the literature and managed to improve the results for nine of the nineteen instances tested.

This thesis presents and develops a theory of self-reduction. This process is used to map instances of combinatorial optimisation problems onto smaller, more easily solvable instances in such a way that a solution of the former can be readily re-constructed, without loss of information or quality, from a solution of the latter. Self-reduction rules are surveyed for the Graph Colouring Problem, the Maximum Clique Problem, the Steiner Problem in Graphs, the Bin Packing Problem and the Set Covering Problem. This thesis introduces the problem of determining the maximum sequence of self-reductions on a given structure, and shows how the theory of confluence can be adapted from term re-writing to solve this problem by identifying rule sets for which all maximal reduction sequences are equivalent. Such confluence results are given for a number of reduction rules on problems on discrete systems. In contrast, NP-hardness results are also presented for some reduction rules. A probabilistic analysis of self-reductions on graphs is performed, showing that the expected number of self-reductions on a graph tends to zero as the order of the graph tends to infinity. An empirical study is performed comparing the performance of self-reduction, graph decomposition and direct methods of solving the Graph Colouring and Set Covering Problems. The results show that self-reduction is a potentially valuable, but sometimes erratic, method of finding exact solutions to combinatorial problems.

Un objet multiboîte est composé de plusieurs parties identiques qui doivent être rangées dans des boîtes différentes. La hauteur d'une boîte est alors la somme des hauteurs des objets qu'elle contient. Ce concept généralise et englobe de nombreux problèmes de la littérature de la recherche opérationnelle.<br /><br />Une classification de ces modèles est proposée. Les bases théoriques sont posées. En particulier, la complexité pour les principaux types d'objets et objectifs est déterminée.<br /><br />Une étude détaillée est effectuée lorsque les objets ont des largeurs constantes et que l'on veut minimiser la hauteur de la boîte la plus haute. Des bornes inférieures, des heuristiques avec de très bonnes garanties de performance et un algorithme génétique sont proposés pour résoudre ce modèle. Leurs comportements théoriques et expérimentaux sont analysés.

Cette thèse a été réalisée dans le cadre du projet " Gestion et Optimisation de la Chaîne Documentaire ", projet labellisé par le Pôle de compétitivité des Industries du Commerce. Le projet a pour but de concevoir et de développer un nouveau workflow et un outil d'aide à la décision. Ce système doit être capable de gérer et d'optimiser le flux complet dématérialisé de contrats reçus à COFIDIS.Nous présentons d'abord le framework retenu dans le cadre du projet pour modéliser et implémenter le workflow. En phase de conception BPMN a été choisi. Pour la partie développement, l'utilisation de BPEL a été préconisée pour implémenter et exécuter l'application finale (services web).Cependant la flexibilité offerte par BPMN peut conduire à des propriétés indésirables du processus telles que blocage et inaccessibilité. De plus, BPMN a été conçu pour fournir des modèles Orientés Process. Les données ou les ressources y sont donc peu représentées. En conséquence, l'analyse de performance sur un modèle BPMN est quasi inexistante.Afin de surmonter ces problèmes nous proposons d'insérer dans le framework deux nouvelles phases. Ces deux phases sont appliquées au modèle BPMN. La première est une phase de vérification et de validation et la deuxième une phase d'optimisation. Ces deux phases sont réalisées en transformant le modèle BPMN vers un langage formel. Notre choix dans ce travail a été d'utiliser les réseaux de Petri. Ce qui nous a permis de vérifier et de valider de bonnes propriétés du process. Quant à l'optimisation, nous avons défini une nouvelle variante du problème d'affectation (bin packing problem) et proposé une résolution à intégrer dans le processus d'aide à la décision

One of the remaining obstacles to the widespread application of industrial robots is their inability to deal with parts that are not precisely positioned. In the case of manual assembly, components are often presented in bins. Current automated systems, on the other hand, require separate feeders which present the parts with carefully controlled position and attitude. Here we show how results in machine vision provide techniques for automatically directing a mechanical manipulator to pick one object at a time out of a pile. The attitude of the object to be picked up is determined using a histogram of the orientations of visible surface patches. Surface orientation, in turn, is determined using photometric stereo applied to multiple images. These images are taken with the same camera but differing lighting. The resulting needle map, giving the orientations of surface patches, is used to create an orientation histogram which is a discrete approximation to the extended Gaussian image. This can be matched against a synthetic orientation histogram obtained from prototypical models of the objects to be manipulated. Such models may be obtained from computer aided design (CAD) databases. The method thus requires that the shape of the objects be described, but it is not restricted to particular types of objects.

This paper describes a hand-eye system we developed to perform the binpicking task. Two basic tools are employed: the photometric stereo method and the extended Gaussian image. The photometric stereo method generates the surface normal distribution of a scene. The extended Gaussian image allows us to determine the attitude of the object based on the normal distribution. Visual analysis of an image consists of two stages. The first stage segments the image into regions and determines the target region. The photometric stereo system provides the surface normal distribution of the scene. The system segments the scene into isolated regions using the surface normal distribution rather than the brightness distribution. The second stage determines object attitude and position by comparing the surface normal distribution with the extended-Gaussian-image. Fingers, with LED sensor, mounted on the PUMA arm can successfully pick an object from a pile based on the information from the vision part.

Notre problème consiste à déterminer le nombre de grands rectangles identiques nécessaires pour ranger une liste de rectangles sans modifier leur orientation. Nous proposons des méthodes pour calculer des bornes inférieures pour ce problème, essentiellement basée sur le concept de fonctions dual-réalisables. Nous proposons aussi deux méthodes exactes de type énumératives. L'une permet de déterminer si un ensemble de rectangles peut être contenu dans un rectangle unique. Elle repose sur une nouvelle relaxation du problème. La deuxième méthode permet de résoudre le problème général de bin packing en deux dimensions. Elle calcule pour cela une décomposition itérative de l'ensemble des rectangles à placer.

The term “Fundamentalism” used as a comparative category within the academic study of religion has become problematic. Fundamentalism, is not one comprehensive movement but is, in fact, a phenomenon which encompasses a variety of beliefs, practices, and expectations. This thesis will explore the diversity of several different and distinct fundamentalist movements. I will discuss the natures of four Christian movements that have been labeled “fundamentalist” – Jehovah’s Witnesses, Christian Reconstructionists, Jerry Falwell and Pat Robertson – on several key points, eschatology, political philosophy, as well as level of social involvement. I will then turn to fundamentalism as it is used as a category to describe a global phenomenon. I will discuss three different scholarly approaches by turning to the work of Bruce Lawrence, Mark Juergensmeyer, and Bruce Lincoln on the Islamic “fundamentalist” group al- Qaeda. Finally I will argue that the category “fundamentalism” can be best understood in terms of a family resemblance.

Detta examensarbete har ägt rum vid Produktionsverkstad 1 (PV1) på Wexiödisk AB där diskmaskiner av huvtyp tillverkas. Syftet med detta examensarbete har varit att undersöka vilka lagerstyrningsmodeller som är lämpliga för att styra avdelningens materialflöden med. Arbetet har genomförts i två steg. Först behandlades artiklar unika för produkterna vid PV1, därefter artiklar gemensamma med andra produkter. Enligt modeller ur relevant litteratur utformades förslag på hur dessa kunde appliceras praktiskt. Förslagen presenterades och diskuterades med berörd personal som valde Tvåbingesystem 2. Ett test gjordes enligt principen ”den japanska sjön” vilket innebar lägre lagernivåer i lastbärarna. De problem som uppstod noterades. Resultatet blev att antalet artiklar som plockades i veckosatser minskades vilket skapat underlag för att minska administrationen av tillhörande plocklistor. Plockvagnen har kunnat tas bort vilket frigjort yta vid monteringsavdelningen. Förutsättningar finns att slå samman två plocklistor till en och därmed förenkla arbetet för förrådspersonalen. / This degree project has been performed at Production unit 1 (PV1) at Wexiödisk AB, where hood type washing machines is manufactured. The purpose of this project has been to investigate which inventory control models that could be suitable to control the section’s material supplies. The work has been accomplished in two steps. At first, items unique to products manufactured at PV1 were treated, followed by items common with other products. According models in relevant literature, suggestions were made to how the models could be applied practically. The suggestions was presented to and discussed with the parties concerned who chose Two-bin system 2. A trial was carried out according to the principle of “the Japanese river” which implied lowered inventory levels. The problems that occurred were noted. The result was that the number of items that was weekly picked and distributed was reduced which has created a basis to also reduce the administration of the systems picking lists. The item wagon has been removed which has cleared floor space at the assembly section. Conditions have been created to merge two picking lists into one and thereby simplify the work for the inventory staff.

Notre travail porte sur le problème de bin-packing qui consiste à déterminer le nombre minimum de grands rectangles (bins) nécessaires pour ranger un ensemble de petits rectangles (objets). Ce problème d'optimisation combinatoire est NP-difficile au sens fort. Nous proposons des prétraitements des objets permettant la valorisation des espaces perdus dans les bins et la diminution de la taille du problème à résoudre. Nous proposons une nouvelle méthode d'évaluation de bornes inférieures tenant compte de la possibilité de tourner les objets de 90 degrés. Nous procédons à une résolution approchée du problème grâce à deux nouvelles méthodes : une heuristique et un algorithme de recherche tabou.