Orientador: Marcus Vinicius S. Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-21T10:33:41Z (GMT). No. of bitstreams: 1 Longo_HumbertoJose_M.pdf: 2296998 bytes, checksum: cb6cef9a3b19187ee26dc91e8fe15b17 (MD5) Previous issue date: 1995 / Resumo: Esta dissertação tem como tema central o Problema de Recobrimento de um Conjunto (SCP - Set Covering Problem). O objetivo principal é a proposta de uma nova abordagem para sua resolução, mais precisamente, este objetivo visa o desenvolvimento de um método heurístico, multi-algorítmico, baseado no paradigma de Times Assíncronos. Um segundo objetivo desta dissertação, e de grande importância na funda­mentação do método ora proposto, é um estudo das principais características estruturais do problema; de sua formulação como um problema de programação linear inteira 0-1 e dos principais métodos computacionais (heurísticos e exatos) atualmente disponíveis para sua resolução. Times Assíncronos são organizações de software que visam a interação efici­ente entre vários algoritmos, para a resolução de problemas adequados à aborda­gem multi-algorítmica. A arquitetura proposta utiliza métodos aproximados para a resolução do SCP e do dual da relaxação linear do mesmo. Esta abordagem primal-dual permite garantir que a melhor solução encontrada esteja a um certo percentual da solução ótima, ou mesmo, eventualmente, provar a otimalidade da solução. Segundo este enfoque, os principais componentes da arquitetura proposta são algoritmos gulosos e de consenso, procedimentos de busca tabu, métodos de otimização por subgradientes e geradores de planos de corte. Os principais métodos exatos para a resolução do SCP são baseados em metodologias enumerativas. A maioria desses métodos combina ao esquema de enumeração diversas das técnicas heurísticas utilizadas na arquitetura aqui proposta. Contudo, esses métodos apresentam desempenho insatisfatório para algu­mas classes de instâncias, por não obterem boas soluções em um limite razoável de tempo. A arquitetura proposta foi aplicada a instâncias dessas classes de difícil reso­lução. Os resultados obtidos mostraram que é possível alcançar, com um esforço computacional aceitável, resultados no mínimo comparáveis aos dos melhores algoritmos para o SCP / Abstract: The development of an Asynchronous Team Method for heuristic resolution of the Set Covering Problem (SCP) is the main focus of this dissertation. Asynch­ronous Teams are software organizations that aim to efficient interaction among several algorithms for the resolution of problems that fit in a multi-algorithm approach. Another goal of this work is an extensive study of the SCP which covers: the SCP structures its formulation as a 0-1 ILP; and the description of the main heuristic and exact methods currently available for its resolution. This study is most1y required since we are concerned with the development of a multi-algorithm method. The resulting software architecture makes use of approximate algorithms for the resolution of the se P and its continuous relaxation dual. This primal-dual approach guarantees the best found solution to be at a certain percentage of the optimal solution and, eventually, proves the solution optimality. The main components of the proposed architecture are greedy and consensus algorithms, tabu search procedures, subgradient methods and cutting plane generators. The main exact methods for the se P resolution are based on enumerative methodologies. Most of these methods deploys many of the heuristic technics used in the proposed architecture to the enumeration scheme. However, these methods have a poor performance in some instance classes, because they do not obtain good solutions in a reasonable time limit. The proposed architecture was applied to particularly hard instances. The obtained results show that it is possible to reach solutions, at an acceptable computational effort, that are at least comparable to the ones obtained by the best algorithms for the SCP / Mestrado / Mestre em Ciência da Computação

Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-22T03:48:35Z (GMT). No. of bitstreams: 1 Berretta_ReginaEsther_D.pdf: 9864278 bytes, checksum: ba475c4277cadec8953864df9f0375a7 (MD5) Previous issue date: 1997 / Resumo: Esse trabalho trata do problema dimensionamento de lotes em sistemas de produção multiestágio, que consiste na determinação das quantidades a serem produzidas em diferentes períodos, de tal modo que a demanda seja atendida. Por ser um sistema multiestágio de produção, os produtos dependem da compra e/ou produção de certos componentes. O modelo apresentado utiliza o conceito de estoque de escalão e considera custos de produção, estoque e preparação. Para retratar o consumo dos recursos, são incluídos tempos de preparação e produção. Além disso, supõe-se que o lead time de cada item seja diferente de zero. Para a resolução deste problema, foram desenvolvidos métodos heurísticos com o propósito de obter planos factíveis e buscar soluções com menor custo. Com o objetivo de melhorar o desempenho das heurísticas propostas, as técnicas meta- heurísticas Busca Tabu e Simulated Annealing foram incorporadas. Os resultados dos testes computacionais são comparados com a solução ótima em instâncias com até 60 variáveis binárias e para instâncias de maior porte, os resultados são comparados com um limitante inferior obtido pela aplicação de Relaxação Lagrangeana ao problema / Abstract: This thesis deals with the lotsizing problem in multistage production systems. The problem basically consists in determining the quantities to be produced in different periods of time such that a forecast demand would be attained. Since the production system is of a multistage type, the available items would be either produced or bought to satisfy the needs of the plan. The model we present uses the concept of echelon stock and considers production, stock and preparation costs. To model the aspects of consumption of resources, preparation and production times are also included in the mode!. In addition, the lead time of each item is supposed to be different from zero. In order to give feasible solutions for this problem we have developed heuristic methods which also lead to low cost solutions. In order to improve the performance of the developed heuristics, search techniques based on metaheuristics like "Tabu Search" and "Simulated Annealing" were introduced in a second stage. The results from the computational tests were compared with the optimal solution when the instances had up to 60 binary variables. For instances of a larger size the results were compared with a lower bound which was obtained by Lagrangean Relaxation of the problem's mixed-integer programming formulation / Doutorado / Doutor em Engenharia Elétrica

