Made available in DSpace on 2014-06-11T19:22:34Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-03-25Bitstream added on 2014-06-13T18:49:35Z : No. of bitstreams: 1 000740375.pdf: 2082789 bytes, checksum: d1483f48718c198c624d0f146dae6d70 (MD5) / Os problemas de corte ótimo são considerados como clássicos dentro da pesquisa operacional, dado sua grande área de aplicação na industria e sua alta complexidade matemática e computacional. Um dos problemas mais conhecidos desta classe é o chamado Cutting Stock Problem, o qual permite dividir uma placa em varias peças de diversos tamanhos, com a finalidade de obter a configuração que maximize a área da placa que está sendo utilizada. Dado o nível de dificuldade e a grande quantidade de aplicações deste problemas em diversas áreas, existe muito interesse em criar novos procedimentos eficientes para resolver este tipo de problemas. Nesta dissertação, é apresentado o estado da arte dos diversos problemas de corte bidimensional de peças retangulares em uma única placa, em varias placas e em rolos, considerando a possibilidade de rotacionar as peças em um ângulo de 90 e com restrições de corte tipo não-guilhotinado. Além disso, são descritas as abordagens matemáticas aplicadas pelos diversos pesquisadores dedicados a resolver estes problemas. Este trabalho está focado em resolver exclusivamente o Cutting Stock Problem com e sem rotação de peças. Portanto, é proposto um tipo de codificação binária com vista a ser aplicada neste tipo de problema e resolvê-lo mediante o uso do algoritmo heurístico Bottom-Left, em conjunto com a metaheurística Simulated Annealing. Finalmente, para comprovar a eficiência da metodologia apresentada, foram utilizados alguns casos de estudo da literatura especializada, com diferentes níveis de complexidade. Para cada caso, são apresentados os resultados obtidos e é realizada uma comparação dos métodos de solução propostos para resolver o Cutting Stock Problem com e sem rotação de peças. / The problems of optimal cutting are considered as classic within the operational research, given their large area of application in industry and their high computational and mathematic complexity. One of the most well-known of this kind of problem is called the Cutting Stock Problem, which allows to divide a plate in several pieces of various sizes, in order to obtain the configuration that maximizes the area of the plate being used. Given the level of difficulty and the large number of applications of this problem in several areas, there is interest in creating new efficient procedures for solving this kind of problem. In this dissertation, it is presented the state of the art of the two-dimensional cutting problems of rectangular pieces on a single plate, in several plates and rollers, considering the possibility of rotating the pieces at an angle of 90 in which the cuts are restricted to non-guillotined type. Furthermore, the mathematical approaches applied by different researchers dedicated to solving these problems are described. This work is focused exclusively on solving the Cutting Stock Problem with and without rotating pieces. Therefore, a kind of binary encoding in order to be applied to this kind of problem and to solving it through the use of the Bottom-Left heuristic algorithm in conjunction with Simulated Annealing are proposed. Finally, to prove the efficiency of the presented methodology, some study cases from the specialized literature were used, with different levels of complexity. For each case, the results are presented and a comparison of the proposed solution methods for solving the Cutting Stock Problem with and without rotating pieces is performed.

