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: 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

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: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T14:25:03Z (GMT). No. of bitstreams: 1 Nascimento_JulianaMartinsdo_M.pdf: 4967741 bytes, checksum: 20ceacaab689704941f1f9d3ec41695a (MD5) Previous issue date: 2002 / Resumo: Problemas de otimização combinatória são classificados na grande maioria das vezes como NP-difíceis. Para estes problemas, não são conhecidos algoritmos polinomiais capazes de resolvê-los. Logo, é necessário o desenvolvimento de estratégias eficientes para tratá-los. O desenvolvimento de técnicas híbridas para a resolução destes problemas tem por objetivo valorizar os pontos fortes dos métodos que estão sendo empregados, para, desta forma, compensar os pontos mais fracos, criando um procedimento de qualidade superior. Este trabalho propõe um método híbrido que integra técnicas de Programação por Restrições com metaheurísticas de Busca Tabu para atacar o problema de escalonamento de atividades na produção de um campo petrolífero. Como não há resultados anteriores para serem comparados com os resultados obtidos para as instâncias consideradas neste trabalho, modelos de programação matemática foram utilizados para a obtenção de limitantes duais para a solução do problema. Além disso, para determinar quão robusta é a técnica proposta, uma análise de sensibilidade foi realizada sobre as instâncias consideradas / Abstract: Combinatorial optimization problems are generally NP-hard. As it is not known polinomial time algorithms to solve them, it is necessary to develop efficient strategies to treat them. The aim in developing hybrid techniques to solve combinatorial optimization problems is to strength the good features of the methods that are being combined to compensate for their weakness. In this paper, we propose a hybrid method that combines Constraint Programming techniques and Tabu Search metaheuristics to schedule the activities involved in the production process of an oil field. As there are no previous results to estabilish a comparision with the results obtained with the instances considered in this work, bounds were determined using mathematical programming models. Finally, to estabilish the robusteness of proposed method, a sensibility analysis was performed over the considered instances / Mestrado / Mestre em Ciência da Computação

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado profissional) - Universidade Estadual de Campinas. Instituto de Computação / Made available in DSpace on 2018-08-04T04:16:19Z (GMT). No. of bitstreams: 1 Ganhoto_MarcoAlves_M.pdf: 1370660 bytes, checksum: 851eb09fb46a8ed3bfb7990592eb9a41 (MD5) Previous issue date: 2004 / Resumo: Neste trabalho, investigamos abordagens para problemas de roteamento, que têm como finalidade encontrar um melhor conjunto de rotas para que veículos possam transportar mercadorias a clientes geograficamente dispersos, respeitando certas restrições, como por exemplo, a de capacidade de carga dos veículos. Para isto, além de pesquisas em diversas fontes de informações, desenvolvemos um aplicativo para auxiliar no entendimento dos algoritmos, na ilustração do texto e na realização de experimentos. A partir de observações feitas durante as execuções do aplicativo, experimentamos combinações de critérios de seleção de localidades, utilizando tais combinações durante a realização dos movimentos de intercâmbio de vértices entre rotas de uma conhecida estratégia, a Metaheurística Busca Tabu. Foram combinados critérios baseados em distâncias com critérios baseados em ângulos, para compor algoritmos que foram testados com instâncias clássicas utilizadas por diversos pesquisadores. Os resultados obtidos foram apresentados juntamente com os de outras estratégias, fornecendo valores iguais ao melhor valor conhecido para duas instâncias, e valores intermediários para as outras cinco instâncias utilizadas nos testes / In this work, we examine some approaches for vehicle routing problems, to find a best set of routes to enable companies for delivery goods or commodities to customers, respecting some constraints, such as vehicles loading capacity. To this purpose, besides researching available information sources, we have developed a software to help us to understand the algorithms issues, for enriching the text with illustrations, and for effectiving some experiments concerning to previously selected approaches. From the analysis made during running software process, we decided to arrange chosen vertices criterias, using these arrangements in the vertices interchanging movements between routes of an already know method, the Tabu Search Metaheuristic. More precisely, we have combined distances and angles criteria, to implement algorithms on which it were tested using some classical instances considered by several researchers. The obtained results are presented with those selected approaches, and it provided us two equals values to the best known solution, and five intermediate values amoung to the others used on these experiments / Mestrado / Engenharia de Software / Mestre Profissional em Computação

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2015-11-12T10:42:09Z No. of bitstreams: 1 texto completo.pdf: 1645681 bytes, checksum: eede2be161a471450d5d998d3d3f3ffe (MD5) / Made available in DSpace on 2015-11-12T10:42:09Z (GMT). No. of bitstreams: 1 texto completo.pdf: 1645681 bytes, checksum: eede2be161a471450d5d998d3d3f3ffe (MD5) Previous issue date: 2015-02-25 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A otimização de percursos é de grande interesse para empresas que fornecem serviços relacionados com transporte, seja de pessoas ou de mercadorias, visto que podem levar a uma diminuição do tempo e do custo necessário para prestar um serviço e, consequentemente, elevar a lucratividade. Neste trabalho é abordado o Problema do Caixeiro Viajante com Seleção de Hotéis (PCVSH), uma variante do clássico Pro- blema do Caixeiro Viajante (PCV). No PCVSH, existe um limite de tempo imposto a uma jornada diária de trabalho. Desta forma, considerando que há um conjunto de clientes que precisam ser atendidos, há casos em que não é possível atender a todos em um mesmo dia. Levando em consideração esta restrição, é necessário es- colher hotéis, dentre um conjunto previamente fornecido, para que seja realizada a parada entre duas jornadas diárias consecutivas. O objetivo desta dissertação é apresentar, discutir e tratar o Problema do Caixeiro Viajante com Seleção de Hotéis aplicando heurísticas e comparando os resultados obtidos com aqueles disponíveis na literatura. Foram propostas três heurísticas, sendo duas baseadas em Algoritmo Memético (AM) e outra baseada na metaheurística Iterated Greedy (IG), além de um modelo de Programação Linear Inteira alternativo ao existente na literatura. / The optimization of routes is of great interest to companies that provide services related to transportation, being of peoples or goods, as they can lead to a decrease in the time and cost required to provide a service, and consequently to a raise in profitability. In this work we deal with the Travelling Salesperson Problem with Hotel Selection (PCVSH), a variant of the classic Travelling Salesperson Problem (TSP). In PCVSH there is a limit of time imposed to a daily journey of work. Thus, considering that there is a set of customers that need to be visit, there are cases in which one cannot visit all in one day. Considering this restriction, one you must choose hotels, among a previously given set, where a break will take place between two working daily journey. The aim of this work is to present, discuss and solve the Travelling Salesperson Problem with Hotel Selection applying heuristics and comparing the results with those available in the literature. Three heuristics, two based on memetic algorithm (AM) and another based on the metaheuristic Iterated Greedy (IG), and an alternative Integer Linear Programming model to the existing on the literature were proposed.

