Orientador : Fernando Antonio Campos Gomide / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T15:28:39Z (GMT). No. of bitstreams: 1 RamirezDominguez_LuisAlberto_M.pdf: 8004190 bytes, checksum: 62aeeb49d8655d2c7172f08e8c6ba749 (MD5) Previous issue date: 2000 / Resumo: Este trabalho descreve uma nova ferramenta computacional para resolver um problema de programação de escalas encontrado no Sistema de Transporte Ferroviário Brasileiro. Um procedimento de busca evolutiva é usado na procura das melhores seqüências de trabalho, usando para isso critérios práticos que permitam um balanço aceitável no sentido econômico e social. A função de avaliação das soluções é baseada em duas metodologias de análise. A primeira usa um método de soma ponderada e a outra baseia-se em conceitos da teoria de conjuntosfuzzy. O algoritmo proposto foi testado usando dados reais fornecidos por uma empresa ferroviária. As escalas geradas pelo algoritmo evolutivo apresentaram resultados qualitativamente superiores quando comparados com os resultados produzidos por técnicas atualmente em uso / Abstract: This work describes a new computational tool to solve a crew-scheduling problem common in the Brazilian Railway Transport Systems. An evolutionary search procedure is used to generate the preferred work sequences with respect to evaluating criteria. The aim is to obtain an acceptable balance between human and economic aspects. The fitness function is based on two methodologies. The first one uses a weighting sum scheme to aggregate the objectives whereas the second uses fuzzy set theory for the same purpose. The proposed algorithm was tested with actual data provided by a railway company. The schedules generated by the evolutionary algorithm are qualitatively better than those used in practice / Mestrado / Automação / Mestre em Engenharia Elétrica

Orientador : João Carlos Setubal / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-02T14:52:50Z (GMT). No. of bitstreams: 1 Conceicao_ArlindoFlavioda_M.pdf: 1967561 bytes, checksum: 27b15ad3216c72fe882e027f64fc719e (MD5) Previous issue date: 2000 / Resumo: Nesta dissertação estudamos o aspecto combinatório dos problemas de congestionamento. O principal problema estudado consiste em, dado um grafo G e um inteiro positivo k, encontrar k árvores espalhadas de G, não necessariamente disjuntas, de peso total mínimo. Neste problema o congestionamento é caracterizado por funções que penalizam o peso de uma aresta se ela é usada por mais de uma árvore. Roskind e Tarjan apresentaram um algoritmo para a versão deste problema onde as árvores devem ser disjuntas nas arestas. Nós apresentamos uma descrição detalhada do algoritmo de Roskind e Tarjan e então mostramos um algoritmo polinomial para o problema de congestionamento, o algoritmo consiste em uma redução ao problema disjunto. O nosso algoritmo é quadrático em k. Apresentamos ainda duas heurísticas de complexidade linear em k. Baseados na mesma técnica, desenvolvemos algoritmos polinomiais para problemas combinatórios de congestionamento relacionados aos problemas de encontrar um caminho mínimo e de encontrar um emparelhamento de custo mínimo / Abstract: This work studies the combinatorial aspects of congestion problems. The main problem studied is the following: Given a graph G and a positive integer k, we want to find k spanning trees on G, not necessarily disjoint, of minimum total weight, such that the weight of each edge is subject to a penalty function if it belongs to more than one tree. This penalty function models congestion situations. Roskind and Tarjan have developed an algorithm for the disjoint version of this problem. We present a detailed description of their algorithm and then show that a polynomial algorithm for the congestion problem can be obtained by reducing it to the disjoint problem. The complexity of our algorithm is quadratic in k. We also present two heuristics with complexity linear in k. Based on the same idea, we then present polynomial algorithms for combinatorial congestion problems related to shortest paths and minimum weight matchings / Mestrado / Mestre em Ciência da Computação