Orientadores: Pedro Sergio de Souza, Marcus Vinicius Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-22T21:33:18Z (GMT). No. of bitstreams: 1 Haddad_ElaineGaspareto_M.pdf: 1752527 bytes, checksum: 6ecf36f9a07b62f0718f185c0fd4ca43 (MD5) Previous issue date: 1997 / Resumo: Este trabalho aborda o problema de seqüenciamento de tarefas conhecido como Job Shop Scheduling Problem (JSP). O objetivo aqui é mostrar a adequação de uma técnica conhecida como Times Assíncronos (A-Teams), para resolver este problema de otimização combinatória, que é bastante freqüente em ambientes industriais. Esta abordagem tem sido aplicada com sucesso na resolução de outros problemas, como o Traveling Salesman Problem, o Flow-Shop Problem e até mesmo o próprio Job Shop Problem sob uma abordagem de heurísticas de construção. Esta técnica está baseada na cooperação de algoritmos heurísticos no sentido de obter soluções, possivelmente, melhores que aquelas obtidas quando os mesmos algoritmos são executados isoladamente. Neste trabalho, o enfoque é dado a heurísticas de melhoria. Outros tipos de algorit­mos foram desenvolvidos para compor os A-Teams. Estes A-Teams desenvolvidos foram acoplados a um outro já existente, baseado em heurísticas de construção. Algumas instâncias de JSP foram testadas e os resultados obtidos atestam a adequação desta técnica para a resolução deste problema. / Abstract: This work treats the sequencing of tasks problem known as Job Shop Scheduling Problem. The goal here is to show the adequability of a technique known as Assynchronous Teams (A-Teams) to solve this optimization problem which is used in industrial environments. This approach has been applied successfully in the solving of other problems such as the Traveling Salesman Problem, Flow Shop Problem and the Job Shop Problem itself using construction heuristics algorithms. This technique is based on the cooperation of some heuristics algorithms in order to obtain solutions, possibly better then ones obtained when same algorithms are working alone. In this work, the focus is on the development of improvement heuristics algorithms. Another type of algorithms were also developed to form the A-Teams. These A-Teams developed were joined to another one, based in construction heuristics. Some instances of the JSP were tested and the results obtained show the adequability oí this technique to solve this problem. / Mestrado / Mestre em Ciência da Computação

