Problemas de corte de estoque consistem em arranjar peças menores, em tamanhos e quantidades especificados, dentro de peças maiores. Tais problemas têm sido investigados intensamente nas últimas décadas, acrescidos de novas características e novos métodos de solução. Nesta tese abordamos o problema de corte de estoque multiperíodo que surge imerso no planejamento e programação da produção em empresas que têm um estágio de produção caracterizado pelo corte de peças. As demandas dos itens ocorrem em períodos diversos de um horizonte de planejamento finito, sendo possível antecipar ou não a produção de itens. Os objetos disponíveis em estoque não utilizados em um período ficam disponíveis no próximo período, juntamente com novos objetos adquiridos ou produzidos pela própria empresa. Um modelo de otimização linear inteira de grande porte é proposto, cujo objetivo pondera o custo das perdas nos cortes, os custos de estocagem de objetos e itens. O método simplex com geração de colunas foi especializado para resolver a relaxação linear do modelo proposto. Foram realizados experimentos computacionais com problemas de corte de estoque unidimensional e bidimensional. Tais experimentos mostram que ganhos efetivos podem ser obtidos usando-se o modelo de corte de estoque multiperíodo, quando comparado com a solução lote-por-lote, tipicamente utilizada na prática. Porém, na prática, a solução relaxada é de pouca, ou nenhuma, utilidade. Assim, nesta tese, desenvolvemos dois procedimentos de arredondamento da solução do problema multiperíodo, baseado em horizonte rolante, ou seja, determinamos uma solução inteira factível apenas para o primeiro período, a qual será, de fato, implementada. Enfim, concluímos que o modelo para o problema de corte de estoque multiperíodo permite flexibilidade na análise de uma solução a ser implementada e, portanto, é uma ferramenta que permite ao gerente de produção uma visão global do problema para auxiliá-lo na tomada de decisões / Cutting stock problems consist of cutting a set of available stock objects in order to produce smaller ordered items. Such problems have been intensively researched over the last decades, together with additional characteristics and new methods for solving them. In this thesis, we address the multiperiod cutting stock problem, which arises in the production planning and programming in many industries that have a cutting process as an important stage. Ordered items have different due date over a finite planning horizon. An integer linear optimization model of large scale is proposed. The model makes possible to anticipate or not the production of items. Unused objects in inventory in a period become available to the next period, added to new inventory, which are acquired or produced by the own company. The mathematical model\'s objective is to minimize the cost of waste in the cutting process and costs for holding objects and fInal items. The simplex method with column generation was specialized to solve its linear relaxation. Computational experiments were carried out to solve one-dimensional and two-dimensional cutting stock problems. Such experiments showed that the multiperiod model could obtain effective gains when compared with the lot-for-lot solution, which is typically used in practice. However, in practical problems, the fractional solution is useless. So, in this thesis, two rounding procedures are developed to determine integer solutions for multiperiod cutting stock problems. Such procedures are based on a rolling horizon scheme, which roughly means, find an integer solution only for the first period, since this is the solution to be, in fact, carried out. Finally, we conclude that the proposed model for multiperiod cutting stock problems allows flexibility on analyzing a solution to be put in practice. The multiperiod cutting problem can be a tool that provides the decision maker a wide view of the problem and it may help him/her on making decisions

