Um importante problema de programação da produção surge em indústrias de papel integrando o problema de planejamento em múltiplas máquinas paralelas com o problema de corte. O problema de dimensionamento de lotes deve determinar a quantidade de jumbos (bobinas grandes de papel) de diferentes tipos de papel a serem produzidos em cada máquina. Estes jumbos são então cortados para atender a demanda de itens (bobinas menores de papel). O planejamento, que minimiza custos de produção e preparação, deve produzir jumbos (cada máquina produz jumbos de larguras diferentes) que diminuam a perda no processo de corte. Por outro lado, o melhor número de jumbos do ponto de vista de minimizar a perda no processo de corte pode acarretar em altos custos de preparação. Ambos são problemas de otimização combinatória não trivial, o que tem motivado extensas pesquisas nas últimas décadas, entretanto, essa combinação não é bem explorada na literatura. Neste trabalho, são propostos um modelo de otimização integrado e métodos heurísticos de solução. Foram realizados experimentos computacionais com o intuito de analisar o desempenho dos métodos propostos e os resultados apresentaram- se bastante satisfatórios, significando que tais métodos são apropriados para tratar o problema integrado. / An important production programming problem arises in paper industries coupling mul- tiple machine scheduling with cutting stock. From machine scheduling the problem of determining the quantity of jumbos (large rolls of paper) of different types of paper to be produced in each machine arises. These jumbos are then cut to meet the demand for items (smaller rolls of paper). Scheduling that minimizes setups and production costs may produce jumbos (each machine produces jumbos of a specific width) which may increase waste in the cutting process. On the other hand, the best number of jumbos in the point of view of minimizing waste in the cutting process may lead to high setup costs. Both problems are non-trivial combinatorial optimization problems, which have motivated ex- tensive research in the last decades, however their combination is not well explored in the literature. In this work, a coupled optimization modelling and heuristic solution methods are proposed. Computational experiments are devised in order to analyze the performance of the methods and the results had been presented sufficiently satisfactory, meaning that such methods are appropriate to deal with the integrated problem.

O planejamento da produção em indústrias moveleiras de pequeno porte é comumente constituído por decisões referentes ao volume de produção e à política de estoque, com o objetivo de minimizar o desperdício de material, os atrasos e as horas-extras utilizadas ao longo do horizonte de planejamento. Administrar tais decisões de uma maneira tratável e eficiente é, em geral, um desafio, especialmente considerando a natureza incerta dos dados. Nessa tese, são desenvolvidos modelos de otimização para apoiar tais decisões no contexto do problema combinado de dimensionamento de lotes e corte de estoque sob incertezas que surge em indústrias moveleiras. Para lidar com as incertezas dos dados, são investigadas duas metodologias: programação estocástica e otimização robusta. Dessa maneira, são propostos modelos de programação estocástica de dois estágios com recurso, assim como modelos estocásticos robustos que incorporam aversão ao risco. A motivação em também desenvolver modelos baseados em otimização robusta é considerar casos práticos em que não há uma descrição probabilística explícita dos dados de entrada, assim como evitar trabalhar com numerosos cenários, o que pode tornar o modelo estocástico computacionalmente intratável. Os experimentos numéricos baseados em exemplares reais de uma empresa moveleira de pequeno porte mostram que as soluções obtidas pelos modelos de programação estocástica fornecem planos de produção robustos e que o (a) decisor (a) pode designar suas preferências em relação ao risco aos modelos, assim como controlar o tradeoff entre o custo total esperado e a robustez da solução. Em relação aos resultados dos modelos de otimização robusta, são obtidos alguns insights entre os chamados budgets de incerteza, as taxas de atendimento da demanda e os valores ótimos. Além disso, evidências numéricas indicam que budgets de incerteza menos conservadores resultam em níveis de serviço razoáveis com baixos custos globais, enquanto a abordagem de pior caso gera, relativamente, boas taxas de atendimento da demanda, mas com custos globais elevados / Production planning procedures in small-size furniture companies commonly consist of decisions with respect to production level and inventory policy, while attempting to minimize trim-loss, backlogging and overtime usage throughout the planning horizon. Managing these decisions in a tractable and efficient way is often a challenge, especially when the uncertainty of data is taken into account. In this thesis, we develop optimization models to support these decisions in the context of the combined lot-sizing and cutting-stock problem that arises in furniture companies. To deal with data uncertainty, we investigate two methodologies: stochastic programming and robust optimization. In the former case, we propose two-stage stochastic programming models with recourse, as well as robust stochastic models to incorporate risk-aversion. In the latter case, our motivation to investigate robust optimization models is the lack of an explicit probabilistic description of the input data. Furthermore, we want to avoid dealing with a large number of scenarios, which typically lead to computationally intractable stochastic programming models. Numerical experiments based on real data from a small-size furniture plant show that the solutions of the stochastic programming models provide robust production plans so that the decision-maker can assign his or her risk preferences to the model and control the tradeoff between the expected total cost and solution robustness. Regarding the results from the robust optimization models, we provide some insights into the relationship among budgets of uncertainty, fill rates and optimal values. Moreover, numerical evidence indicate that less conservative budgets of uncertainty result in reasonable service levels with cheaper global costs, while worst case deterministic approaches lead to relatively good fill rates, but with prohibitive global costs