Orientador: Paulo Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-22T22:52:02Z (GMT). No. of bitstreams: 1 Pureza_VitoriaM.M_D.pdf: 9869285 bytes, checksum: 3d30f5f94e19c47fb41416cb14190a97 (MD5) Previous issue date: 1996 / Resumo: A Busca Tabu é um procedimento heurístico de orientação da busca com vistas à obtenção de boas soluções em problemas de dificil tratamento. Fundamentalmente, ela é caracterizada por mecanismos que promovem a superação da otimalidade local. Esses mecanismos geralmente tomam a forma de parâmetros que impõem restrições à seleção de movimentos. Como a calibragem desses elementos restritivos tem um impacto fundamental no desempenho do algoritmo, algumas implementações utilizam estratégias que provocam alterações sistemáticas nos valores de determinados parâmetros. Estas estratégias procuram intensificar a exploração de regiões promissoras e o abandono de regiões onde possibilidades de melhoria parecem mínimas. As alterações nos valores dos parâmetros são normalmente acionadas por fases de busca caracterizadas pela ausência de movimentos de atualização da solução incumbente. O objetivo principal deste trabalho é o de propor uma nova abordagem adaptativa de metaheurísticas Tabu. A abordagem HTA, aqui considerada, propõe que a alteração de parâmetros seja determinada a partir da identificação de padrões da trajetória de busca recentemente traçada. Estes padrões fornecem indicações, ainda que limitadas, acerca da topologia do espaço de soluções. Para cada padrão, são aplicadas perturbações nos valores de parâmetros tabu selecionados, como forma de adaptar a busca às diferentes condições encontradas. A abordagem HTA foi desenvolvida a partir de extensos experimentos com o Problema do Caixeiro Viajante Simétrico e Euclideano (PCV). Testes envolveram 12 instâncias clássicas e verificaram ganhos significativos em relação à versão não-adaptativa, mesmo sob condições operacionais estressantes impostas por parâmetros mantidos fora de controle. A seguir, a mesma abordagem foi aplicada ao Problema de Roteamento de Veículos (PRV). Neste trabalho, apresentamos os resultados obtidos com 14 instâncias clássicas caracterizadas por diferentes restrições. Os resultados foram comparados com os de três algoritmos altamente competitivos e indicaram que HTA produz soluções de qualidade comparável aos demais. São também apresentados os resultados obtidos com uma implementação adaptativa HTA para o Problema de Agrupamento Capacitado (PAC). Os resultados, mais uma vez, sugerem que a introdução de mecanismos adaptativos baseados em padrões da trajetória da busca é uma estratégia robusta e promissora / Abstract: Tabu Search (TS) is a general heuristic procedure for guiding search to obtain good solutions in complex solution spaces. Fundamentally, it is characterized by mechanisms that allow the exploration of the solution space beyond local optimality. These mechanisms are generally implemented by means of parameters which impose restrictions to move selection. Since the calibration of such restrictive elements has a major impact on the algorithm's performance, some implementations use strategies for altering the values of these parameters whenever non-improving search phases are verified. Essentially, these strategies seek to intensify the exploration of promising regions of the solution space, and to abandon the search in regions where improvement possibilities seem to be minimal. The main purpose ofthis work is to propose a new adaptive Tabu metaheuristic approach. The HTA approach, considered here, assumes that the alteration of the parameters values should be defined first by identifying specific pattems in the search trajectory recently described. These pattems provide indications of the solution space topology. For each pattem, perturbation on the values of selected tabu parameters is applied, as means to adapt the search to the different conditions found. The HTA approach was developed from extensive experiments with the Symmetric and Euclidean Traveling Salesman Problem (TSP). Tests involved 12 benchmark instances and verified improvements with respect to a non-adaptive implementation, even under stressing operational conditions provided by free-Junning parameters. HTA was also applied to the Vehicle Routing Problem (VRP). We present the results obtained for 14 benchmark instances characterized by different restrictions. Our adaptive implementation is compared to three highly competitive algorithms. The results indicate that HTA is able to provide solution quality levels comparable to the other algorithms. We also present the results provided by an HTA implementation for the Capacitated Clustering Problem (CCP). They also suggest that introducing adaptive mechanisms based on the pattems of search trajectories is a robust and promising strategy / Doutorado / Doutor em Engenharia Elétrica