Orientador: Silvio Alexandre de Araujo / Banca: Sônia Cristina Poltronieri da Silva / Banca: Maria do Socorro Nogueira Rangel / Resumo: Neste trabalho estudamos o processo produtivo de uma fábrica de móveis característica do Pólo Moveleiro de Votuporanga/SP e propomos um modelo de otimização inteira mista para o processo de produção desta fábrica acoplando o Problema de Dimensionamento de Lotes (PDL) com o Problema de Corte de Estoque (PCE) Bidimensional. O modelo considera vários itens (produtos finais), horizonte rolante de planejamento, sendo que somente o período inicial é programado detalhadamente em relação às restrições de atendimento à demanda por peças e de capacidade das máquinas. Dois conjuntos de padrões de corte são utilizados, aqueles preferidos pela empresa e um conjunto de padrões tabuleiros compostos, e visa a utilização da capacidade total de corte da máquina seccionadora. Testes computacionais fazendo várias comparações foram realizados e mostram a eficiência da abordagem quando o problema é resolvido de forma integrada e quando o conjunto de padrões de corte tabuleiros compostos é utilizado. / Abstract: In this work we studied the production process of a furniture company located in Votuporanga/SP and we propose a mixed-integer optimization model for the furniture industry production process, integrating the Lot Sizing Problem with the Cutting Stock Problem. The mathematical model considers multi items (final products) in a rolling horizon basis, where only the initial period is detailed with respect to the pieces demanded and capacity machines constraints. Two cutting pattern sets are used, the industry preferred cutting patterns and a set of composed checkerboard patterns, and aims at using the total capacity of the saw machine use. Computational tests with multiple comparisons show the approach effectiveness when the problem is solved in an integrated form and when the composed checkerboard patterns set is used. / Mestre

Orientador: Maria do Socorro Nogueira Rangel / Banca: Silvio Alexandre de Araujo / Banca: Kelly Cristina Poldi / Resumo: Neste trabalho apresentamos o problema de corte de estoque (PCE) e algumas de suas características e propriedades. Abordamos com mais detalhes o problema de corte de estoque bidimensional, guilhotinado, 2-estágios, exato e não-exato. Exibimos o modelo matemático do PCE e o método de geração de colunas proposto por Gilmore e Gomory na década de $60$. Apresentamos duas heurísticas residuais da literatura e sugerimos mudanças no método da ordenação dos padrões de corte de uma delas. Implementamos todo o algoritmo das heurísticas residuais utilizadas, realizamos testes computacionais usando três conjuntos de instâncias da literatura. As instâncias do Conjunto 1 foram geradas aleatoriamente e as dos Conjuntos 2 e 3 foram baseados em dados reais de uma fábrica de móveis. Os resultados obtidos com as heurísticas residuais foram comparadas com resultados disponíveis na literatura e resultados do Sistema CorteBiFur e do método branch-and-cut disponível no Cplex. Os resultados do estudo computacional indicam que a heurística residual estudada se mostra uma boa alternativa para ser implementada no sistema CorteBiFur / Abstract: In this research we presented the cutting stock problem (CSP), and some of its features and properties. The focus is the two-dimensional cutting stock problem, considering guillotine cuts and, two-staged cutting patterns and the exact and non-exact cases. We exhibit a mathematical model for the CSP and a method for its solution proposed by Gilmore and Gomory in the 1960's. We present two residual heuristics from the literature and we suggest some changes on the criterion of sorting the cutting patterns in one of them. We implemented all the heuristics used in this research. We performed computacional tests with three sets of instances available in the literature. The instances of the Set 1 were randomly generated and the instances of the Sets 2 e 3 were based on real data from a furniture industry. The results obtained with the residuals heuristics were compared with results avaiable in the literature, with results from the Software CorteBiFur and the branch-and-cut method available on Cplex. The results indicated that the residual heuristic we studied its a good choice to be implemented on the CorteBiFur / Mestre

