Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276336
Type: TESE
Degree Level: Mestrado
Title: O problema do corte bidimensional : uma abordagem utilizando o metodo de geração de colunas
Author: Teodoro, Alan Augusto
Advisor: Miyazawa, Flávio Keidi, 1970-
Abstract: Resumo: Neste trabalho é realizado um estudo experimental de técnicas de otimização para gerar soluções eficientes para o problema do corte bidimensional, que pode ser definido como: dado um número finito n de itens retangulares de largura li, comprimento Ci e demanda di, a serem obtidos de retângulos maiores de dimensão LxC, encontrar padrões de corte que atendam a uma demanda de itens utilizando o menor número possível de retângulos maiores. O problema foi formulado através de um modelo de programação linear inteira. Para obter soluções de custo reduzido para o problema, aplicamos o método de geração de colunas, obtendo então soluções viáveis para o problema relaxado do programa linear inteiro. Utilizamos um algoritmo de aproximação para obter uma solução inicial de qualidade e métodos de arredondamento com tratamento de problema residual para transformar a solução fracionária em soluções viáveis para o problema. Finalmente, diversos estudos são realizados através de testes computacionais

Abstract: In this work we describe an experimental study of optimization techniques to generate efficient results for the two-dimensional cutting stock problem which can be defined as follows: given a finite number n of rectangular items of width li, length Ci and demand di, to be cut from larger rectangles with dimensions LxC, find cutting pattems which attend the demand of the requested items minimizing the number of larger rectangles. The problem is formulated as an integer programming mode!. To obtain solutions with reduced cost to the problem, we apply the column generation method, obtaining feasible solutions for the relaxed integer programo We use an approximation algorithm to generate a good initial solution and rounding techniques with treatment of the residual problem to transform the fractional solution into feasible solutions to the problem. Finally, several studies are realized through computational experiments
Subject: Otimização combinatória
Programação inteira
Pesquisa operacional
Language: Português
Editor: [s.n.]
Citation: TEODORO, Alan Augusto. O problema do corte bidimensional: uma abordagem utilizando o metodo de geração de colunas. 2003. 63f. Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/276336>. Acesso em: 3 ago. 2018.
Date Issue: 2003
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Teodoro_AlanAugusto_M.pdf1.95 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.