O presente trabalho desenvolve uma extensão do problema de corte de estoque unidimensional no caso em que a demanda pelos vários tipos de itens não é exatamente conhecida. Para considerar a aleatoriedade, foi proposto um modelo de programação estocástica de dois estágios com recurso. As varáveis de primeiro estágio são os números de barras cortadas por padrão de corte, e as variáveis de segundo estágio, os números de itens produzidos em escassez e em escassez. O objetivo do modelo é minimizar o custo total esperado. Para resolver a relaxação linear do modelo, foram propostos um método exato baseado no método Simplex com geração de colunas e uma estratégia heurística, que considera o valor esperado da demanda na resolução do problema de corte de estoque. As duas estratégias foram comparadas, assim como a possibilidade de resolver o problema de corte ignorando as incertezas. Finalmente, observou-se que é mais interessante determinar o valor ótimo do modelo recurso quando o problema sofre mais influência da aleatoriedade / This paper presents an integer linear optimization model of large scale for the one-dimensional cutting stock problem in the case which a demand is considered a random variable. To take this randomness into account, the problem was formulated as a two-stage stochastic linear program with recourse. The first stage decision variables are given by the number of bars that has to be cut according to each pattern, and the second stage decision variables by the number of holding items or backordering items production. The model objective is minimizes the total expected cost. We propose two methods to solve the model linear relaxation, one of them it is a Simplex-based method with column generation. The second method is a heuristic strategy that adopted the expected value of demand. We compare both strategies and the possibly of ignoring uncertainties on model. Finally, we observe that is much more interesting to determine the optimal recourse model solution when we have problems that are more afected by randomness

