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

Made available in DSpace on 2014-12-02T11:16:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-05-13Bitstream added on 2014-12-02T11:20:50Z : No. of bitstreams: 1 000796058.pdf: 2888477 bytes, checksum: aeb48d13f2d71aae91a21d050cd51b93 (MD5) / O presente trabalho propõe uma análise sobre os problemas de corte e empacotamento com restrições práticas que representam cenários reais na indústria. Em síntese o problema de corte consiste em cortar um conjunto de peças de um determinado objeto, e o problema de empacotamento consiste em alocar um conjunto de peças dentro de um objeto. No mundo real se apresenta uma grande quantidade de variações destes problemas. Neste estudo limitamo-nos a estudar os problemas com peças e objetos com formas regulares, restringindo assim os problemas de duas dimensões ao uso de retângulos e aos problemas de três dimensões ao uso de paralelepípedos. De forma específica os problemas de corte estudados neste trabalho são o problema da mochila bidimensional (2D-SLOPP, do inglês Two-Dimensional Single Large Object Placement Problem) com restrições de padrão de corte; valores associados às peças; limites de exemplares por peça e orientação das peças. O segundo problema a ser estudado, é o problema da embalagem (2D-SBSBPP, do inglês Two-Dimensional Single Bin Size Bin Packing Problem) com restrições de padrões de corte tipo guilhotina e restrições de orientação das peças. Finalmente, o problema de empacotamento estudado no presente trabalho é o problema do carregamento de um único contêiner (3D-SKP ou 3D-SLOPP, do inglês Three-Dimensional Single Knapsack Problem e Three-Dimensional Single Large Object Placement Problem, respectivamente) com restrições de orientação das caixas; limites de resistência das caixas ao empilhamento; limite de peso do carregamento suportado pelo contêiner; estabilidade do padrão de carregamento e carga divida em múltiplos destinos. Estes três problemas apresentados são de grande interesse para a indústria, graças a isto, atualmente existe uma ampla literatura especializada de trabalhos referentes a esta temática. Logo, diferentes tipos de ... / In this work we study the cutting and packing problems with practical constraints that represent real world scenarios of the industry. The cutting problem consists in to cut a set of pieces from an object, and the packing problem consists in to pack a set of items in an object. In the real world there are a big number of variations of this problem. In this study we only carry out the problems where the pieces and the objects have a regular shape, bounding of that way the two-dimensional problems to use just rectangular items and the three-dimensional problems to use just parallelepiped pieces. Specifically, the cutting problems studied in this work are: the Two-Dimensional Single Knapsack Problem, taking into account cutting pattern constraints (guillotine and non-guillotine patterns), orientation of the pieces constraints, associated costs to the pieces constraints and demanding types of pieces constraints. The second problem that we work on is the Two-Dimensional Single Bin Size Packing Problem, taking into account cutting pattern constraints (only guillotine patterns) and orientation pieces constraints. The last problem is the Container Loading Problem (Three- Dimensional Single Large Object Placement Problem) taking into account: orientation box constraints, load-bearing strength constraints, cargo stability constraints (full support) and multi-drop constraints. All the previous problems have a big spectrum of application on the Industry, because of this; there is a big amount of previous work on it. Different methodologies, exact and approximate algorithms have been proposed as solution strategies. Due to the mathematical and computational complexity of these problems, the exact algorithms cannot solve real world instances of the problem. The approach of this study consists on presenting and/or adapting different encodings and optimization algorithms. Among the proposed approach solutions is ...

Made available in DSpace on 2016-06-02T19:51:24Z (GMT). No. of bitstreams: 1 DissAA_2.pdf: 2467441 bytes, checksum: 3618b64c429e59e38fbf9929c981ad63 (MD5) Previous issue date: 2006-12-07 / Financiadora de Estudos e Projetos / The Cutting Stock Problem consists of determining the best form to cut units of material (objects in supply), producing a set of lesser units (demanded item), with specific dimensions, that are ordered through an order wallet. To minimize the loss of material this study described a method of evaluation and optimization of the process planning of the cutting of metallic structural tubes used in the manufacturing of small aircrafts for the agricultural aeronautic industry. In order, to support the decisions in the cutting process it was developed an optimization approach based on mathematical mixed integer programming models. The mathematic models are resolved in GAMS/CPLEX, using the production data of Neiva, an aeronautical company subsidiary of Embraer. The results showed that it is possible obtain significant profits in the production in with the application of mathematical models in the process of cut in the aeronautic industry. Mathematical models have a potential to generate beneficial solutions in the production process reducing the costs of production with the re-use of the leftovers. / O objetivo deste estudo foi avaliar e otimizar o planejamento do processo de corte de tubos estruturais metálicos utilizados na fabricação de aeronaves leves voltadas ao segmento de mercado agrícola. Através do enfoque sistêmico da Pesquisa Operacional, buscamos a possibilidade de minimizar as perdas de material e gerar retalhos cujas dimensões permitam sua posterior utilização. Foi desenvolvida uma abordagem de otimização baseada em programação matemática linear inteira mista, para apoiar as decisões no processo de corte. Os modelos estudados abrangem os objetivos propostos, incluindo o critério de minimizar os custos com as perdas do material e a possibilidade de gerar sobras com tamanho suficiente para reaproveitamento. Utilizando-se a linguagem de modelagem GAMS e o solver CPLEX, os modelos resolveram exemplos destacados da prática da empresa Neiva, localizada em Botucatu/SP, subsidiária da empresa aeronáutica Embraer. Inclusive com uma abordagem multi-períodos, esses exemplos mostram o potencial dos modelos para gerar soluções melhores que as atualmente utilizadas pela empresa, em um tempo computacional admissível.