Orientador : Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-02T15:30:06Z (GMT). No. of bitstreams: 1 Yunes_TallysHoover_M.pdf: 6565656 bytes, checksum: 4ef3637ed1584172d24419ae96564bcc (MD5) Previous issue date: 2000 / Resumo: Este trabalho de mestrado procurou estudar e resolver um problema real de escalonamento de mão-de-obra oriundo da operação diária de uma empresa de ônibus urbanos da cidade de Belo Horizonte. Por questões de complexidade, este tipo de problema é normalmente dividido em dois subproblemas, a saber: crew scheduling, que trata a alocação diária de viagens a duplas de funcionários (motorista e cobrador), e crew rostering, que parte da solução do subproblema anterior e constrói uma escala de trabalho de mais longo prazo, e.g. um mês. Cada um desses subproblemas foi abordado utilizando-se técnicas de Programação Matemática e Programação por Restrições. Para o problema de crew scheduling, em particular, desenvolveu-se também um algoritmo híbrido de geração de colunas combinando as duas técnicas mencionadas e cujo desempenho foi significativamente melhor que o dos métodos isolados. Em geral, os modelos matemáticos resultantes de problemas dessa natureza são de grande porte. No caso aqui tratado, a matriz de coeficientes do programa linear associado a algumas instâncias dos problemas chega a conter dezenas de milhões de colunas. Todos os algoritmos propostos para a solução do problema foram implementados e testados sobre dados reais obtidos junto à empresa em questão. A análise dos resultados computacionais mostra que foi possível obter soluções de excelente qualidade em um tempo de computação adequado para as necessidades da empresa. Em particular, para o subproblema de scheduling, foi possível comprovar que as soluções obtidas são ótimas / Abstract: This dissertation aimed at studying and solving a real world crew management problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, in Brazil. Due to its intrinsic complexity, the problem is usualIy divided in two distinct subproblems, namely: crew scheduling, that deals with the daily alIocation of trips to crews, and crew rostering, which takes the solution of the first subproblem and extends the scheduling to a longer planning horizon, e.g. a month. We have tackled each one of these subproblems using Mathematical Programming (MP) and Constraint Logic Programming (CLP) approaches. Besides, we also developed a hybrid column generation algorithm for solving the crew scheduling problem, combining MP and CLP, which performed much better than the two previous approaches when taken in isolation. Real world crew management problems typicalIy give rise to large scale mathematical models. In our case, the coefficient matrix of the linear program associated with some instances of the problem contains tens of millions of columns. AlI the proposed algorithms have been implemented and tested over real world instances obtained from the aforementioned company. The analysis of our experiments indicates that it was possible to find high quality solutions within computational times that are suitable for the company's needs. In particular, we were able to find provably optimal solutions for the crew scheduling problem / Mestrado / Mestre em Ciência da Computação

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: Jose Plinio de Oliveira Santos / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-03T19:13:49Z (GMT). No. of bitstreams: 1 Craveiro_IreneMagalhaes_D.pdf: 478619 bytes, checksum: 002cd67ea4ffe9740bdb584528e54706 (MD5) Previous issue date: 2004 / Doutorado / Doutor em Matemática

Orientadores: Paulo Morelato França, Mauricio Guilherme de Carvalho Resende / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-03T19:16:40Z (GMT). No. of bitstreams: 1 Buriol_LucianaSalete_D.pdf: 1278955 bytes, checksum: 81c4d001b9fa79d3045253176b03bfbd (MD5) Previous issue date: 2003 / Doutorado

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T19:57:30Z (GMT). No. of bitstreams: 1 Teodoro_AlanAugusto_M.pdf: 1993309 bytes, checksum: eb9abfe2294e3e44de68abc5fba42be3 (MD5) Previous issue date: 2003 / Resumo: Neste trabalho é realizado um estudo experimental de técnicas de otimização para gerar soluções eficientes para o problema do corte bidimensional, que pode ser definido como: dado um número finito n de itens retangulares de largura li, comprimento Ci e demanda di, a serem obtidos de retângulos maiores de dimensão LxC, encontrar padrões de corte que atendam a uma demanda de itens utilizando o menor número possível de retângulos maiores. O problema foi formulado através de um modelo de programação linear inteira. Para obter soluções de custo reduzido para o problema, aplicamos o método de geração de colunas, obtendo então soluções viáveis para o problema relaxado do programa linear inteiro. Utilizamos um algoritmo de aproximação para obter uma solução inicial de qualidade e métodos de arredondamento com tratamento de problema residual para transformar a solução fracionária em soluções viáveis para o problema. Finalmente, diversos estudos são realizados através de testes computacionais / Abstract: In this work we describe an experimental study of optimization techniques to generate efficient results for the two-dimensional cutting stock problem which can be defined as follows: given a finite number n of rectangular items of width li, length Ci and demand di, to be cut from larger rectangles with dimensions LxC, find cutting pattems which attend the demand of the requested items minimizing the number of larger rectangles. The problem is formulated as an integer programming mode!. To obtain solutions with reduced cost to the problem, we apply the column generation method, obtaining feasible solutions for the relaxed integer programo We use an approximation algorithm to generate a good initial solution and rounding techniques with treatment of the residual problem to transform the fractional solution into feasible solutions to the problem. Finally, several studies are realized through computational experiments / Mestrado / Engenharia de Computação / Mestre em 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-03T19:56:42Z (GMT). No. of bitstreams: 1 Ramos_Luciana_M.pdf: 2723419 bytes, checksum: 9c82eed676fdf2e14f006a3a84c61941 (MD5) Previous issue date: 2003 / Mestrado / Engenharia de Computação / Mestre Profissional em Computação

