• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tesis Doctoral
DOI
https://doi.org/10.11606/T.45.2004.tde-20210729-135851
Documento
Autor
Nombre completo
Glauber Ferreira Cintra
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2003
Director
Título en portugués
Algoritmos para problemas de corte de guilhotina bidimensional
Palabras clave en portugués
Problemas Combinatórios Clássicos
Resumen en portugués
Muitas indústrias têm como desafio encontrar soluções mais econômicas possíveis para o problema de cortar objetos grandes visando a produção de objetos menores de dimensões especificadas, ou o problema de empacotar uma coleção de objetos pequenos dentro de objetos grandes. Tais problemas são chamados de problemas de corte de empacotamento e são, em geral, NP-difíceis. Em muitas aplicações, os objetos grandes (placas) e os objetos pequenos (itens) têm apenas duas dimensões relevantes e possuem a forma retangular. Além disso, é comum a restrição de que os cortes em cada objeto sejam de guilhotina, isto é, estes devem ser paralelos a um de seus lados e se estender desde um lado do objeto até o lado oposto, problemas desse tipo são chamados de problemas de corte de guilhotina bidimensional. Algoritmos para tais tipos de problemas constituem o tema central desta tese. Investigamos o problema de corte de estoque bidimensional com demandas (PCED IND. 2) (um caso mais geral em que os cortes não precisam ser de guilhotina) e introduzimos o conceito de padrões semi-homogêneos. Fazendo uso de tais padrões, desenvolvemos um algoritmo polinomial cuja razão de aproximação absoluta é 4, e mostramos que esta razão é justa. Ainda utilizando padrões semi-homogêneos, desenvolvemos um algoritmo que resolve uma variante do 'PCED IND. 2' na qual as placas e os itens são quadrados. Provamos que este algoritmo tem razão de aproximação assintótica entre 2,4166 e 2,6875. Até onde sabemos, estes são os primeiros algoritmos de aproximaçãopropostos para tais problemas. Desenvolvemos ainda um algoritmo para o problema de corte de estoque bidimensional binário com rotações e provamos que esse algoritmo possui razão de aproximação assintótica não maior que 4. Utilizando a fórmula de recorrência proposta por Beasley e os pontos de discretização definidos por Herz, desenvolvemos um algoritmo pseudo-polinomial para o problema de corte de ) de guilhotina bidimensional com valor (PCGV IND. 2) baseado em programação dinâmica. Chamamos tal algoritmo de 'PCGV IND. 2 PD'. Este algoritmo também resolve uma variante do 'PCGV IND. 2' na qual os itens podem sofrer rotações ortogonais. Apresentamos também um algoritmo baseado em enumeração explicíta e em programação dinâmica para calcular os pontos de discretização. Mostramos que, se os itens não são muito pequenos em relação ao tamanho das placas, então o algoritmo 'PCGV IND. 2 P-D' requer tempo polinomial. Implementamos o 'PCGV IND. 2 PD' e resolvemos todas as instâncias do 'PCGV IND. 2' encontradas na OR-LIBRARY. Destacamos que para uma destas instâncias (mencionada há duas décadas) não se conhecia uma solução ótima
Título en inglés
not available
Resumen en inglés
not available
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2021-07-29
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.