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

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

Orientadores: Antonio Carlos Moretti, Luis Leduino de Salles Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-15T18:13:59Z (GMT). No. of bitstreams: 1 Marciniuk_FernandaLedo_M.pdf: 1221484 bytes, checksum: b1408936331c027b4c3cc1129bc0105a (MD5) Previous issue date: 2010 / Resumo: O problema de corte de estoque ordenado, um problema relativamente novo na literatura, e uma adaptação do problema de corte de estoque tradicional onde algumas restrições quanto a limitação do numero de ordens de produção em processamento são adicionadas. Esta dissertação tem como objetivo estudar uma nova abordagem deste problema utilizando uma aplicação da metaheurística colônia de formigas. Esta metaheurística utiliza os princípios de auto-organização de uma população de formigas visando a resolução de problemas de otimização combinatorial / Abstract: The Ordered Cutting Stock Problem (OCSP), a relatively recent problem in technical literarture, is a variant of the more well-known Cutting Stock Problem (CSP). This variant includes some new constraints in the mathematical formulation, regarding the number of production orders being processed simultaneously. This work studies a new approach to solve the OCSP, applying the Ant Colony Optimization (ACO) metaheurisitic. This metaheuristic is based in the self-organizing principles that govern ant population's behaviour, solving combinatorial optimization problems / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

