Orientador: Clovis Perin Filho / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-20T00:13:37Z (GMT). No. of bitstreams: 1 Rangel_MariadoSocorroNogueira_M.pdf: 1539388 bytes, checksum: 1b7cb5400a240ba143c6750c03f7c7ac (MD5) Previous issue date: 1990 / Resumo: Não informado / Abstract: Not informed / Mestrado / Mestre em Matemática Aplicada

Neste trabalho é apresentada uma revisão do método simplex com geração de colunas e sua aplicação ao problema de corte de estoque. É apresentado o problema combinado, que acopla os problemas de dimensionamento de lotes e de corte de estoque, incluindo uma formulação matemática deste problema. Em seguida consideramos algumas propriedades da matriz de restrições e como construir uma base esparsa para ela, utilizando um reordenamento estático das colunas básicas. Resultados numéricos de uma implementação em MATLAB que realiza trocas de colunas da base e verifica sua esparsidade, simulando o método simplex são apresentados. Após uma troca de colunas básicas, estas são atualizadas de forma eficiente, de modo que cause o menor preenchimento da matriz. Foram realizados também testes computacionais para verificar a robustez do método, através de operações inversas à decomposição e comparação com as colunas originais. Concluímos que a proposta de construção da base estática esparsa leva a bons resultados computacionais com relação à velocidade e robustez em comparação com abordagens que não consideram a estrutura esparsa da matriz de restrições.

Os problemas de corte de estoque unidimensional consistem em cortar um conjunto de peças disponíveis em estoque para produzir um conjunto de itens em quantidades especificadas, em que apenas uma dimensão é relevante. Tais problemas têm inúmeras aplicações industriais e são bastante estudados na literatura. Tipicamente, esses problemas de corte apresentam uma característica comum - a minimização das perdas -entretanto, neste trabalho, consideramos que se uma perda é suficientemente grande para ser reaproveitada no futuro, não deve ser contabilizada como perda. Isto introduz uma postura diferente frente ao problema de corte: até que ponto a solução de perda mínima é a mais interessante, já que sobras podem ser reaproveitadas? Algumas características para considerar se uma solução é desejável são definidas e alterações em métodos heurísticos clássicos são propostas, de modo que os padrões de corte com perdas indesejáveis (nem tão grande, nem tão pequena) sejam alterados. As análises das soluções heurísticas são realizadas com base na resolução de um conjunto de classes de exemplos geradas aleatoriamente.

Neste trabalho é apresentada uma revisão do método simplex com geração de colunas e sua aplicação ao problema de corte de estoque. É apresentado o problema combinado, que acopla os problemas de dimensionamento de lotes e de corte de estoque, incluindo uma formulação matemática deste problema. Em seguida consideramos algumas propriedades da matriz de restrições e como construir uma base esparsa para ela, utilizando um reordenamento estático das colunas básicas. Resultados numéricos de uma implementação em MATLAB que realiza trocas de colunas da base e verifica sua esparsidade, simulando o método simplex são apresentados. Após uma troca de colunas básicas, estas são atualizadas de forma eficiente, de modo que cause o menor preenchimento da matriz. Foram realizados também testes computacionais para verificar a robustez do método, através de operações inversas à decomposição e comparação com as colunas originais. Concluímos que a proposta de construção da base estática esparsa leva a bons resultados computacionais com relação à velocidade e robustez em comparação com abordagens que não consideram a estrutura esparsa da matriz de restrições.

Os problemas de corte de estoque unidimensional consistem em cortar um conjunto de peças disponíveis em estoque para produzir um conjunto de itens em quantidades especificadas, em que apenas uma dimensão é relevante. Tais problemas têm inúmeras aplicações industriais e são bastante estudados na literatura. Tipicamente, esses problemas de corte apresentam uma característica comum - a minimização das perdas -entretanto, neste trabalho, consideramos que se uma perda é suficientemente grande para ser reaproveitada no futuro, não deve ser contabilizada como perda. Isto introduz uma postura diferente frente ao problema de corte: até que ponto a solução de perda mínima é a mais interessante, já que sobras podem ser reaproveitadas? Algumas características para considerar se uma solução é desejável são definidas e alterações em métodos heurísticos clássicos são propostas, de modo que os padrões de corte com perdas indesejáveis (nem tão grande, nem tão pequena) sejam alterados. As análises das soluções heurísticas são realizadas com base na resolução de um conjunto de classes de exemplos geradas aleatoriamente.