Orientador: Maria do Socorro Nogueira Rangel / Banca: Valeriano Antunes de Oliveira / Banca: Flávio Molina da Silva / Resumo: Nessa dissertação é feito uma revisão das características gerais dos problemas de corte e empacotamento e apresentam-se duas tipologias encontradas da literatura para classificar os problemas. São estudados em detalhes três problemas: (i) o problema da mochila limitada, (ii) o problema de corte bidimensional guilhotinado 2estágios restrito, e (iii) o problema do corte de estoque bidimensional. Para o problema (i) é proposto um algoritmo de programação dinâmica adaptado de um algoritmo proposto na literatura. Esse algoritmo é a base para a proposta de duas estratégias para resolver o problema (ii). Os algoritmos desenvolvidos para o problema (ii) são então usados no processo de geração de colunas usado para resolver o problema de corte de estoque exato. Resultados de um estudo computacional realizado para avaliar o desempenho dos algoritmos propostos usando instâncias da literatura são apresentados e analisados / Abstract: In this dissertation a review of the main characteristics of the Cutting and Packing problems are presented together with a summary of two typologies proposed in the literature to classify the problems. Three problems are studied in detail: (i) the Bounded Knapsack problem, (ii) the constraint two-dimensional guillotine 2-stage cutting problem, and (iii) the two-dimensional cutting stock problem. For problem (i) we propose a dynamic programming algorithm adapted from one given in the literature. This algorithm is the basis for the proposal of two strategies to solve the problem (ii). The algorithms developed for problem (ii) are then used in the column generation process employed to solve the exact cutting stock problem. Results of a computational study conducted to evaluate the performance of the proposed algorithms using instances of the literature are presented and analyzed / Mestre

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

Orientador: Silvio Alexandre de Araujo / Coorientadora: Adriana Cristina Cherri / Banca: Sonia Cristina Poltrooniere Silva / Banca: Roberto Fernandes Tavares Neto / Resumo: Dois problemas fundamentais surgem no planejamento da produção de muitos processos produtivos: o problema de dimensionamento de lotes e o problema de corte de estoque. Geralmente, as empresas tratam estes problemas separadamente, porém, ao considerá-los de maneira integrada, é possível obter melhores resultados. Neste trabalho, investiga-se o problema integrado de dimensionamento de lotes e corte de estoque tridimensional aplicado a uma indústria de colchões, visando à redução de custos e desperdícios. É proposto um modelo matemático de programação inteira mista para a resolução do problema. Testes computacionais com base em dados coletados em uma indústria do setor foram realizados, permitindo comparar as soluções obtidas pelo modelo e as soluções adotadas pela indústria. Testes adicionais foram realizados com dados aleatórios, a fim de avaliar o comportamento do modelo para diferentes casos. Os resultados indicam que o modelo apresenta um bom desempenho, reduzindo os custos da função objetivo para diferentes conjuntos de testes. Com base nos resultados, algumas direções interessantes podem ser exploradas pela indústria, como por exemplo, ao aumentar o número de padrões de corte, aumenta-se o número de combinações possíveis para o corte, resultando em melhor aproveitamento de material e redução nos custos. / Abstract: Two fundamental problems arise in the production planning of many productive processes: the lot-sizing problem and the cutting stock problem. Generally, companies deal with these problems separately, but by considering them in an integrated way, it is possible to obtain better results. In this paper, the integrated lot-sizing and three-dimensional cutting stock problem applied to a mattress industry is investigated, aiming at reducing costs and waste. It is proposed a mathematical model of mixed integer programming for the problem resolution. Computational tests based on data collected in an industry of the sector were carried out, allowing to compare the solutions obtained by the model and the solutions adopted by the industry. Additional tests were performed with random data in order to evaluate the behaviour of the model for different cases. The results indicate that the model performs well, reducing the objective function costs for different sets of tests. Based on the results, some interesting directions can be explored by the industry, for example, by increasing the number of cutting patterns, the number of possible combinations for cutting is increased, resulting in better material utilization and reduction in costs. / Mestre

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-03-15Bitstream added on 2014-06-13T20:09:18Z : No. of bitstreams: 1 longhi_al_me_sjrp.pdf: 570095 bytes, checksum: 5a30b272ec5bfcb3379a569e16f72a50 (MD5) / Os problemas de dimensionamento de lotes e corte de estoque unidimensional têm importante papel em diversos setores industriais, tais como, fábricas de móveis tubulares e de papel, metalurgicas, entre outros e geralmente são tratados de maneira indepen-dente. Neste trabalho, abordamos os dois problemas de maneira integrada. Estudamos um modelo clássico do problema de dimensionamento de lotes, bem como, sua reformu-lação baseada no problema de caminho mínimo. Para o problema de corte de estoque unidimensional, foram estudados três diferentes modelos matemáticos propostos na lite-ratura. Apresentamos os modelos estudados de maneira integrada e fizemos um estudo computacional, utilizando dados gerados aleatoriamente, comparando os diferentes mo-delos para o problema integrado / The lot-sizing and the one-dimensional cutting-stock problems have an important role in the production sector, such as, tubular furniture and paper factories, metallurgi-cal, among others and generally are dealt independently. In this work, we approach both problems in an integrated way. We studied a classical model for lot sizing problem and its reformulation based on the shortest path problem. For the one-dimensional cutting stock problem, three different models proposed in the literature were studied. We present the studied models in an integrated way and we made a computacional study using randomly generated data, comparing the different models for the integrated problem

