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.

Made available in DSpace on 2016-05-17T16:51:25Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-08-22. Added 1 bitstream(s) on 2016-05-17T16:55:01Z : No. of bitstreams: 1 000864107.pdf: 1967063 bytes, checksum: b6a04d735d1964d6dfeb7d1495b12ed3 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Os Problemas de Corte de Estoque (PCE) são frequentemente encontrados em indústrias moveleiras, onde deseja-se cortar objetos maiores (placas de madeira) em objetos menores (itens), cada qual com uma quantidade pré-estabelecida (demanda), a fim de que seja possível a construção de diversos produtos finais demandados. O foco deste trabalho é a solução dos PCE bidimensionais, em que duas dimensões são relevantes durante o processo de corte, utilizando diferentes métodos para elaborar maneiras distintas de se cortar um único objeto em estoque (elaboração de padrões de corte). Devido às diferentes prioridades que se tem dentro de uma indústria moveleira, pode ser que seja necessário cortar placas de madeira mais rapidamente para que os produtos sejam fabricados com maior agilidade. No entanto, esta rapidez na produção pode gerar maior perda de matéria-prima, ocasionando maiores gastos no processo produtivo. Para possibilitar a solução computacional desse problema foi desenvolvido um código computacional e alguns resultados são apresentados. É realizado um estudo comparativo entre a solução encontrada na prática de uma fábrica real de móveis com a solução encontrada neste trabalho. Os dados utilizados foram extraídos de uma empresa localizada na cidade de Jaci, no interior do estado de São Paulo, considerada de médio porte e que atende o mercado moveleiro a nível nacional / The Cutting Stock Problems (CSP) are generally found in furniture industry, where is need to cut larger objects (wooden boards) into smaller objects (items), each one with a specific amount (demand), in order to produce several final products. The focus of this work is to solve the two-dimensional CSP, where two dimensions are relevant during the cutting process, using different methods to create different ways to cut a single object in stock (development of cutting patterns). Due to the different priorities that have in a furniture industry, sometimes could be necessary to cut wooden boards more quickly to make products as fast as possible. However, this agility in production process may generate greater loss of raw materials, making the manufacturing process more expensive. In order to present a computational solution to the problem, was developed a computational code and some computational results are presented. A comparative study is carried out with a solution found in the practice of real furniture factory and a solution found at this work. The data was obtained from a company located in Jaci, in the state of Sao Paulo, considered medium-sized and deal with furniture market at national level

Orientador: Silvio Alexandre de Araujo / Banca: Maria do Socorro Nogueira Rangel / Banca: Adriana Cristina Cherri / Resumo: Os Problemas de Corte de Estoque (PCE) são frequentemente encontrados em indústrias moveleiras, onde deseja-se cortar objetos maiores (placas de madeira) em objetos menores (itens), cada qual com uma quantidade pré-estabelecida (demanda), a fim de que seja possível a construção de diversos produtos finais demandados. O foco deste trabalho é a solução dos PCE bidimensionais, em que duas dimensões são relevantes durante o processo de corte, utilizando diferentes métodos para elaborar maneiras distintas de se cortar um único objeto em estoque (elaboração de padrões de corte). Devido às diferentes prioridades que se tem dentro de uma indústria moveleira, pode ser que seja necessário cortar placas de madeira mais rapidamente para que os produtos sejam fabricados com maior agilidade. No entanto, esta rapidez na produção pode gerar maior perda de matéria-prima, ocasionando maiores gastos no processo produtivo. Para possibilitar a solução computacional desse problema foi desenvolvido um código computacional e alguns resultados são apresentados. É realizado um estudo comparativo entre a solução encontrada na prática de uma fábrica real de móveis com a solução encontrada neste trabalho. Os dados utilizados foram extraídos de uma empresa localizada na cidade de Jaci, no interior do estado de São Paulo, considerada de médio porte e que atende o mercado moveleiro a nível nacional / Abstract: The Cutting Stock Problems (CSP) are generally found in furniture industry, where is need to cut larger objects (wooden boards) into smaller objects (items), each one with a specific amount (demand), in order to produce several final products. The focus of this work is to solve the two-dimensional CSP, where two dimensions are relevant during the cutting process, using different methods to create different ways to cut a single object in stock (development of cutting patterns). Due to the different priorities that have in a furniture industry, sometimes could be necessary to cut wooden boards more quickly to make products as fast as possible. However, this agility in production process may generate greater loss of raw materials, making the manufacturing process more expensive. In order to present a computational solution to the problem, was developed a computational code and some computational results are presented. A comparative study is carried out with a solution found in the practice of real furniture factory and a solution found at this work. The data was obtained from a company located in Jaci, in the state of Sao Paulo, considered medium-sized and deal with furniture market at national level / Mestre

Orientador: Silvio Alexandre de Araujo / Banca: Maria do Socorro Nogueira Rangel / Banca: Kelly Cristina Poldi / Banca: Sonia Cristina Poltroniere Silva / Banca: Deisemara Ferreira / Resumo: Nesta tese, estamos interessados em tratar de maneira integrada dois conhecidos problemas da literatura. Esta integração é referida na literatura como problema integrado de dimensionamento de lotes e corte de estoque. A ideia consiste em considerar simultaneamente, as decisões relacionadas com ambos os problemas, de modo a capturar a interdependência entre estas decisões e, assim, obter uma melhor solução global. Propõe-se um modelo matemático geral para o problema integrado de dimensionamento de lotes e corte de estoque (GILSCS), que considera vários níveis de integração e nos permite classificar a literatura, em termos de modelos matemáticos, dos problemas integrados. A classificação é organizada a partir de dois principais aspectos de integração que são: a integração através dos períodos de tempo e a integração entre os níveis de produção. Em um horizonte de planejamento que considera vários períodos, o estoque fornece uma ligação entre os períodos. Esta integração, por períodos de tempo, constitui o primeiro tipo de integração. O problema geral também considera a produção em diferentes níveis: objetos são fabricados ou comprados e então são cortados para produzir peças menores e estas, por sua vez, constituem componentes para a produção dos produtos finais. A integração entre os diferentes níveis de produção consiste no segundo tipo de integração. A revisão da literatura também possibilita direcionar interessantes áreas para pesquisas futuras. O comportamento da solução... / Abstract: In this thesis, the subject of interest is in treating, in an integrated way, two wellknown problems in the literature. This integration is referred in the literature as the integrated lot-sizing and cutting stock problem. The basic idea is to consider, simultaneously, the decisions related to both problems so as to capture the interdependency between these decisions in order to obtain a better global solution. We propose a mathematical model for a general integrated lot-sizing and cutting stock (GILSCS) problem. This model considers multiple dimensions of integration and enables us to classify the current literature, in terms of mathematical models, in this field. The main classification of the literature is organized around two types of integration. In a planning horizon which consists of multiple periods, the inventory provides a link between the periods. This integration across time periods constitutes the first type of integration. The general problem also considers the production in different levels: objects are fabricated or purchased and then, they are cut to produce the pieces which are then assembled as components in the production of final products. The integration between these production levels constitutes the second type of integration. The literature review also enables us to point out interesting areas for future research. The behavior of a solution to this type of problem, with three levels of production and several time periods, is studied considering the ... / Doutor