Orientadores : Paulo Morelato França, Marcos Nereu Arenales / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-29T01:58:08Z (GMT). No. of bitstreams: 1 Gramani_MariaCristinaNogueira_D.pdf: 978844 bytes, checksum: d3c3f8a368908933e14e2242a999c6d7 (MD5) Previous issue date: 2001 / Doutorado

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2010-04-16Bitstream added on 2014-06-13T20:28:18Z : No. of bitstreams: 1 martins_at_me_sjrp.pdf: 1107946 bytes, checksum: 4889aecbca6c259500ae7438b3cb059b (MD5) / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / Neste trabalho estudamos o problema de corte de estoque bidimensional originado da realidade de uma fábrica de móveis. Descrevemos o sistema de produção de uma fábrica de móveis característica do Polo Moveleiro de Votuporanga, com ênfase no setor de corte da matéria-prima, e propomos um algoritmo para resolver o problema de corte de estoque considerando a minimização do número de objetos cortados e do número de ciclos da serra. A ideia principal do algoritmo proposto (AFM-P) consiste em adicionar ao problema, de forma dinâmica, restrições que imponham uma frequência mínima para a utilização de um dado padrão de corte. A cada iteração uma solução é gerada e no final do algoritmo existe um conjunto de soluções que são analisadas segundo critérios de dominância. Realizamos um estudo computacional utilizando os dados reais da fábrica visitada para analisar o comportamento do AFM-P. O estudo computacional mostrou que através do algoritmo proposto é possível encontrar soluções próximas e, na maioria das vezes, melhores que a prática da indústria tomada como estudo de caso / In this work we study the two-dimensional cutting stock problem originated from a furniture industry. We describe the production system of a characteristic furniture plant situated at Votuporanga Regional Center and we propose an algorithm to solve the cutting stock problem taking into account the minimization of the number of objects and the number of saw cycles. The main idea of the algorithm (AFM-P) is adding to the problem, in a dynamic way, constraints that impose a minimum frequency to the use of a given cutting pattern. At each iteration a solution is generated and at the end there is a set of solutions that are analyzed according to dominance criteria. The AFM-P algorithm is tested using data from the furniture plant visited. The computational study shows that using the proposed algorithm it is possible to find solutions that are close the ones used in the industry practice and, in most cases, better than theirs

Made available in DSpace on 2014-06-11T19:22:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-02-28Bitstream added on 2014-06-13T20:48:30Z : No. of bitstreams: 1 greccho_tx_me_sjrp.pdf: 478270 bytes, checksum: 87e981ec8683b4fe4c15ca85ae4b8b66 (MD5) / Neste trabalho apresentamos métodos de decomposição para problemas de otimização inteira que auxiliam no processo de geração de colunas aplicado ao problema de corte de estoque bidimensional. É feita uma revisão de literatura sobre problemas considerando o corte simultâneo de objetos (ciclos da serra). Visando a aceleração do método de ge- ração de colunas, propomos uma técnica de decomposição para o problema de corte de estoque com minimização de ciclos da serra que incorpora informações duais associadas às restrições de ciclos da serra no subproblema pricing / In this paper we present decomposition methods for integer optimization problems that will help the column generation process applied to the two-dimensional cutting stock problem. It’s made a literature review about problems considering the simultaneous cutting of objects (cycles saw). Seeking an acceleration in the generation column method, the propose a decomposition technique for the cutting stock problem with minimization saw cycles which incorporates dual information associated to saw cycles restrictions in the pricing subproblem

Orientador: Maria do Socorro Nogueira Rangel / Banca: Deisemara Ferreira / Banca: Silvio Alexandre de Araujo / Resumo: Neste trabalho apresentamos métodos de decomposição para problemas de otimização inteira que auxiliam no processo de geração de colunas aplicado ao problema de corte de estoque bidimensional. É feita uma revisão de literatura sobre problemas considerando o corte simultâneo de objetos (ciclos da serra). Visando a aceleração do método de ge- ração de colunas, propomos uma técnica de decomposição para o problema de corte de estoque com minimização de ciclos da serra que incorpora informações duais associadas às restrições de ciclos da serra no subproblema pricing / Abstract: In this paper we present decomposition methods for integer optimization problems that will help the column generation process applied to the two-dimensional cutting stock problem. It's made a literature review about problems considering the simultaneous cutting of objects (cycles saw). Seeking an acceleration in the generation column method, the propose a decomposition technique for the cutting stock problem with minimization saw cycles which incorporates dual information associated to saw cycles restrictions in the pricing subproblem / Mestre

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