Orientador: Silvio Alexandre de Araujo / Banca: Marcos Nereu Arenales / Banca: Maria do Socorro Nogueira Rangel / Resumo: Os problemas de dimensionamento de lotes e corte de estoque unidimensional têm importante papel em diversos setores industriais, tais como, fábricas de móveis tubulares e de papel, metalurgicas, entre outros e geralmente são tratados de maneira indepen-dente. Neste trabalho, abordamos os dois problemas de maneira integrada. Estudamos um modelo clássico do problema de dimensionamento de lotes, bem como, sua reformu-lação baseada no problema de caminho mínimo. Para o problema de corte de estoque unidimensional, foram estudados três diferentes modelos matemáticos propostos na lite-ratura. Apresentamos os modelos estudados de maneira integrada e fizemos um estudo computacional, utilizando dados gerados aleatoriamente, comparando os diferentes mo-delos para o problema integrado / Abstract: The lot-sizing and the one-dimensional cutting-stock problems have an important role in the production sector, such as, tubular furniture and paper factories, metallurgi-cal, among others and generally are dealt independently. In this work, we approach both problems in an integrated way. We studied a classical model for lot sizing problem and its reformulation based on the shortest path problem. For the one-dimensional cutting stock problem, three different models proposed in the literature were studied. We present the studied models in an integrated way and we made a computacional study using randomly generated data, comparing the different models for the integrated problem / Mestre

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

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2008-02-27Bitstream added on 2014-06-13T19:47:35Z : No. of bitstreams: 1 santos_smpg_me_sjrp.pdf: 975189 bytes, checksum: 365d7872dbad44341fdaa7290f787b15 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho estudamos o processo produtivo de uma fábrica de móveis característica do Pólo Moveleiro de Votuporanga/SP e propomos um modelo de otimização inteira mista para o processo de produção desta fábrica acoplando o Problema de Dimensionamento de Lotes (PDL) com o Problema de Corte de Estoque (PCE) Bidimensional. O modelo considera vários itens (produtos finais), horizonte rolante de planejamento, sendo que somente o período inicial é programado detalhadamente em relação às restrições de atendimento à demanda por peças e de capacidade das máquinas. Dois conjuntos de padrões de corte são utilizados, aqueles preferidos pela empresa e um conjunto de padrões tabuleiros compostos, e visa a utilização da capacidade total de corte da máquina seccionadora. Testes computacionais fazendo várias comparações foram realizados e mostram a eficiência da abordagem quando o problema é resolvido de forma integrada e quando o conjunto de padrões de corte tabuleiros compostos é utilizado. / In this work we studied the production process of a furniture company located in Votuporanga/SP and we propose a mixed-integer optimization model for the furniture industry production process, integrating the Lot Sizing Problem with the Cutting Stock Problem. The mathematical model considers multi items (final products) in a rolling horizon basis, where only the initial period is detailed with respect to the pieces demanded and capacity machines constraints. Two cutting pattern sets are used, the industry preferred cutting patterns and a set of composed checkerboard patterns, and aims at using the total capacity of the saw machine use. Computational tests with multiple comparisons show the approach effectiveness when the problem is solved in an integrated form and when the composed checkerboard patterns set is used.