O planejamento da produção em indústrias moveleiras de pequeno porte é comumente constituído por decisões referentes ao volume de produção e à política de estoque, com o objetivo de minimizar o desperdício de material, os atrasos e as horas-extras utilizadas ao longo do horizonte de planejamento. Administrar tais decisões de uma maneira tratável e eficiente é, em geral, um desafio, especialmente considerando a natureza incerta dos dados. Nessa tese, são desenvolvidos modelos de otimização para apoiar tais decisões no contexto do problema combinado de dimensionamento de lotes e corte de estoque sob incertezas que surge em indústrias moveleiras. Para lidar com as incertezas dos dados, são investigadas duas metodologias: programação estocástica e otimização robusta. Dessa maneira, são propostos modelos de programação estocástica de dois estágios com recurso, assim como modelos estocásticos robustos que incorporam aversão ao risco. A motivação em também desenvolver modelos baseados em otimização robusta é considerar casos práticos em que não há uma descrição probabilística explícita dos dados de entrada, assim como evitar trabalhar com numerosos cenários, o que pode tornar o modelo estocástico computacionalmente intratável. Os experimentos numéricos baseados em exemplares reais de uma empresa moveleira de pequeno porte mostram que as soluções obtidas pelos modelos de programação estocástica fornecem planos de produção robustos e que o (a) decisor (a) pode designar suas preferências em relação ao risco aos modelos, assim como controlar o tradeoff entre o custo total esperado e a robustez da solução. Em relação aos resultados dos modelos de otimização robusta, são obtidos alguns insights entre os chamados budgets de incerteza, as taxas de atendimento da demanda e os valores ótimos. Além disso, evidências numéricas indicam que budgets de incerteza menos conservadores resultam em níveis de serviço razoáveis com baixos custos globais, enquanto a abordagem de pior caso gera, relativamente, boas taxas de atendimento da demanda, mas com custos globais elevados / Production planning procedures in small-size furniture companies commonly consist of decisions with respect to production level and inventory policy, while attempting to minimize trim-loss, backlogging and overtime usage throughout the planning horizon. Managing these decisions in a tractable and efficient way is often a challenge, especially when the uncertainty of data is taken into account. In this thesis, we develop optimization models to support these decisions in the context of the combined lot-sizing and cutting-stock problem that arises in furniture companies. To deal with data uncertainty, we investigate two methodologies: stochastic programming and robust optimization. In the former case, we propose two-stage stochastic programming models with recourse, as well as robust stochastic models to incorporate risk-aversion. In the latter case, our motivation to investigate robust optimization models is the lack of an explicit probabilistic description of the input data. Furthermore, we want to avoid dealing with a large number of scenarios, which typically lead to computationally intractable stochastic programming models. Numerical experiments based on real data from a small-size furniture plant show that the solutions of the stochastic programming models provide robust production plans so that the decision-maker can assign his or her risk preferences to the model and control the tradeoff between the expected total cost and solution robustness. Regarding the results from the robust optimization models, we provide some insights into the relationship among budgets of uncertainty, fill rates and optimal values. Moreover, numerical evidence indicate that less conservative budgets of uncertainty result in reasonable service levels with cheaper global costs, while worst case deterministic approaches lead to relatively good fill rates, but with prohibitive global costs

O problema de corte de estoque consiste em cortar objetos maiores, disponíveis em estoque, para produzir uma quantidade especificada de peças menores, de modo que uma certa função objetivo seja otimizada. Um modelo de otimização linear tem sido amplamente utilizado na solução deste problema desde os anos 60, que incorpora parte da estrutura combinatória inerente ao problema na construção das colunas da matriz de restrições. As colunas são construídas a cada iteração do Método Simplex, chamando-se geração de colunas. Apesar do método Simplex ser largamente utilizado para este tipo de problema, apresenta baixa convergência quando próximo da otimalidade, pouco melhorando a função objetivo. Assim, estratégias para aceleração do Método Simplex faz-se necessário, uma maneira consiste na redução do espaço dual, com a introdução de restrições (colunas no primal) que evite grandes variações nas variáveis duais, chamadas cortes duais. Neste trabalho, generalizamos duas famílias de cortes duais recentemente publicadas e analisamos o impacto computacional desses cortes duais sobre a convergência do Método Simplex / The cutting stock problem consists of cutting large available objects in stock to produce a quantity of ordered smaller itens, in such a way as to optimize a given objective function. A linear optmizatim model has been widely used to solve this problem since the 60s, in which part of a combinatorial structure of the problem is embedded. The columns of the constraint matrix are generated in each iteration of the Simplex Method, called the column generation technique. Although, the Simplex Method is widely used, it has a low convergence near to optimality. In this way, strategies to accelerate the Simplex Method are welcome which can be obtained by adding dual cuts (primal columns). The goal of this work is to study published dual cuts and to proposed others. In this book us extend two families of dual cuts, which were recently published, and analyse the computational impact of these dual cuts on the converge of the Simplex Method

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-13T18:55:34Z : No. of bitstreams: 1 faccio_ap_me_sjrp.pdf: 1095275 bytes, checksum: ec84ac0e5bcbf1c37d9ca5d883c46a81 (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Neste trabalho, estudamos o problema de corte de estoque bidimensional aplicado ao corte da matéria-prima de uma fábrica de móveis. Este problema NP-difícil aparece em diversos outros processos industriais que incluem o corte de objetos retangulares grandes em itens retangulares menores que estão sendo requisitados. Analisamos a eficiência de alguns modelos lineares inteiros para problemas de corte guilhotinados bidimensionais propostos na literatura. Além disto, apresentamos resultados computacionais para o problema de corte de estoque de uma fábrica de móveis de pequeno porte, localizada no noroeste do estado de São Paulo. O estudo computacional realizado mostrou que as estratégias propostas fornecem resultados aceitáveis pela fábrica. / In this work we study the two-dimensional cutting stock problem applied to the cutting of raw material in the furniture industry. This NP-hard problem appears in several other industrial processes that include cutting rectangular objects in smaller retangular items that are being requested. We analyze the efficiency of some integer linear models for two-dimensional guillotine cutting problem proposed in the literature. We also present computational results for the cutting stock problem of a small furniture factory, located in the northwest of the state of São Paulo. The computational results show that the proposed strategies give results accepted by the factory.

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2004-07-30Bitstream added on 2014-06-13T20:55:45Z : No. of bitstreams: 1 cavali_r_me_sjrp.pdf: 560996 bytes, checksum: 6792ea8d0dd5f26eb5250b68217a4443 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Diariamente, em indústrias de móveis, painéis retângulares de madeira são cortados em retângulos menores para a manufatura de seus produtos. Por causa da possível perda de material envolvida neste processo e de sua influência no custo dos produtos, existe a necessidade de um planejamento prþevio para a realização dos cortes. Na maioria das empresas de móveis situadas na região Noroeste do estado de São Paulo, este planejamento é feito manualmente e não é uma tarefa simples. O enfoque deste trabalho þe analisar a utilização de um sistema computacional no planejamento do corte de painéis de madeira. Esta ferramenta é capaz de resolver o problema do corte bidimensional segundo o algoritmo de dois estþagios de Gilmory e Gomore. Aspectos práticos encontrados no corte dos painéis e estratégias adotadas pelas empresas no planejamento da produção são abordados. Além disso, apresentamos os resultados de um estudo computacional com base em dados reais de uma das empresas visitadas. / In the furniture industries, the cut of rectangular plates to produce smaller rectangular pieces is an every day task. To reduce the waste of material involved in this process and its influence in the cost of the products, a previous planning for the cuts is necessary. In the majority of the furniture companies situated at Northwest region of the state of São Paulo, the generation of cutting patterns is made manually and it is not a simple task. The goal of this work is to analyze the use of a computational system in the cutting patterns generation. This computational system is able to solve the two-dimensional cutting stock problem by the 2-stage Gilmory and Gomore method. Practical aspects found in the cutting patterns generation and strategies adopted for the companies in the production planning are discussed. We also report some results of the application of the computacional system to the cutting patterns generation based on real data of one company.

Made available in DSpace on 2014-06-11T19:27:08Z (GMT). No. of bitstreams: 0 Previous issue date: 2006-05-05Bitstream added on 2014-06-13T19:34:54Z : No. of bitstreams: 1 figueiredo_ag_me_sjrp.pdf: 1360576 bytes, checksum: 72fa7984af3edfd1d741b5f6773cc5d8 (MD5) / Neste trabalho, analisamos os padrões de corte adotados por uma Indústria de Móveis, e identificamos suas características básicas. Definimos, a partir dessas características, os padrões tabuleiros compostos, que pertencem a classe dos padrões de corte n-grupos, apresentada por Gilmore e Gomory (1965). Os padrões tabuleiros compostos preservam as facilidades de corte dos padrões tabuleiros, apresentando melhores índices de sobra de matéria-prima. Propomos uma heurística para a geração de um pool de padrões tabuleiros compostos, usados para resolver o problema de corte de estoque na indústria de móveis. / In this work, we analyze the cutting patterns used by a furniture Industry, and we determine some of its basic characteristics. We defined a composed checkerboard pattern, that belongs to the class of n-groups cutting patterns, presented by Gilmore and Gomory (1965). The composed checkerboard patterns preserve the easiness of the cutting process and have better indexes of waste. We propose a heuristic to generate a pool of composed checkerboard patterns to solve the cutting stock problem in the furniture Industry.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The PCE (Cutting Stock Problem) is to cut a set of objects available in stock to produce a quantity of items with specific sizes in order to optimize the raw material. Such problems have numerous industrial applications and has been widely studied in literature. The PCE's are classified as combinatorial optimization problems, because depending on the amount of requested items can be combined in numerous ways within an object forming an arrangement of cut. The number of possible combinations is, in practice, very high, requiring well-developed techniques are developed to determine an optimum arrangement. In defining the arrangements of cut is needed to graph the components of the problem and in this case, the tools used in the implementation must have the ability to manipulate geometric. In this paper, the combinatorial problem was approached from the GRASP heuristic technique and as a tool of manipulation was employed geometric applications deployed in an environment of Computer Aided Design (CAD). Furthermore, we proposed an integration of arrays of cutting systems with computer-aided manufacturing (CAM). The analysis of performance of the developed algorithm considers data provided by a furniture industry in the region of Santa Maria. The results obtained by the algorithm were compared to results generated by specialized software, consisting that the proposed method presents a similar performance, which demonstrates the feasibility of using CAD tools to implement solutions in the industry of PCE small and medium businesses. / O Problema de Corte de Estoque Bidimensional (PCEB) consiste em cortar um conjunto de objetos disponíveis em estoque para produzir uma quantidade de itens com tamanhos específicos, de modo a otimizar a matéria prima. Tais problemas têm inúmeras aplicações industriais e tem sido amplamente estudados na literatura. Os PCEB são classificados como problemas de otimização combinatória, pois, dependendo da quantidade de itens solicitados, podem ser combinados de inúmeras maneiras dentro de um objeto formando um arranjo de corte. O número de combinações possíveis é, na prática, muito elevado, exigindo que técnicas bem elaboradas sejam desenvolvidas para determinar um arranjo ótimo. Na definição dos arranjos de corte é necessário representar graficamente os componentes do problema e neste caso, as ferramentas empregadas na implementação devem apresentar capacidade de manipulação geométrica. Neste trabalho, o problema combinatório foi abordado a partir da técnica heurística GRASP e como ferramenta de manipulação geométrica empregou-se aplicativos implementados em ambiente de Projetos Auxiliado por Computador (CAD). Além disso, foi proposta uma integração dos arranjos de cortes com sistemas de Manufatura Auxiliador por Computador (CAM). A analise de desempenho do algoritmo desenvolvido considera dados fornecidos por uma indústria moveleira da região de Santa Maria. Os resultados obtidos pelo algoritmo foram comparados aos resultados gerados por software especializado, constando-se que a metodologia proposta apresenta um desempenho semelhante, o que demonstra a viabilidade o uso das ferramentas CAD para implementação de soluções PCE em indústria de pequeno e médio porte.

Orientador: Maria do Socorro Nogueira Rangel / Banca: Robinson Hoto / Banca. Trajano Pires da Nóbrega Neto / Resumo: Diariamente, em indústrias de móveis, painéis retângulares de madeira são cortados em retângulos menores para a manufatura de seus produtos. Por causa da possível perda de material envolvida neste processo e de sua influência no custo dos produtos, existe a necessidade de um planejamento prþevio para a realização dos cortes. Na maioria das empresas de móveis situadas na região Noroeste do estado de São Paulo, este planejamento é feito manualmente e não é uma tarefa simples. O enfoque deste trabalho þe analisar a utilização de um sistema computacional no planejamento do corte de painéis de madeira. Esta ferramenta é capaz de resolver o problema do corte bidimensional segundo o algoritmo de dois estþagios de Gilmory e Gomore. Aspectos práticos encontrados no corte dos painéis e estratégias adotadas pelas empresas no planejamento da produção são abordados. Além disso, apresentamos os resultados de um estudo computacional com base em dados reais de uma das empresas visitadas. / Abstract: In the furniture industries, the cut of rectangular plates to produce smaller rectangular pieces is an every day task. To reduce the waste of material involved in this process and its influence in the cost of the products, a previous planning for the cuts is necessary. In the majority of the furniture companies situated at Northwest region of the state of São Paulo, the generation of cutting patterns is made manually and it is not a simple task. The goal of this work is to analyze the use of a computational system in the cutting patterns generation. This computational system is able to solve the two-dimensional cutting stock problem by the 2-stage Gilmory and Gomore method. Practical aspects found in the cutting patterns generation and strategies adopted for the companies in the production planning are discussed. We also report some results of the application of the computacional system to the cutting patterns generation based on real data of one company. / Mestre