Orientador: Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-24T03:31:34Z (GMT). No. of bitstreams: 1 Cavalcante_CristinaCeliaBarros_M.pdf: 2965474 bytes, checksum: 985e21c3520bb2270df4c0dda2caeaf9 (MD5) Previous issue date: 1998 / Resumo: Esta dissertação estuda o problema de escalonamento com restrição de mão-de-obra (SPLC) e apresenta algumas estratégias para obtenção de limitantes inferiores e de limitantes superiores para este problema NP-difícil. No que diz respeito à obtenção de limitantes inferiores para o SPLC, são apresentadas duas formulações de programação inteira e discutidos os limitantes inferiores obtidos com a relaxação linear de cada uma delas. Um algoritmo de branch-and-bound específico para o SPLC é também implementado na tentativa de se obter soluções exatas para este problema. Finalmente, é introduzida uma extensão, baseada em uma formulação de programação inteira, para um método existente na literatura para o cálculo de limitantes inferiores para problemas de escalonamento com restrição de recursos. Com relação à obtenção de limitantes superiores para o SPLC, são propostas e implementadas quatro estratégias heurísticas seqüenciais (heurística baseada em regras de prioridade, heurística baseada em classes de escalonamento, heurística baseada em programação linear e um algoritmo seqüencial de busca tabu) e duas estratégias paralelas e assíncronas (A-Team e um algoritmo paralelo de busca tabu). Um conjunto de instâncias de teste para o SPLC é gerado e disponibilizado como benchmark para ser usado na avaliação da qualidade dos limitantes inferiores e superiores obtidos neste trabalho e em outros disponíveis na literatura. Embora pouco sucesso tenha sido obtido com as estratégias propostas para obtenção de limitantes inferiores, no caso dos limitantes superiores, as estratégias paralelas e assíncronas propostas e implementadas neste trabalho mostraram-se altamente adequadas à obtenção de soluções de boa qualidade para o SPLC e são, atualmente, responsáveis pelas melhores soluções conhecidas para este problema. / Abstract: This dissertation studies the scheduling problem under labour constraints (SPLC) and presents some strategies to obtain lower and upper bounds for this NP-hard problem. Concerning the lower bounds, two integer programming formulations are presented and the lower bounds associated with their linear relaxations are discussed. A branch-and-bound algorithm is also implemented as an essay to provide exact solutions for this problem. Finally, integer programming is used as a basis to extend a procedure reported in the literature to compute lower bounds for the resourte constrained project scheduling problem. In order to get upper bounds for SPLC, four heuristic approaches (priority rule based heuristic, schedule set based heuristic, linear programming based heuristic and sequential tabu search algorithm) and two parallel strategies (A - Team and parallel tabu search algorithm) are proposed and implemented. A benchmark instance data set for SPLC is generated to be used in the evaluation of the lower and upper bounds obtained in this dissertation and in other works available in the SPLC literature. Although little success has been achieved with respect to the lower bounds, in the case of upper bounds, the parallel strategies proposed in this work have shown the applicability of such techniques in providing high quality solutions for SPLC, and are, presently, responsible for the best known solutions for this problem. / Mestrado / Mestre em Ciência da Computação

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-24T07:54:32Z (GMT). No. of bitstreams: 1 Mazzini_Renata_D.pdf: 12936662 bytes, checksum: 581f180b73d247423b83bd197041667d (MD5) Previous issue date: 1998 / Resumo: Neste trabalho estuda-se a aplicação de meta-heurísticas populacionais em problemas de programação da produção. O problema abordado consiste da minimização do atraso total na programação de tarefas em máquinas paralelas idênticas onde se consideram tempos de preparação de máquina dependentes da seqüência de processamento e datas de entregas distintas. São apresentadas duas implementações de Algoritmos Genéticos e quatro implementações de Busca por Espalhamento. Testes computacionais extensos foram realizados com essas implementações sobre um conjunto de problemas gerados aleatoriamente. Os resultados obtidos possibilitaram a realização de análises comparativas do desempenho e do comportamento das versões implementadas dessas duas meta-heurísticas quando aplicadas ao problema de programação da produção estudado / Abstract: The application of population-based meta-heuristics on scheduling problems is studied in this work. The problem which is addressed is the minimization of total tardiness when jobs are scheduled on identical parallel machines with sequence dependent set-up times and distinct due dates. Two implementations of Genetic Algorithms and four implementations of Scatter Search are presented. These implementations were extensively tested over a set of randomly generated problems. The obtained results were used to compare the performance and the behavior of the implemented versions of these two meta-heuristics when applied to the scheduling problem studied. / Doutorado / Doutor em Engenharia Elétrica

A metodologia Tropos para o desenvolvimento de Sistemas Multiagentes é uma das metodologias que vem despertando interesse de diversos grupos de pesquisa. Apesar desse interesse e das pesquisas em andamento, alguns aspectos podem ser melhorados. Esta tese de mestrado apresenta uma abordagem para apoiar a consistência dos artefatos que compõem o projeto de Sistemas Multiagentes na metodologia Tropos. Para tanto, são propostas técnicas baseadas em cenários e objetivos em conjunto com heurísticas para elaboração e consistência dos artefatos de projeto que usa a metodologia Tropos, tendo como motivações a falta de uma sistematização que facilite a consistência dos artefatos gerados desde a fase de requisitos até o projeto detalhado. A abordagem foi experimentada em sistemas multiagentes, resultados preliminares indicam a obtenção dos benefícios esperados.