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.

Thesis (M.A.)--University of Missouri-Columbia, 2007. / The entire dissertation/thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file (which also appears in the research.pdf); a non-technical general description, or public abstract, appears in the public.pdf file. Title from title screen of research.pdf file (viewed on November 12, 2007) Includes bibliographical references.

Diss. (sammanfattning) Uppsala : Uppsala universitet, 2006. / Härtill 4 uppsatser.

Diss. Univ. Freiburg im Breisgau, 2006.

Proefschrift ter verkrijging van de graad van Doctor--Faculteit der godgeleerdheid--Leiden--Rijksuniversiteit, 1994. / Contient la translittération en caractères latins du texte de la traduction turque des livres de Samuel, et en annexe le fac-sim. du manuscrit, en caractères arabes, de cette trad. Remerciements, résumé et curriculum vitae en néerlandais. Bibliogr. p. 401-404.

Robotic bin picking is the problem of emptying a bin of randomly distributedobjects through a robotic interface. This thesis examines an SVM approach to ex-tract grasping points for a vacuum-type gripper. The SVM is trained on syntheticdata and used to classify the points of a non-synthetic 3D-scanned point cloud aseither graspable or non-graspable. The classified points are then clustered intograspable regions from which the grasping points are extracted. The SVM models and the algorithm as a whole are trained and evaluated againstcubic and cylindrical objects. Separate SVM models are trained for each type ofobject in addition to one model being trained on a dataset containing both typesof objects. It is shown that the performance of the SVM in terms accuracy isdependent on the objects and their geometrical properties. Further, it is shownthat the algorithm is reasonably robust in terms of successfully picking objects,regardless of the scale of the objects.

Content: Recent trends show that cloud computing adoption is continuously increasing in every organization. So, demand for the cloud datacenters tremendously increases over a period, resulting in significantly increased resource utilization of the datacenters. In this thesis work, research was carried out on optimizing the energy consumption by using packing of the virtual machines in the datacenter. The CloudSim simulator was used for evaluating bin-packing algorithms and for practical implementation OpenStack cloud computing environment was chosen as the platform for this research.   Objectives:  In this research, our objectives are as follows <ul type="disc">Perform simulation of algorithms in CloudSim simulator. Estimate and compare the energy consumption of different packing algorithms. Design an OpenStack testbed to implement the Bin packing algorithm.   Methods: We use CloudSim simulator to estimate the energy consumption of the First fit, the First fit decreasing, Best fit and Enhanced best-fit algorithms. Design a heuristic model for implementation in the OpenStack environment for optimizing the energy consumption for the physical machines. Server consolidation and live migration are used for the algorithms design in the OpenStack implementation. Our research also extended to the Nova scheduler functionality in an OpenStack environment.   Results: Most of the case the enhanced best-fit algorithm gives the better results. The results are obtained from the default OpenStack VM placement algorithm as well as from the heuristic algorithm developed in this simulation work. The comparison of results indicates that the total energy consumption of the data center is reduced without affecting potential service level agreements.   Conclusions: The research tells that energy consumption of the physical machines can be optimized without compromising the offered service quality. A Python wrapper was developed to implement this model in the OpenStack environment and minimize the energy consumption of the Physical machine by shutdown the unused physical machines. The results indicate that CPU Utilization does not vary much when live migration of the virtual machine is performed.

Orientador: Kléber Pereira Lanças / Resumo: A eficiência tratória dos tratores equipados com pneus infláveis varia desde próximo de 90%, quando operando em concreto, até menos de 50% para trabalhos em solos soltos ou arenosos. As características trativas de um pneu dependem do tipo e condições do solo, tipo e geometria do pneu, formato das suas garras, carga no eixo e pressão de inflação do pneu. Este trabalho teve como objetivo quantificar e avaliar o contato pneu/solo com ênfase nos métodos para a obtenção da área de contato. A abordagem, visando uma solução analítica para o caso, seria de difícil execução e imprecisa, não fosse o uso da técnica de Elementos Finitos que tem demonstrado versatilidade, flexibilidade e excelentes resultados em casos semelhantes. A área de contato do pneu com o solo é a responsável, em grande parte, pelo desempenho do trator, afetando também características como, a patinagem de pneus e a tração. A abordagem do problema, em primeira instância, considerou um delineamento experimental com parcelas sub-divididas constituído de 48 tratamentos, assim distribuídos: a) Três tipos de pneu: Diagonal, Radial e BPAF (baixa pressão de inflação e alta flutuação). b) Dois níveis de pressões de inflação do pneu: Alta: 165,50 kPa (17 psi, pneus montados no eixo traseiro do trator), "Baixa/correta" para pneus montados no eixo traseiro do trator: 68,95 kPa (7 psi) ou para cada tipo de pneu respectivamente. c) Quatro magnitudes de carga vertical aplicada no pneu: 0,5 kN, 1,0 kN, 1,5 kN e 2,0 kN. d) Dois tipos de solo: amostra de solo agrícola arenoso ( s= 1,4g/cm3) e amostra de solo agrícola argiloso ( s= 1,2g/cm3). Para realização do experimento com os dois tipos e condições de solo, foi utilizado um equipamento para o ensaio estático de pneus individuais, denominado tanque de solo com dispositivo hidráulico de aplicação de carga... (Resumo completo, clicar acesso eletrônico abaixo). / Abstract: The tractive efficiency of tractors equipped with inflated tires varies from nearly 90%, whem working on concrete, to less than 50% when working on loose soil or sand. The tractive characteristics of a tire depend on soil conditions, tire geometry and lugs, axle load and tire pressure. This wok aimed to estimate the contact tire/soil with emphasis on methods of determination of contact area. The approach using an analytical solution for this case wold of hard execution and inaccurate, but the use of the finite element solutions has been shown versatile, flexible and with exelents results in similar cases. The contact area of tire with the soil is the major responsible by the performance, affected also characteristics like sliding and traction. The problem was considered like an experimental design with 48 treatments being: a) Tree kinds of the tires, bias, radial and B.P.A.F. (low inflation pression and high flutuation). b) Two levels of inflation pressure of the tire, high: 165,50 kPa for each kind of tire, respectively. c) Two types of soil: sample of agricultural sandy soil ( s= 1,4g/cm3) and sample of agricultural clay soil ( s= 1,2g/cm3). To realize the experiment with two soil types and conditions were used an equipment for static test of individual tires named soil bin with hydraulic device to apply the loads. For each test the tire/soil contact area was determinate using a method of digital picture area integration. The data were used to elaborate mathematical models that expressed the relation ships among loads and strains using the Finite Element Method. The tests proved that relationship to determine the contact areas for bias tires gained the worst results once the B.P.A.F. tires showed the bests one. The Radial tires showed always intermediates results compared with the other two types. The pressure cells installed into the soil bin always showed... (Complete abstract click electronic access below). / Doutor