Orientador: Marcus Vinicius Soledade Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T14:07:59Z (GMT). No. of bitstreams: 1 Farias_MariadoSocorroAlvesTaumaturgode_M.pdf: 3829944 bytes, checksum: 99a0235b38672fc180f6ff5dbef49c96 (MD5) Previous issue date: 1997 / Resumo: Deteção de contornos é uma importante tarefa em processamento de imagens. Desempenha um papel crucial em reconhecimento de padrões e sistemas de tratamento de imagens, o que explica o grande número de trabalhos que têm sido aplicados a detectar contornos de regiões em imagens obtidas em diferentes contextos. Apesar disto, a detecção automática de contornos é ainda um grande desafio para a tecnologia de hoje. Uma maneira de atacar o problema é através da definição de uma função de custo capaz de capturar o conceito de um contorno ou borda. Neste trabalho é usada a função de custo proposta por Tan, Gelfand e Delp, que é uma combinação linear de fatores tais como continuidade de uma linha de borda, dissimilaridade entre regiões limitadas por bordas e espessura de bordas. Esta função é usada para propor um novo algoritmo para minimização de custos. Trabalhos anteriores, que minimizam a mesma função de custos, foram propostos por Tan et ai., que realizou experiências com algoritmos baseados em busca local e em Simulated Annealing, além de Bhandarkar et ai., que desenvolveu um algoritmo genético para deteção'de contornos. O algoritmo aqui apresentado é baseado na busca em vizinhanças variáveis, proposta por Hansen e Mladenovic, que é uma busca local que inteligentemente trata com diferentes vizinhanças. A experiência computacional mostrou resultados favoráveis à abordagem proposta em relação às anteriores, no que diz respeito ao tempo de, CPU e aos valores encontrados para a função de custo. / Abstract: Edge detection is an important task in image processing. It plays a crucial role in object recognition and image understanding systems, what explains the great deal of research that has been dedicated to detect region edges in images obtained from different contexts. Nevertheless, the automatic edge detection is still a great challenge to today's technology. One way to tackle this problem is by the definition of a cost function able to capture the concept of an edge. We use the cost function proposed by TanJ Gelfand and Delp, which is a linear combination of factors such as continuity of an edge, region dissimilarity and edge thickness, to propose a new algorithm for the minization of the resulting function. Previous works that minimize equivalent cost function has been proposed by Tan et al., who experimented with local search and Simulated Annealing algorithms, and Bhandarkar et al., who developed a Genetic Algorithm to accomplish this task. Our algorithm is based on Hansen and Mladenovíc's Variable Neighborhood Search (VNS), which is a local search capable of playing smartly with different neighborhoods. The computational experience showed that our algorithm compares favorably with the previous ones with respect to CPU time and minimum cost function value found. / Mestrado / Mestre em Ciência da Computação

Orientador: Paulo Morelato França / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-26T23:25:56Z (GMT). No. of bitstreams: 1 Milanez_EduardoMedeiros_M.pdf: 3118600 bytes, checksum: 0d8f4ba53c2cf46dcb543bd1b00ae12d (MD5) Previous issue date: 2000 / Resumo: Uma das etapas da cadeia de fornecimento de produtos derivados de aves como frangos e perus diz respeito ao processo de coleta dos lotes no campo e seu transporte para o abatedouro. Durante este processo, as aves são submetidas a condições extremas de desgaste fisico. Para se reduzir os custos referentes às perdas de peso decorrentes do estresse é necessário minimizar o tempo médio de espera para abate. A programação do serviço de coleta deve, além de perseguir tal objetivo, atender condicionantes próprios do processo tais como coleta ininterrupta das cargas, capacidade de abate das linhas de pendura, estoques de segurança na plataforma de desembarque e tamanho de frota disponível para o transporte. As restrições do problema e sua natureza combinatorial dificultam sua solução. Os programadores da coleta geralmente dispõem de simuladores determinísticos, ferramentas de simulação visual interativa, que os auxiliam na determinação dos horários iniciais de coleta dos lotes que constam dos planos diários de abate. Para garantir soluções de estoque mínimo de segurança em tempo hábil foi desenvolvido uma heurística de construção que implementa uma política de sincronização dos fluxos de chegada e abate. Este procedimento heurístico, objeto central deste trabalho, foi posteriormente incorporado a um simulador atualmente em uso em diversas plantas. A eficácia da heurística na geração de soluções de estoque mínimo é ilustrada através de um estudo de caso. A comparação é feita com soluções otimizadas, obtidas através de programação matemática. Para isto, um modelo do tipo MILP é implementado / Abstract: One of the crucial processes of the poultry industry supply chain involves flocks catching and their transportation to the slaughter house. During the process the birds undergo extreme physical stress. In arder to reduce the costs that relate to stress induced weight loss it is necessary to minimize the average waiting time from arrival to hanging. The catching schedule of the flocks must pursue that goal. It also must take into account specific process constraints such as continuous trucks loading, the hanging lines capacities, the safety stocks requirements and the truck fleet size. These constraints and the combinatorial nature of the problem make it a hard one to solve. The catching schedulers usually make use of deterministic simulators. These interactive visual simulation tools allow them to determine the catching start time for alI flocks in the daily slaughtering plano A constructive heuristic was developed to find a minimum stock solution in a reasonable time. It enforces a sincronization policy for the arrival and hanging birds flows. This procedure was later embedded in a simulator that is currently in use in several plants. The efficacy on generating minimum stock solutions is shown in a case study. Heuristic solutions for small instances were compared to optimized solutions obtained by MILP models / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador: Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T05:53:35Z (GMT). No. of bitstreams: 1 Prado_DanielFernandoMechlin_M.pdf: 451492 bytes, checksum: 0350938f30a018718f3b59654e155a93 (MD5) Previous issue date: 2007 / Resumo: Localização de facilidades é uma das atividades da área de logística que envolve decisões do número, localização e tamanho das facilidades a serem usadas. A localização de facilidades é uma questão central no planejamento estratégico de empresas públicas e privadas e está associada à variação da população em uma região, capital de investimento e estimativa de clientes que podem ser servidos. Este trabalho aborda o problema de localização de facilidades com restrições de capacidade e fonte única para atender a demanda de clientes. A fonte única impõe que um cliente seja atendido por uma única facilidade, e o objetivo é minimizar os custos de instalação e atendimento dos clientes. Este problema tem diversas aplicações, incluindo a localização de concentradores em redes de telecomunicações. Trata-se de um problema complexo de otimização combinatória, em que métodos exatos não produzem uma solução ótima em tempo viável, e portanto o uso de métodos heurísticos é pertinente. O objetivo deste trabalho é o desenvolvimento e implementação de um algoritmo de busca tabu para o problema, e comparação de seu desempenho com outros métodos apresentados na literatura. Palavras-chave: Localização de Facilidades, Otimização Combinatória, Heurística, Busca Tabu / Abstract: Facility location is a logistic problem that involves the decision on the number, location and capacity of facilities to be opened. Facility location is an important area in the strategic planning of public and private companies and is associated with population changes, money availability for investment and the estimation of the number of customers to be served. This work addresses on single source capacitated facility location problem. Single source imposes that each customer must be assigned to only one facility, and the objective is to minimize the installation and transportation costs. This problem has several applications, including the network concentrator location problem. It is a complex combinatorial optimization problem, which cannot be solved by exact methods in small computational times; therefore, heuristics methods are indicated. The objective of this thesis is the development and implementation of a tabu search algorithm for the problem and a comparative analysis with other methods available in the literature. Keywords: Facility location, Combinatorial Optimization, Heuristic, Tabu Search / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientadores : Fernando Antonio Campos Gomide, Rodrigo Almeida Gonçalves / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T10:28:52Z (GMT). No. of bitstreams: 1 Molck_PauloHenriqueRodrigues_M.pdf: 1447009 bytes, checksum: b4ae484a2d72fdc36fef64a246a78881 (MD5) Previous issue date: 2002 / Mestrado