Submitted by Reginaldo Soares de Freitas (reginaldo.freitas@ufv.br) on 2018-06-04T17:24:47Z No. of bitstreams: 1 texto completo.pdf: 880884 bytes, checksum: 82669a6f1f82a252a3fc9e9624328ac0 (MD5) / Made available in DSpace on 2018-06-04T17:24:47Z (GMT). No. of bitstreams: 1 texto completo.pdf: 880884 bytes, checksum: 82669a6f1f82a252a3fc9e9624328ac0 (MD5) Previous issue date: 2018-02-23 / O conteúdo de análise combinatória e probabilidades ́e apresentado nesta dissertação sob o aspecto relativo à sua aplicação no processo dos concursos públicos de nível médio. Para tanto, desenvolveu-se um estudo do conteúdo de análise combinatória e probabilidades com uma ampla apresentação da sua história, seus principais resultados e o contexto institucional das orientações oficiais de ensino bem como uma descrição do processo de avaliação nos concursos públicos por meio de questões desse conteúdo aplicadas nesses certames. / The content of combinatorial analysis and probabilities is presented in this dissertation in the aspect related to its application in the process of the civil service entrance examination of high school level. For that, a study of the content of combinatorial analysis and probabilities was developed with a broad presentation of its history, its main results and the institutional context of the official teaching guidelines as well as to describe the evaluation process in the public tendering through applied questions in these examinations that use this content.

Orientador: Claudio L. Lucchesi / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-13T23:27:26Z (GMT). No. of bitstreams: 1 Giglio_MariaCeciliaMottaTorres_M.pdf: 5819263 bytes, checksum: c24dd7357f8a2283359356720f51597b (MD5) Previous issue date: 1990 / Resumo: O problema dos dois caminhos disjuntos consiste em determinar, dados vértices s1, S2, t1 e t2 de um grafo, se existem ou não dois caminhos disjuntos, P1 e P2 ligando s1 a t1 e S1 a t1, respectivamente. O problema se manifesta em quatro versões, a saber, o grafo pode ser orientado ou não, e a exigência de disjunção pode ser apenas nas arestas ou também nos vértices. Nas quatro versões, o problema admite reduções elementares do ponto de vista computacional que levam finalmente à solução ou a uma certidão da sua não existência. Esta análise apresenta uma interconexão interessante entre combinatória, complexidade de algoritmos e topologia. No caso de grafos orientados, exige-se também que o grafo seja acíclico, pois caso contrário o problema se torna NP-difícil. / Abstract: The two disjoint paths problem consists in determining, given vertices S1, S2, t1 and t2 of a graph, whether or not there exist two disjoint paths. P1 and P21 joining s1 to t1 and S2 to t2 respectively. The problem may be considered in four versions, namely, the graph may or may not be directed, and the disjointness requirement on the paths may be on the edges only or on the vertices too. In all version, the problem admits computationally elementary reductions which provide either a solution or a certificate of its nonexistence. The analysis presents an interesting interconnection between combinatorics, complexity of algorithms and topology. In the case of direct graphs, it is also required that the graph be acyclic, otherwise the problem becomes NP-hard. / Mestrado / Mestre em Ciência da Computação