Magíster en Gestión de Operaciones. Ingeniero Civil Industrial / La educación en las zonas rurales del país presenta ineficiencias respecto a la distribución geográfica de las escuelas, lo que genera ocupación ociosa muy elevada y dificultad de acceso para los alumnos que deben asistir a ellas. La razón principal de este problema es la inexistencia de una planificación al momento de diseñar la forma en que se distribuirá la infraestructura educacional en estas zonas. Esto motiva a la generación de propuestas que permitan mejorar la calidad de vida de los estudiantes, disminuir la brecha de desigualdad en la conectividad y realizar un uso apropiado y eficiente de los recursos con los que se cuenta. Para este problema, se utilizó la realidad de las escuelas rurales de la Tercera Región de Atacama, que cuenta con 44 establecimientos en esta categoría funcionando al 67% de su capacidad, en los cuales asisten 2.761 alumnos que en promedio viajan 22,3 km para estudiar. Este trabajo se desarrolló en dos etapas. La primera, implica un modelo de programación lineal mixta para simular y obtener una estimación de los costos operacionales y de transporte incurridos por administradores y alumnos. La segunda etapa contempla una serie de modelos de programación lineal entera y mixta, para optimizar la localización de los establecimientos educacionales, donde se restringía además la distancia máxima que podía recorrer un estudiante en 50 km. Los resultados de la optimización indicaron una reducción del 35% en el gasto global. Además, los beneficios para los estudiantes son significativos, pues reducen las distancias recorridas en 71% y disminuyen los aislamientos geográficos. Para concretar los resultados obtenidos con el modelo se deben incorporar 3 nuevos establecimientos, requiriendo inversión en infraestructura, pero en total funcionan solo 31 escuelas, por lo que los costos operacionales son reducidos en 27%, llegando a una inversión total de $1.424 millones. Dada la distribución geográfica de las zonas rurales en las regiones extremas del país, se ve que es pertinente aumentar la distancia máxima permitida, complementándose con el desarrollo de un sistema de transporte, el cual se realizó con programación lineal mixta con un algoritmo iterativo de generación de restricciones, que se crean a partir de la resolución del Bin Packing Problem, que determina el número de vehículos que se requieren para un conjunto de paraderos y que evita la generación de rutas que no pasen por los establecimientos. En esta nueva instancia se requiere el funcionamiento de 37 escuelas, de las cuales 8 son nuevas. Los costos operacionales son reducidos 23% con respecto a la situación actual, sin embargo, se requiere una fuerte inversión en transporte, la que alcanza los $743 millones. Esto sumado a las operaciones e infraestructura contempla una inversión anual total de $2.157 millones, con lo que se logra una reducción de 2% respecto a los costos totales actuales.

Made available in DSpace on 2015-03-03T15:16:25Z (GMT). No. of bitstreams: 1 SauloCM_TESE.pdf: 2950789 bytes, checksum: d10187bfbd3f161c4305c3a9fa050100 (MD5) Previous issue date: 2011-08-18 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / Sessenta e cinco sistemas bin?rios eclipsantes, identificados nos objetivos da miss?o espacial CoRoT, foram selecionados para a an?lise. Destes, cinquenta e nove curvas de luz fotom?tricas que foram analisadas e processadas neste estudo s?o curvas crom?ticas (simultaneamente observadas nos tr?s filtros azul, verde e vermelho do sat?lite), fornecendo uma importante informa??o que ajuda a distinguir falsos positivos e genu?nos sistemas bin?rios eclipsantes. Neste sentido, este estudo fornece um cat?logo de sistemas bin?rios eclipsantes com suas respectivas solu??es fotom?tricas, baseadas nas curvas de luz CoRoT. Os sistemas selecionados incluem ambos, sistemas de n?o contato e de contato para os quais s?o apresentados uma variedade de par?metros f?sicos, incluindo per?odo orbital, o ?ngulo de inclina??o da orbita, raz?o de temperaturas, raz?o de raios e raz?o de luminosidades. Em adicional, e poss?vel estimar, aproximadamente, os par?metros absolutos de tais sistemas tomando como refer?ncia os valores t?picos a partir dos tipos espectrais conhecidos. O trabalho contribui para um aumento significativo no n?mero e na diversidade de sistemas bin?rios eclipsantes estudados a partir da base de dados CoRoT