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-08-03T17:43:38Z (GMT). No. of bitstreams: 1 Mendes_AlexandredeSousa_D.pdf: 1237414 bytes, checksum: 79ab61ac72d53bfe2374807e58a1f03c (MD5) Previous issue date: 2003 / Doutorado

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T17:30:49Z (GMT). No. of bitstreams: 1 Yamashita_DeniseSato_D.pdf: 2970003 bytes, checksum: 72c1667962da475bb3a8d324efecf62b (MD5) Previous issue date: 2003 / Doutorado

Orientador: Christiano Lyra Filho / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T19:21:35Z (GMT). No. of bitstreams: 1 Cavellucci_Celso_D.pdf: 7349643 bytes, checksum: 36de213206369c56664ecd7794007a00 (MD5) Previous issue date: 1998 / Resumo: Este trabalho apresenta uma nova abordagem para a minimização das perdas em sistemas de distribuição de energia elétrica.A minimização das perdas é obtida por meio da reconfiguração das redes de distribuição.Considerando que essas redes operam com uma configuração radial, busca-se a árvore recobridora do grafo que representa a rede de distribuição, que minimize as perdas de energia e satisfaça as restrições de demanda e os limites do fluxo de corrente nas linhas; em outras palavras, trata-se de uma generalização do problema da árvore recobridora de custo mínimo. A generalização é devida às variações nos custos dos arcos com a mudança da configuração.A solução ótima global desse problema combinatório é obtida por um procedimento recursivo em duas fases, onde se combina as técnicas de fluxo não lineares e estratégias de busca usadas na área de inteligência artificial. Na primeira etapa a restrição de operação radial da rede é relaxada, levando a uma solução otimista para o problema; as informações desta solução são usadas na segunda etapa, onde busca-se a solução factível de custo mínimo. As etapas são repetidas, até que a configuração de rede radial de mínimas perdas seja encontrada. O procedimento recursivo é controlado por estratégias de busca inteligentes para contornar a explosão exponencial do esforço computacional. Três procedimentos de busca informada foram concebidos para obter uma árvore recobridora de perdas mínimas: backtracking infonnado, bactracking heurístico e algoritmo A*. Apresenta-se também procedimentos de paralelização dos algoritmos. Estudos de caso são discutidos, indicando as possibilidades e limitações da abordagem proposta / Abstract: This thesis presents a new approach to minimize losses in e1ectricalenergy distribution systems. The loss minimization is accomplished with the reconfiguration of the distribution network. Since distribution networks must operate radially, the problem can be regarded as a generalization of the minimum spanning tree problem. It seeks a spanning tree for a graph that represents the distribution network which minimizes losses while meetting loadsand satisfying constraints on line flow capacities - the generalization is due to variation in the costs as the network configuration changes. A global optimum to this combinatorial prob1em is found through a recursive two-step procedure, merging non-1inear network flow techniques with intelligent search strategies. Radial operation is relaxed in a first step, leading to an optimistic solution; information from the oprimist solution are used to approach feasibility in the second step. Both steps are repeated, driven by intelligent search techniques to cope with computational intractability. Three informed search procedures were conceived to obtain a minimum-loss spanning tree: enhanced backtracking, heuristic backtracking and A* algorithm. Parallel implementations of the algorithms are also presented. Case studies are discussed, providing guidelines about the possibilities and limitations of the proposed approach / Doutorado / Doutor em Engenharia Elétrica

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-25T20:34:59Z (GMT). No. of bitstreams: 1 Campos_DanilodaSilva_M.pdf: 5708291 bytes, checksum: 3aee68b9155ce0d5d427287c5fa57bc1 (MD5) Previous issue date: 1999 / Resumo: Neste trabalho foi estudado o problema de inventário e roteamento de veículos (PIRV). Um estudo de caso originado na agroindústria, para o problema de distribuição de ração de frangos foi relatado. O problema foi modelado como uma variação do PIRV tradicional. Uma série de restrições foram levantadas de maneira incremental e discutidas ao longo do trabalho. A estratégia de resolução focou, em primeiro lugar, o problema de manutenção do inventário nas granjas e depois, num segundo nível, no roteamento dos veículos. O algoritmo de programação de envios apresentado respeita todas as restrições técnicas e operacionais relacionadas ao problema de distribuição de ração. O algoritmo de montagem das rotas é usado sob demanda no momento dos despachos dos veículos da fábrica. O algoritmo foi colocado em operação e validado na prática. Uma simulação é apresentada para efeito de análise. Finalmente, foi desenvolvido um sistema computacional que integra todas as informações pertinentes ao problema, bem como que oferece uma interface amigável para os usuários do planejamento da empresa / Abstract: In this work we have studied the inventory and vehicle routing problem (IRVP). A case study, raised on the agribusiness area, for distribution of chicken food have been described. The problem was modeled as a variation of the traditional IRVP. Many constraints have been reported in an incremental way and explained throughout this work. The resolution strategy focused, first, on the inventory guarantee problem, and in a second levei on vehicle routing problem. The delivery planning algorithm considers ali technical and operational constraints related with the distribution chicken food system. The dispatching algorithm is used on demand, when each vehicle arrive in the factory. The algorithms have been evaluated and validated in a real operation. The analysis of the performance of the method was done by simulation. Finally, we have developed a software that integrate ali information needed to the planner, with a friendly user interface / Mestrado / Mestre em Engenharia Elétrica