Orientador : Vinicius Amaral Armentano / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T14:09:48Z (GMT). No. of bitstreams: 1 Christofoletti_LucianoMarcelo_M.pdf: 330664 bytes, checksum: 72ba00623f07b0d6a740c86049e839b1 (MD5) Previous issue date: 2002 / Mestrado

Orientador : Carlos Alberto de Castro Junior / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T15:25:32Z (GMT). No. of bitstreams: 1 Abrantes_HederDelciodaCosta_M.pdf: 5158849 bytes, checksum: 5e129947214f9c7ddedb6b3e5fcecad6 (MD5) Previous issue date: 2000 / Resumo: Este trabalho apresenta um método simples e eficiente para eliminar ramos sobrecarregados em sistemas elétricos de potência. Redespacho de geração e corte de carga são usados como controles. As ações de controle são definidas através de métodos de programação não linear. A idéia de otimização local adaptativa é usada para os controles de redespacho de geração. Corte de carga é usado como último recurso, ou seja, quando nenhum gerador pode ser redespachado. Heurísticas foram adicionadas de forma a aumentar a velocidade do processo computacional bem como para incluir aspectos práticos relacionados à operação de sistemas de potência. Foi desenvolvido um procedimento específico para resolver casos críticos, onde as ações de controle extremo são definidas. A idéia é sempre a de manter o novo ponto de operação o mais próximo possível do original. O método pode ser útil em estudos de planejamento de expansão, análise de segurança e avaliação de confiabilidade de sistemas de potência. Algumas simulações foram realizadas utilizando sistemas diversos com o objetivo de mostrar a eficiência do método proposto / Abstract: In this work a simple and efficient method for eliminating branch overloads in power systems is presented. Generation rescheduling (GR) and load shedding (L8) are used as controls. Control actions are defined through the use of non linear programming. The idea of adaptative local optimization is used for the definition of GR. L8 is used as a last resort, that is, when further GR is no longer possible. Heuristics are added in order to speed up the computation process and to include practical aspects of power systems operation into it. A special procedure is carried out in case of critical situations, where emergency control actions are defined. The idea is to keep the new operating point as close as possible to the original one. The method can be a helpful tool for operation planning studies, security analysis and reliability evaluation of power systems. 8imulations have been carried out for small test to large real life systems in order to show the effectiveness of the proposed method / Mestrado / Energia Eletrica / Mestre em Engenharia Elétrica