Problemas de corte de estoque consistem em arranjar peças menores, em tamanhos e quantidades especificados, dentro de peças maiores. Tais problemas têm sido investigados intensamente nas últimas décadas, acrescidos de novas características e novos métodos de solução. Nesta tese abordamos o problema de corte de estoque multiperíodo que surge imerso no planejamento e programação da produção em empresas que têm um estágio de produção caracterizado pelo corte de peças. As demandas dos itens ocorrem em períodos diversos de um horizonte de planejamento finito, sendo possível antecipar ou não a produção de itens. Os objetos disponíveis em estoque não utilizados em um período ficam disponíveis no próximo período, juntamente com novos objetos adquiridos ou produzidos pela própria empresa. Um modelo de otimização linear inteira de grande porte é proposto, cujo objetivo pondera o custo das perdas nos cortes, os custos de estocagem de objetos e itens. O método simplex com geração de colunas foi especializado para resolver a relaxação linear do modelo proposto. Foram realizados experimentos computacionais com problemas de corte de estoque unidimensional e bidimensional. Tais experimentos mostram que ganhos efetivos podem ser obtidos usando-se o modelo de corte de estoque multiperíodo, quando comparado com a solução lote-por-lote, tipicamente utilizada na prática. Porém, na prática, a solução relaxada é de pouca, ou nenhuma, utilidade. Assim, nesta tese, desenvolvemos dois procedimentos de arredondamento da solução do problema multiperíodo, baseado em horizonte rolante, ou seja, determinamos uma solução inteira factível apenas para o primeiro período, a qual será, de fato, implementada. Enfim, concluímos que o modelo para o problema de corte de estoque multiperíodo permite flexibilidade na análise de uma solução a ser implementada e, portanto, é uma ferramenta que permite ao gerente de produção uma visão global do problema para auxiliá-lo na tomada de decisões / Cutting stock problems consist of cutting a set of available stock objects in order to produce smaller ordered items. Such problems have been intensively researched over the last decades, together with additional characteristics and new methods for solving them. In this thesis, we address the multiperiod cutting stock problem, which arises in the production planning and programming in many industries that have a cutting process as an important stage. Ordered items have different due date over a finite planning horizon. An integer linear optimization model of large scale is proposed. The model makes possible to anticipate or not the production of items. Unused objects in inventory in a period become available to the next period, added to new inventory, which are acquired or produced by the own company. The mathematical model\'s objective is to minimize the cost of waste in the cutting process and costs for holding objects and fInal items. The simplex method with column generation was specialized to solve its linear relaxation. Computational experiments were carried out to solve one-dimensional and two-dimensional cutting stock problems. Such experiments showed that the multiperiod model could obtain effective gains when compared with the lot-for-lot solution, which is typically used in practice. However, in practical problems, the fractional solution is useless. So, in this thesis, two rounding procedures are developed to determine integer solutions for multiperiod cutting stock problems. Such procedures are based on a rolling horizon scheme, which roughly means, find an integer solution only for the first period, since this is the solution to be, in fact, carried out. Finally, we conclude that the proposed model for multiperiod cutting stock problems allows flexibility on analyzing a solution to be put in practice. The multiperiod cutting problem can be a tool that provides the decision maker a wide view of the problem and it may help him/her on making decisions

O planejamento de rotações de culturas é um tema de interesse em ascensão por permitir uma redução significativa no uso de adubos industriais, agrotóxicos e outros produtos químicos no cultivo, permitindo a auto-sustentação e qualidade das terras cultivadas. Este trabalho centraliza em utilizar rotações para atender uma demanda periódica prédeterminada, respeitando as restrições relativas a aspectos ecológicos que auxiliam na estabilidade geral do solo para definir uma rotação de culturas factível. Modelos matemáticos que consideram um tamanho mínimo de lote a ser usado por uma rotação e métodos heurísticos, baseados em geração de colunas, são apresentados. Uma análise detalhada do comportamento dos métodos perante variações em diferentes parâmetros e critérios é realizada. A primeira heurística, denominada Algoritmo GC-BC, obteve resultados de melhor qualidade e de forma mais rápida que a segunda heurística, denominada Heurística Lote Fixo. Entretanto, combinando ambas heurísticas foi possível obter os resultados mais satisfatórios, ou seja, soluções que respeitam a condição de lote mínimo em um tempo computacional aceitável para um planejamento anual, cujos valores são próximos a um limitante superior. A ideia subjacente de gerar colunas adicionais para um problema mestre restrito produz soluções de qualidade, o que pode vir a ser aplicado em outras áreas de pesquisa que necessitam da geração de colunas para uma resolução em tempo computacional viável / The crop rotation planning is a rising topic for providing a significative reduction on the usage of industrial fertilizers, pesticides and other chemical, allowing the soil to selfsustain. This study focus on using rotations to meet a periodic and pre-defined demand while ecologic restrictions, that help sustain the soils stability, define a valid crop rotation. Mathematical models that consider a minimum size of a used lot associated with a given rotation and heuristic resolution methods, based on column generation, are presented. A detailed analysis of the methods behaviour before changes on parameters and criteria is performed. The first heuristic, called GC-BC Algorithm, achieved better and faster results compared to the second heuristic, called Fixed Lot Heuristic. However, combining both heuristics produced even better results, that is, solutions that respect the minimum lot sizing restrictions in good execution time for an annual planning. The idea behind of generating additional columns to the restricted master problem produces good quality solutions, which may be applicable in other research areas that require column generation for their resolution with a reasonable execution time

Made available in DSpace on 2016-08-10T10:40:17Z (GMT). No. of bitstreams: 1 Geovane Reges de Jesus Campos.pdf: 308868 bytes, checksum: 7d7dde587ca6eede4281609bfad2c151 (MD5) Previous issue date: 2012-09-04 / This paper presents a study for the classroom assignment problem for the PUC Goiás, Area 3, Campus I, based on a programming system (SAPA), the Hungarian algorithm, and on the idea of solving the problem time by time. The problem is solved with real data no more than 6 seconds. / Este trabalho apresenta um estudo para o problema de designação de salas de aula para a PUC Goiás, área 3, Campus I, baseado em um sistema de programação (SAPA), no algoritmo Húngaro e na idéia de resolver o problema horário por horário. O problema é resolvido, com dados reais, em não mais do que 6 segundos.

