Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276270
Type: TESE
Title: Um algoritmo exato para o problema de empacotamento bidimensional em faixas
Title Alternative: A exact algorithm to two-dimensional level strip packing
Author: Andrade, Carlos Eduardo de, 1981-
Advisor: Miyazawa, Flávio Keidi, 1970-
Abstract: Resumo: Problemas de corte e empacotamento aparecem freqüentemente na indústria e comércio, e sua solução de forma otimizada pode trazer grandes ganhos em diversos setores.Um problema muito comum, notadamente no setor têxtil e do papel, é o corte de um rolo ou faixa de um determinado material para obtenção de itens menores, onde temos por objetivo utilizar a menor extensão do rolo/faixa possível. Este problema, conhecido como Problema de Empacotamento Bidimensional em Faixas (PEBF), é tido como um problema de otimização combinatória de difícil resolução. Neste trabalho, apresentamos um algoritmo exato para o PEBF restrito a cortes de dois estágios (PEBF2). O algoritmo usa a técnica de branch-and-price, que utiliza, por sua vez, heurísticas baseadas em algoritmos aproximados para a obtenção de limitantes superiores. O algoritmo se mostrou eficaz na obtenção de soluções para instâncias de pequeno e médio porte

Abstract: Cutting and packing problems are common problems that occur in many industry and business process. Their optimized resolution leads to great profits in several sectors. A common problem, that occur in textil and paper industries, is to cut a strip of some material to obtain several small items, using the minimum length of material. This problem, known by Two Dimensional Strip Packing Problem (2SP), is a hard combinatorial optimization problem. In this work, we present an exact algorithm to 2SP, restricted to two staged cuts (known by Two Dimensional Level Strip Packing, 2LSP). The algorithm uses the branch-and-price technique, and heuristics based on approximation algorithms to obtain upper bounds. The algorithm obtained optimal or almost optimal for small and moderate sized instances
Subject: Otimização combinatória
Algoritmos
Programação inteira
Pesquisa operacional
Language: Português
Editor: [s.n.]
Date Issue: 2006
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Andrade_CarlosEduardode_M.pdf1.48 MBAdobe PDFView/Open


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