Orientadores: Christiano Lyra Filho, Marcos Carneiro da Silva / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-25T23:00:34Z (GMT). No. of bitstreams: 1 Pinheiro_DanielBachega_M.pdf: 8970194 bytes, checksum: 94df48a445de9dd6f74c3350a54bc70b (MD5) Previous issue date: 1999 / Resumo: Esta tese apresenta o desenvolvimento de uma metodologia e um programa computacional para o projeto de rede externa de telefonia. Busca-se a minimização de custos através de métodos formais de otimização e automatiza-se o processo de projeto, levando a melhores tomadas de decisões. A metodologia foi desenvolvida para um cenário onde se deseja capacitar as redes atuais para atender as demandas reprimidas. As rede externas telefônicas ligam o assinante ao centro de fios através de duas sub-redes, a rede primária e a rede secundária. O projeto de um conjunto dessas redes é um problema combinatorial complexo e de difícil tratamento; a metodologia apresentada divide-se em três etapas, utilizando técnicas formais de otimização combinatória em conjunto com heurísticas construtivas e de melhoria. Inicialmente, localizam-se os armários telefônicos, que são pontos de "passagem" da rede primária para a rede secundária. Em seguida, minimiza-se a utilização de cabos e a construção de novos dutos e galerias na rede primária, avaliando-se, inclusive, alternativas de utilização de novas tecnologias, como as fibras e armários óticos. Finalmente, procura-se minimizar a instalação de novos cabos na rede secundária. Para ambas as sub-redes, aproveitam-se as facilidades presentes nas redes telefônicas existentes. Estudos de casos detalhados ilustram a aplicação da metodologia / Abstract: This thesis presents the development of a methodology and software for telecommunications access network design. It adopts a network flow optimizations methods and heuristics to minimize costs, leading to better decisions. The methodology was developed for a scenario where the network should be improved to deal with future demands. The access network connects the switching center to the subscribers, through the primary and secondary networks. Defining the best alternatives for both networks is a complex combinatorial problem; the methodology is divided in three stages that uses formal combinatorial optimization techniques in conjunction with a set of constructive heuristics and local search. Initially, equipments that connect primary and secondary networks are located. Following, the combined costs of cables and galleries is minimi zed for the primary network; the optimization includes the evaluation of using new technologies, such as fiber and optics equipment. Finally, the use of new cables in the secondary network is minimized. All the installed facilities are taken in account for both networks (primary and secondary). Detailed case studies illustrate application of the methodology / Mestrado / Mestre em Engenharia Elétrica