Made available in DSpace on 2016-08-10T10:40:20Z (GMT). No. of bitstreams: 1 JEANCARLO RIBEIRO.pdf: 683766 bytes, checksum: 28e6690b67012436dd91788ec7ff346b (MD5) Previous issue date: 2013-06-17 / The classroom assignment problem at universities consist in distributing classes scheduled for the appropriate rooms, respecting the requirements in each situation. The objective of this work is to apply the Hungarian algorithm and a computational system to solve the classroom assignment problem time by time. The tests were performed with real data from the PUC Goiás for a quantitative of 5116 classes into 313 classrooms. As a result, we solved the problem in approximately 12 minutes and the solution quality was compared with manual designation usually applied by the institution, which takes a month and a half. / O problema de designação de salas de aula em Universidades consiste em distribuir turmas programadas para as devidas salas, respeitando os requisitos estabelecidos em cada situação. O objetivo deste trabalho é a aplicação do algoritmo húngaro e de um sistema computacional para a resolução do problema de alocação horário por horário. Os testes foram realizados com dados reais da PUC Goiás para um quantitativo de 5116 turmas em 313 salas de aula. Como resultados, resolvemos o problema em aproximadamente 12 minutos e comparamos a qualidade da solução com a designação manual usualmente realizada pela Instituição, a qual leva um mês e meio.

Made available in DSpace on 2016-08-10T10:40:24Z (GMT). No. of bitstreams: 1 Davi Taveira Alencar Alarcao.pdf: 944757 bytes, checksum: 30d55936bd0acaff3d7ecf1816fe22f5 (MD5) Previous issue date: 2015-02-07 / The classroom assignment problem at universities consist in distributing classes scheduled for the appropriate rooms, respecting the requirements in each situation. The objective of this work is to improve the process of allocation of classroom PUC Goiás. The tests were performed with real data from the PUC Goiás for a quantitative of 5116 classes into 312 classrooms. As a result, we solved the problem in approximately 34 minutes and the solution quality was compared both with manual designation usually applied by the institution, which takes a month and a half, as with the results found in Ribeiro (2012). / O problema de designação de salas de aula em Universidades consiste em distribuir turmas programadas para as devidas salas, respeitando os requisitos estabelecidos em cada situação. O objetivo deste trabalho é o de melhorar o processo de alocação de salas de aula da PUC Goiás. Os testes foram realizados com dados reais da PUC Goiás para um quantitativo de 5116 turmas em 312 salas de aula. Como resultados, resolvemos o problema em aproximadamente 34 minutos e comparamos a qualidade da solução tanto com a designação manual usualmente realizada pela Instituição, a qual leva um mês e meio, quanto com os resultados encontrados em Ribeiro (2012).

O problema abordado nesta pesquisa consiste na distribuição de água em redes urbanas para o atendimento de demandas conhecidas, com o objetivo de minimizar o custo da energia elétrica necessária para o funcionamento de bombas hidráulicas. As bombas hidráulicas são utilizadas para captar água de poços artesianos ou estações de tratamento de água para abastecer reservatários distribuídos por bairros de uma cidade, de onde a população será atendida por força gravitacional. Como o custo da energia elétrica varia ao longo do dia, se faz necessário um planejamento do funcionamento das bombas para que não sejam ligadas nos horários em que a energia elétrica é mais cara. O problema de planejamento de estoque de água em reservatórios (PPEAR) consiste em decidir em quais períodos ou frações dos períodos do horizonte de planejamento as bombas hidráulicas que abastecem os reservatórios devem permanecer ligadas e em quais períodos ou frações dos períodos deve haver transporte de água entre os reservatórios para que a demanda de cada reservatório seja atendida em cada período e sejam respeitados os níveis mínimos e máximos de água nos reservatórios. Uma solução heurística para resolver o PPEAR é proposta e analisada por comparação com as soluções obtidas pelo método de enumeração implícita. Resultados computacionais comprovam a eficiência da abordagem, tanto pela qualidade das soluções como pelo baixo tempo de resposta / The problem focused in this study consists of reducing the eletrical energy cost necessary to the operation of hydraulic pumps. The hydraulic pumps are used to catch water from artesians wells or Water Treatment Station to supply tanks which are located in districts in a city, from which the population will be supplied by gravitational force. As the cost of electrical energy varies along the day, a schedule of the pumps run is necessary to avoid that they are not turned in the periods when the energy cost is more expensive. The problem of water stock schedule in tanks (WSST) consists of deciding in which periods or parts of them of the horizon planning the hydraulic pumps have to put on, and in which periods or parts of them should transfer water among the tanks so that the demand of each tank is met for each period and lower and upper limits of water shouldn\'t be violated. A heuristic solution is proposed and analyzed by comparing its solutions with the solutions obtained by the branch and bound method. Computational experiments show the efficiency of the heuristic