Orientador: Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T18:16:55Z (GMT). No. of bitstreams: 1 Hokama_PedroHenriqueDelBianco_M.pdf: 1340789 bytes, checksum: b5cc3f26e41b90afabdfac5c7a33bf05 (MD5) Previous issue date: 2011 / Resumo: Nesta dissertação de mestrado apresentamos um método exato para o Problema do Caixeiro Viajante com Restrições de Empacotamento Tridimensional, que combina o Problema do Caixeiro Viajante o Problema de Empacotamento Tridimensional com Restrição de Ordem. Neste problema, um veículo deve partir carregado de um depósito e entregar caixas em pontos pré-definidos para seus clientes. Cada cliente tem um conjunto de caixas que deve receber e o objetivo é minimizar o custo de deslocamento do veículo. As caixas devem ser retiradas a partir da porta do contêiner do veículo e a remoção das caixas de um cliente não podem ser obstruídas pelas caixas a serem descarregadas posteriormente. Propomos uma abordagem exata baseada em branch-and-cut para buscar uma rota de custo mínimo. Apresentamos algumas adaptações de algoritmos da literatura e uma formulação em Programação por Restrições para encontrar um empacotamento que obedece restrições de ordem. Realizamos testes computacionais em instâncias geradas aleatoriamente e comparamos resultados com os algoritmos adaptados da literatura. Os resultados foram bastante satisfatórios resolvendo instâncias de tamanho médio em tempo computacional aceitável na prática / Abstract: We present an exact method for the Traveling Salesman Problem with Three-dimensional Loading Constraints. This problem combines the Traveling Salesman Problem, and the Three- Dimensional Packing Problem With Loading Constraints. In this problem, a vehicle must be loaded at the depot and deliver boxes to the customers. Every customer has a set of boxes that should receive and our goal is to minimize the travel cost of the vehicle. Unloading is done through a single side of the container and items from an unloading customer must not be blocked by items to be delivered later. We propose exact and heuristic branch-and-cut algorithm to find a minimum cost route. Adaptations of algorithms from the literature and a Constraint Programming formulation is presented to find a packing that consider unloading contraints. We performed computational tests on instances randomly generated and compared results with the algorithms adapted from literature. The results were quite satisfactory resolving several instances in reasonable computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Made available in DSpace on 2014-06-11T19:26:56Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-05-28Bitstream added on 2014-06-13T20:55:44Z : No. of bitstreams: 1 mosquera_gp_me_sjrp.pdf: 826166 bytes, checksum: 1a60fcaee005ae7c3a53ba9d9dad9b98 (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Neste trabalho, estudamos o Problema de Corte de Estoque Bidimensional aplicado à indústria de móveis. Para realizar este estudo, visitamos uma empresa característica do noroeste paulista com o intuito de observarmos a prática da empresa e desenvolver métodos de solução para aumentar sua produtividade. O critério de otimização considerado é a redução do número de ciclos da serra. Três métodos de solução foram propostos para a resolução do problema. O primeiro utiliza um modelo matemático que contém restrições que garantem que o número de objetos cortados de acordo com um determinado padrão de corte seja um múltiplo da capacidade da serra. Duas heurísticas, baseadas na heurística de repetição exaustiva de padrões de corte, são propostas para atender exatamente às demandas e reduzir o número de ciclos da serra na indústria de móveis visitada. Os estudos computacionais realizados, mostraram que as estratégias propostas obtêm resultados próximos aos da empresa e, em alguns casos, melhores. / In this work we have studied the Two-dimensional Cutting Stock Problem applied to a furniture industry. In order to carry out this study, we have visited a characteristic company at the Northwest region of the state of São Paulo in order to observe the industry practice and develop solution methods to increase its productivity. The goal is minimize the number of saw cycles. We propose three solution methods to solve the problem. The first one is a mathematical model which imposes that the number of objects to be cut according to a given cutting pattern is a multiple of the saw capacity. Two heuristics based on the sequential heuristic procedure are proposed to fulfil the demands and to reduce the number of saw cycles. By the computational tests results, we can conclude that these solution methods provide similar results to the industry's practice and, in some cases, better ones.

Esta dissertação apresenta a aplicação de uma nova abordagem utilizando Algoritmo Genético na resolução do Problema de Corte Unidimensional na minimização de dois objetivos, geralmente conflitantes, o número de objetos processados e o setup, simultaneamente. O problema de corte consiste, basicamente, em encontrar a melhor maneira de obter peças de tamanhos distintos (itens) a partir do corte de peças maiores (objetos) com o objetivo de minimizar alguma espécie de custo ou maximizar o lucro. A disposição dos itens no objeto para a realização de cortes durante sua produção é denominada padrão de corte. E o setup é o tempo de preparação de máquina. O modelo do problema, a função objetivo e o método proposto denominado SingleGA, bem como os passos utilizados para sua resolução, também são apresentados. Os resultados obtidos pelo SingleGA são comparados com os métodos SHP, Kombi234, ANLCP300 e Symbio, encontrados na literatura, a fim de verificar a capacidade de encontrar soluções viáveis e competitivas. Os resultados computacionais mostram que o método proposto, o qual utiliza apenas um algoritmo genético para resolver esses dois objetivos inversamente relacionados, proporciona bons resultados.

Orientador: Maria do Socorro Nogueira Rangel / Banca: Horácio Hideki Yanasse / Banca: Silvio Alexandre de Araújo / Resumo: Neste trabalho, estudamos o Problema de Corte de Estoque Bidimensional aplicado à indústria de móveis. Para realizar este estudo, visitamos uma empresa característica do noroeste paulista com o intuito de observarmos a prática da empresa e desenvolver métodos de solução para aumentar sua produtividade. O critério de otimização considerado é a redução do número de ciclos da serra. Três métodos de solução foram propostos para a resolução do problema. O primeiro utiliza um modelo matemático que contém restrições que garantem que o número de objetos cortados de acordo com um determinado padrão de corte seja um múltiplo da capacidade da serra. Duas heurísticas, baseadas na heurística de repetição exaustiva de padrões de corte, são propostas para atender exatamente às demandas e reduzir o número de ciclos da serra na indústria de móveis visitada. Os estudos computacionais realizados, mostraram que as estratégias propostas obtêm resultados próximos aos da empresa e, em alguns casos, melhores. / Abstract: In this work we have studied the Two-dimensional Cutting Stock Problem applied to a furniture industry. In order to carry out this study, we have visited a characteristic company at the Northwest region of the state of São Paulo in order to observe the industry practice and develop solution methods to increase its productivity. The goal is minimize the number of saw cycles. We propose three solution methods to solve the problem. The first one is a mathematical model which imposes that the number of objects to be cut according to a given cutting pattern is a "multiple" of the saw capacity. Two heuristics based on the sequential heuristic procedure are proposed to fulfil the demands and to reduce the number of saw cycles. By the computational tests results, we can conclude that these solution methods provide similar results to the industry's practice and, in some cases, better ones. / Mestre

Esta dissertação apresenta a aplicação de uma nova abordagem utilizando Algoritmo Genético na resolução do Problema de Corte Unidimensional na minimização de dois objetivos, geralmente conflitantes, o número de objetos processados e o setup, simultaneamente. O problema de corte consiste, basicamente, em encontrar a melhor maneira de obter peças de tamanhos distintos (itens) a partir do corte de peças maiores (objetos) com o objetivo de minimizar alguma espécie de custo ou maximizar o lucro. A disposição dos itens no objeto para a realização de cortes durante sua produção é denominada padrão de corte. E o setup é o tempo de preparação de máquina. O modelo do problema, a função objetivo e o método proposto denominado SingleGA, bem como os passos utilizados para sua resolução, também são apresentados. Os resultados obtidos pelo SingleGA são comparados com os métodos SHP, Kombi234, ANLCP300 e Symbio, encontrados na literatura, a fim de verificar a capacidade de encontrar soluções viáveis e competitivas. Os resultados computacionais mostram que o método proposto, o qual utiliza apenas um algoritmo genético para resolver esses dois objetivos inversamente relacionados, proporciona bons resultados.