Tese (livre-docencia) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-15T01:13:46Z (GMT). No. of bitstreams: 1 PalazzoJunior_Reginaldo_LD.pdf: 6624330 bytes, checksum: 122b08f938ace4c9e54a3b41dbb9edff (MD5) Previous issue date: 1987 / Resumo: Neste trabalho procuramos estabelecer os conceitos e métodos utilizados no desenvolvimento das pesquisas sobre códigos de treliça dando um novo enfoque aos problemas: a) de determinação dos códigos ótimos invariantes no tempo sobre o corpo de Galois com q elementos, sob o critério de mínima Pb através da equivalência com o problema de otimização combina-torial; b) de determinação dos códigos ótimos variantes no tempo, sob o critério minimização da função enumeradora; c) equivalência do problema tratado em a) com aplicações em crip tografia; d) determinação da função enumeradora (generalizada) para códigos de treliça não lineares com aplicações em Múltiplo Acesso, Modulação por Sobreposição, Resposta Parcial, Modulação por Codificação de Treliça e etc... / Abstract: Not informed / Tese (livre-docencia) - Univer / Teoria de Informação e Codificação / Livre-Docente em Engenharia Eletrica

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T11:49:51Z (GMT). No. of bitstreams: 1 Bracht_EvandroCesar_M.pdf: 694440 bytes, checksum: b7f0c4ac260849f98329f238c91ec2bd (MD5) Previous issue date: 2004 / Resumo: Em um problema de classificação tradicional temos um conjunto de n objetos e um conjunto de m classes e queremos classificar cada objeto como pertencente a uma classe, de modo que esta classificação seja consistente com alguns dados que temos sobre o problema. Este trabalho apresenta um estudo do problema de classificação métrica através de algoritmos aproximados. Os algoritmos aproximados conhecidos para este problema são baseados na solução de grandes programas lineares e são impraticáveis para instâncias de tamanho moderado e grande. Apresentamos um algoritmo 8 log n-aproximado, analisado pela técnica primal-dual, que apesar de possuir fator de aproximação maior que os algoritmos anteriores, pode ser aplicado a grandes instâncias. Mostramos também que este fator de aproximação é justo, exceto por um fator constante. Obtivemos resultados experimentais usando instâncias geradas computacionalmente e instâncias de processamento de imagens com o novo algoritmo e com outros dois algoritmos baseados na resolução de programas lineares. Para estas instâncias o algoritmo proposto apresentou soluções de boa qualidade com um ganho considerável no tempo computacional / Abstract: In a traditional classification problem, we have a set of n objects and a set of m labels (or classes). We wish to assign one of m labels (or classes) to each one of n objects, in a way that is consistent with some observed data that we have about the problem. In this work we present a study of approximation algorithms for the metric labeling problem. The known approximation algorithms for this problem are based on solutions of large linear programs and are impractical for moderate and large size instances. We present an 8 log n-approximation algorithm analyzed by a primal-dual technique which, although has a factor greater than the previous algorithms, can be applied to large sized instances. We also show that the analysis is tight, up to a constant factor. We obtained experimental results on computational generated and image processing instances with the new algorithm and two other LP-based approximation algorithms. For these instances our algorithm presents good quality solutions with a considerable gain of computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

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-04T14:30:07Z (GMT). No. of bitstreams: 1 Mortati_CamilaFrederico_M.pdf: 341927 bytes, checksum: 5b1a9d9a8e6c0852c0e86425852e2584 (MD5) Previous issue date: 2005 / Resumo: Este trabalho aborda o problema de roteamento periódico de veículos, que consiste em designar uma combinação de dias de visitas a cada cliente, e definir as rotas de veículos em cada dia de um horizonte de planejamento, de forma a minimizar o custo ou a duração total das rotas. Um algoritmo de busca tabu é proposto para a resolução do problema. A história da busca tabu, usada para guiar o processo de busca, é representada através de memórias de curto e longo prazo. A eficiência das estratégias sugeridas para diversificação e intensificação, associadas à memória de logo prazo, são verificadas experimentalmente. O desempenho do algoritmo de busca tabu é testado computacionalmente em problemas da literatura. Um procedimento de busca tabu proposto na literatura é implementado e comparado com o algoritmo aqui proposto / Abstract: This work addresses the periodic vehicle routing problem that consists of assigning a combination of visiting days to each client, and defining the routes every day of a planning horizon, in such a way as to minimize the cost or duration of the routes. A tabu search algorithm is proposed for solving this problem. The history of the tabu search, used to guide the search process, is represented by short and long term memories. The efficacy of the suggested strategies for diversification and intensification, associated to the long term memory, is verified experimentally. The performance of the tabu search algorithm is tested computationally in instances from the literature. A tabu search procedure suggested in the literature is implemented and its performance is tested against the tabu search algorithm developed in this work / Mestrado / Automação / Mestre em Engenharia Elétrica

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2017-02-02T15:07:51Z No. of bitstreams: 1 texto completo.pdf: 2920159 bytes, checksum: 01255d0b5bb511ed365f7e524b38366c (MD5) / Made available in DSpace on 2017-02-02T15:07:51Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2920159 bytes, checksum: 01255d0b5bb511ed365f7e524b38366c (MD5) Previous issue date: 2016-07-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho aborda o problema de sequenciamento de tarefas em máquinas pa- ralelas não-relacionadas em que as tarefas causam desgastes nas máquinas. Este fator diminui o desempenho das máquinas levando ao aumento do tempo de pro- cessamento das tarefas ao longo do tempo. O objetivo do problema é encontrar as sequências de processamento de tarefas em cada máquina de tal maneira que os desgastes das máquinas sejam reduzidos e, consequentemente, minimizar o tempo máximo de conclusão de todas as tarefas, conhecido como makespan. Neste traba- lho, inicialmente, é proposto um novo modelo de Programação Inteira Mista baseado na geração de padrões (conjuntos de tarefas) para cada máquina, com objetivo de obter soluções ótimas para o problema. Dado que o problema é NP-Difícil para mais de uma máquina, dois algoritmos heurísticos são propostos para obter solu- ções de alta qualidade em baixo tempo computacional. Os algoritmos são baseados nas meta-heurísticas Iterated Local Search (ILS) e Iterated Greedy (IG), respecti- vamente. Também, as heurísticas ILS e IG são combinadas com uma variante do método Variable Neighborhood Descent (VND), que utiliza uma ordenação aleatória das vizinhanças (RVND) na fase da busca local, obtendo dois algoritmos híbridos denominados ILS-RVND e IG-RVND. O benchmark usado nos experimentos compu- tacionais usa 900 instâncias de médio porte disponíveis na literatura, e 900 instâncias de grande porte geradas neste trabalho. Os algoritmos são comparados entre si e também com um algoritmo Simulated Annealing (SA) proposto na literatura para o mesmo problema. Os testes realizados mostram que os desempenhos dos algoritmos propostos são significativamente superiores em relação ao algoritmo SA. / This work addresses an unrelated parallel machine scheduling problem in which the jobs cause deterioration of the machines. This factor decreases the performance of the machines, causing an increasing of the jobs over time. The problem is to find the processing sequence of jobs on each machine in order to reduce the deterioration of the machines and consequently minimize the maximum completion time of jobs (makespan). In this work, initially, we propose a new Mixed-Integer Programming model based on patterns (sets of jobs) generation to find optimal solution of the pro- blem. Since the problem is NP-hard when the number of machines is greater than one, two heuristic algorithms are proposed to obtain near-optimal solutions in reaso- nable computational time. The algorithms are based on the meta-heuristics Iterated Local Search (ILS) and Iterated Greedy (IG), respectively. Also, the algorithms ILS and IG are coupled with a variant of the Variable Neighborhood Descent (VND) method that uses a random ordering of neighborhoods (RVND) in local search phase, obtaining two hybrid algorithms called ILS-RVND and IG-RVND. The benchmark used in computational experiments uses 900 medium-size instances available in the literature, and 900 large-size instances generated in this work. The algorithms are compared against each other and are also compared with a Simulated Annealing (SA) algorithm proposed in the literature for the problem under study. The tests show that the proposed algorithms have superior performances compared to the SA algorithm.

Orientador: Flavio Keidi Miyazawa / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-07T21:41:01Z (GMT). No. of bitstreams: 1 Xavier_EduardoCandido_D.pdf: 20666026 bytes, checksum: 5e051653d938a813e227b1e2eebcd415 (MD5) Previous issue date: 2006 / Resumo: Neste trabalho estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes e que geram soluções com garantia de qualidade. Neste trabalho apresentamos alguns algoritmos aproximados para problemas de empacotamento com aplicações práticas. Outra maneira de se lidar com problemas NP-difíceis é o desenvolvimento de heurísticas. Neste trabalho também apresentamos heurísticas baseadas no método de geração de colunas para problemas de corte e empacotamento bidimensional. Resultados computacionais sugerem que tais heurísticas são eficientes e geram soluções de muito boa qualidade. / Abstract: In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are efficient algorithms that produce solutions with quality guarantee. We present several approximation algorithms for some packing problems that have practical applications. Another way to deal with NP-hard problems is to develop heuristics. We also consider column generation based heuristics for packing problems. In this case, we present column generation algorithms for some two dimensional packing problems and also present computational tests with the proposed algorithms. The computational results shows that the heuristics are efficient and produce solutions of very good quality. / Doutorado / Doutor em Ciência da Computação