O planejamento de rotações de culturas é um tema de interesse em ascensão por permitir uma redução significativa no uso de adubos industriais, agrotóxicos e outros produtos químicos no cultivo, permitindo a auto-sustentação e qualidade das terras cultivadas. Este trabalho centraliza em utilizar rotações para atender uma demanda periódica prédeterminada, respeitando as restrições relativas a aspectos ecológicos que auxiliam na estabilidade geral do solo para definir uma rotação de culturas factível. Modelos matemáticos que consideram um tamanho mínimo de lote a ser usado por uma rotação e métodos heurísticos, baseados em geração de colunas, são apresentados. Uma análise detalhada do comportamento dos métodos perante variações em diferentes parâmetros e critérios é realizada. A primeira heurística, denominada Algoritmo GC-BC, obteve resultados de melhor qualidade e de forma mais rápida que a segunda heurística, denominada Heurística Lote Fixo. Entretanto, combinando ambas heurísticas foi possível obter os resultados mais satisfatórios, ou seja, soluções que respeitam a condição de lote mínimo em um tempo computacional aceitável para um planejamento anual, cujos valores são próximos a um limitante superior. A ideia subjacente de gerar colunas adicionais para um problema mestre restrito produz soluções de qualidade, o que pode vir a ser aplicado em outras áreas de pesquisa que necessitam da geração de colunas para uma resolução em tempo computacional viável / The crop rotation planning is a rising topic for providing a significative reduction on the usage of industrial fertilizers, pesticides and other chemical, allowing the soil to selfsustain. This study focus on using rotations to meet a periodic and pre-defined demand while ecologic restrictions, that help sustain the soils stability, define a valid crop rotation. Mathematical models that consider a minimum size of a used lot associated with a given rotation and heuristic resolution methods, based on column generation, are presented. A detailed analysis of the methods behaviour before changes on parameters and criteria is performed. The first heuristic, called GC-BC Algorithm, achieved better and faster results compared to the second heuristic, called Fixed Lot Heuristic. However, combining both heuristics produced even better results, that is, solutions that respect the minimum lot sizing restrictions in good execution time for an annual planning. The idea behind of generating additional columns to the restricted master problem produces good quality solutions, which may be applicable in other research areas that require column generation for their resolution with a reasonable execution time

O problema abordado nesta pesquisa consiste na distribuição de água em redes urbanas para o atendimento de demandas conhecidas, com o objetivo de minimizar o custo da energia elétrica necessária para o funcionamento de bombas hidráulicas. As bombas hidráulicas são utilizadas para captar água de poços artesianos ou estações de tratamento de água para abastecer reservatários distribuídos por bairros de uma cidade, de onde a população será atendida por força gravitacional. Como o custo da energia elétrica varia ao longo do dia, se faz necessário um planejamento do funcionamento das bombas para que não sejam ligadas nos horários em que a energia elétrica é mais cara. O problema de planejamento de estoque de água em reservatórios (PPEAR) consiste em decidir em quais períodos ou frações dos períodos do horizonte de planejamento as bombas hidráulicas que abastecem os reservatórios devem permanecer ligadas e em quais períodos ou frações dos períodos deve haver transporte de água entre os reservatórios para que a demanda de cada reservatório seja atendida em cada período e sejam respeitados os níveis mínimos e máximos de água nos reservatórios. Uma solução heurística para resolver o PPEAR é proposta e analisada por comparação com as soluções obtidas pelo método de enumeração implícita. Resultados computacionais comprovam a eficiência da abordagem, tanto pela qualidade das soluções como pelo baixo tempo de resposta / The problem focused in this study consists of reducing the eletrical energy cost necessary to the operation of hydraulic pumps. The hydraulic pumps are used to catch water from artesians wells or Water Treatment Station to supply tanks which are located in districts in a city, from which the population will be supplied by gravitational force. As the cost of electrical energy varies along the day, a schedule of the pumps run is necessary to avoid that they are not turned in the periods when the energy cost is more expensive. The problem of water stock schedule in tanks (WSST) consists of deciding in which periods or parts of them of the horizon planning the hydraulic pumps have to put on, and in which periods or parts of them should transfer water among the tanks so that the demand of each tank is met for each period and lower and upper limits of water shouldn\'t be violated. A heuristic solution is proposed and analyzed by comparing its solutions with the solutions obtained by the branch and bound method. Computational experiments show the efficiency of the heuristic

Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura